【数据结构】二叉树的性质与存储结构

1. 二叉树的基本概念

二叉树是n(n>=0)个结点的有限集合：

1. 或者为空二叉树，即n=0。
2. 或者由一个根结点和两个互不相交的被称为跟的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

特点：

1. 每个结点至多只有两棵子树。
2. 左右子树不能颠倒（二叉树是度为2的有序树）。

说明：二叉树可以有五种状态。空二叉树、只有左子树、只有右子树、只有根结点、左右子树都有。

2. 几个特殊的二叉树

1. 满二叉树

特点：

1. 只有最后一层有叶子结点。
2. 不存在度为1的结点。
3. 按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1；结点的父结点为i/2向下取整（如果有）。

2. 完全二叉树

特点：

1. 只有最后两层可能有叶子结点。
2. 最多只有一个度为1的结点。
3. 按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1；结点的父结点为i/2向下取整（如果有）。
4. 对于最后一个结点n，i<=n/2向下取整为分支结点。i>n/2向下取整为叶子结点。
5. 如果某个结点只有一个孩子，那一定是左孩子。

3. 二叉排序树

4. 平衡二叉树

3. 二叉树的性质

1. 性质1

设非空二叉树中度为0、1和2的结点个数分别为n0、n1和n2，则n0=n2+1。（叶子结点比二分支结点多一个）

2. 性质2

3. 性质3

4. 完全二叉树性质

1. 性质1

2. 性质2

3. 性质3

5. 二叉树的存储结构

1. 二叉树的顺序存储

#define MaxSize 100
struct TreeNode{
    ElemType value;  // 结点中的数据元素
    bool isEmpty;  // 结点是否为空
};
//定义一个长度为MaxSize的数组t，按照从上至下、从左至右的顺序依次存储完全二叉树的各个结点。
TreeNode t[MaxSize];

// 初始化时所有结点标记为空
for(int i=0;i<MaxSize;i++){
    t[i].isEmpty=true;
}

注意：上面说的几个重点一定要把二叉树的结点编号与完全二叉树对应起来。否则结论不成立。

结论:二叉树的顺序存储结构，只适合存储完全二叉树。

2. 二叉树的链式存储

struct ElemType{
    int value;
}

typedef struct BiTNode{
    ElemType data;  // 数据域
    struct BiTNode *lchild,*rchild;  // 左、右孩子指针
}BiTNode,*BiTree;

注意：n个结点的二叉链表共有n+1个空链域。

// 定义一棵空树
BiTNode root = NULL;

// 插入根结点
root = (BiTree)malloc(sizeof(BiTNode));
root->data={1};
root->lchild=NULL;
root->rchild=NULL;

// 插入新结点
BiTNode *p=(BiTNode *)malloc(sizeof(BiTNode));
p->data={2};
p->lchild=NULL;
p->rchild=NULL;
root->lchild=p;  // 作为根结点的左孩子