5.2 二叉树的概念
5.2.1 二叉树的定义
二叉树是n(n≥0)个结点的有限集合：
① 或者为空二叉树，即n = 0。
② 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
特点：①每个结点至多只有两棵子树 ②左右子树不能颠倒（二叉树是有序树）
二叉树的五种状态
- 空二叉树
- 只有左子树(即右子树为空)
- 只有右子树(即左子树为空)
- 只有根节点(左右子树都为空)
- 左右子树都有
几个特殊的二叉树
满二叉树。一棵高度为h，且含有2^h - 1个结点的二叉树
特点：
①只有最后一层有叶子结点
②不存在度为1的结点
③按层序从1开始编号，结点i的左孩子为2i,右孩子为2i+1;结点的父节点为(向下取整)
完全二叉树。当且仅当其每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应时，称为 完全二叉树
特点：
①只有最后两层可能有叶子结点
②最多只有一个度为1的结点
③按层序从1开始编号，结点i的左孩子为2i,右孩子为2i+1;结点的父节点为(向下取整)
④为分支结点，
为叶子结点
二叉排序树。一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：
左子树上所有结点的关键字均小于根结点的关键字；
右子树上所有结点的关键字均大于根结点的关键字。
左子树和右子树又各是一棵二叉排序树。
二叉排序树可用于元素的排序、搜索
平衡二叉树。树上任一结点的左子树和右子树的深度之差不超过1。
平衡二叉树能有更高的搜索效率
5.2.2 二叉树的常考性质
常见考点1：设非空二叉树中度为0、1和2的结点个数分别为n0、n1和n2，则 n0 = n2 + 1 （叶子结点比二分支结点多一个）
常见考点2：二叉树第 i 层至多有个结点（i≥1）
m叉树第 i 层至多有个结点（i≥1）
常见考点3：高度为h的二叉树至多有个结点（满二叉树）
高度为h的m叉树至多有 个结点。
等比数列求和公式：
完全二叉树的常考性质
常见考点1：具有n个(n>0)结点的完全二叉树高度h为或
常见考点2：对于完全二叉树，可以由的结点数 n 推出度为0、1和2的结点个数为n0、n1和n2
完全二叉树最多只有一个度为1的结点，即
5.2.3 二叉树的存储结构
二叉树的顺序存储
定义一个长度为 MaxSize 的数组 t，按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点
#define MaxSize 100
struct TreeNode{
ElemType value; //结点中的数据元素
bool isEmpty; //结点是否为空
}
//初始化树T
bool initTree(TreeNode T[]){
for(int i=0; i<MaxSize; i++){
t[i].isEmpty=true; //初始化时所有结点标记为空
}
return true;
}
void test(){
struct TreeNode t[MaxSize]; //TreeNode里面的每个元素对应一个结点
initTree(T);
}
常考的基本操作：
- i的左孩子 2i
- i的右孩子 2i+1
- i的父结点 [i/2]向下取整
- i所在的层次
或
若完全二叉树中有n个结点，则
- 判断i是否有左孩子 2i<n
- 判断i是否有右孩子 2i+1<n
- 判断i是否有叶子/分支结点 i>[n/2]向下取整
如果不是完全二叉树，顺序存储时一定要把二叉树的结点编号与完全二叉树对应起来
但是判断结点为空就不能用完全二叉树的公式方式判断，只能通过最开始定义的isEmpty来判但是但是这也会浪费很多存储空间，最坏情况:高度h且只有h个结点的单支树（所有结点只有右孩子），也至少需要2^h-1个存储单元,所以一般不采用链式存储
二叉树的链式存储
//二叉树的结点(链式存储)
typedef struct BiTNode{
ElemType data; //数据域
struct BiTNode *lchild, *rchild; //左右孩子指针
}BiTNode, *BiTree;
//初始化 插入根结点
bool initTree(BiTree &root){
root = (BiTree)malloc(sizeof(BiTNode));
root->data={1};
if(root == NULL)
return false;
root->lchild = NULL;
root->rchild = NULL;
return true;
}
struct ElemTpye{
int value;
};
//定义一颗空树
BiTree root=NULL;
树中的每个结点都会有一个data域，用来存放实际的数据元素，还会有两个指针分别指向左孩子和右孩子，如果没有可以直接把指针设为nullz
n个结点就会有2n个指针域
n个结点的二叉链表共有n+1个空链域 (可以用于构造线索二叉树)
