数据结构——二叉树的性质和存储结构
二叉树的抽象类型定义
基本操作：
CreateBiTree(&T，definition)
初始条件：definition给出二叉树T的定义。
操作结果:按definition构造二叉树T。
PreOrderTraverse(T)
初始条件:二叉树T存在。
操作结果:先序遍历T，对每个结点访问一次。
InOrderTraverse(T)
初始条件:二叉树T存在。
操作结果:中序遍历T，对每个结点访问一次。
PostOrderTraverse(T)
初始条件:二叉树T存在。
操作结果:后序遍历T，对每个结点访问一次。
二叉树的性质和存储结构
在二叉树的第i层最少有1个结点。
深度为k的二叉树最少有k个结点。
两种特殊形式的二叉树
- 满二叉树
- 完全二叉树
满二叉树
为什么要研究这两种特殊形式？
因为它们在顺序存储方式下可以复原！
满二叉树
特点：
1、每一层上的结点数都是最大结点数（即每层都满）；
2、叶子结点全部在最底层
对满二叉树结点进行编号
- 编号规则：从根结点开始，自上而下，自左向右。
- 每一结点位置都有元素。
满二叉树在同样深度的二叉树中结点个数最多
满二叉树在同样深度的二叉树中叶子结点个数最多
完全二叉树
注:在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。
一定是连续的去掉!!!
特点:1.叶子只可能分布在层次最大的两层上；
2.对任一结点，如果其右子树的最大层次为i，则其左子树的最大层次必为i或i+1。
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
完全二叉树的性质
性质4表明了完全二叉树结点数n与完全二叉树深度k之间的关系
性质5：如果对一棵有n个结点的完全二叉树（深度为
）的结点按层序编号（从第1层到第
层，每层从左到右），则对任一结点i(1<=i<=n)有：
性质5表明了完全二叉树中双亲结点编号与孩子结点编号之间的关系。
二叉树的存储结构
二叉树的顺序存储
实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。
二叉树的顺序存储的缺点：
最坏情况：深度为k的且只有k个结点的单支树需要长度为 
的一维数组。
这样存储的话会浪费空间，存储密度低，适于存储满二叉树和完全二叉树。
二叉树的链式存储
二叉树结点的特点
存储方式
data：存储结点数据；
lchild：指向左孩子的指针；
rchild：指向右孩子的指针。
二叉链表存储结构
typedef struct BiNode {TElemType data;struct BiNode* lchild, * rchild;//左右孩子指针
}BiNode,*BiTree;BiNode是普通的结点类型
BiTree是指向有这样三个成员的指针
通过头指针找到这棵树，头指针表示树的时候通常会用字母T表示，头指针没有数据域。
如上图，我们的根节点有左孩子没有右孩子，所以在指针域中，指向左孩子的指针为存储结点B的地址，指向右孩子的指针为空。
在n个指针的二叉链表中，有多少个空指针域呢？
分析：必有2n个链域。除根结点外，每个结点有且只有一个双亲，所以只会有n-1个结点的链域存放指针，指向非空子女结点。
所以空指针数目=2n - （n-1）= n + 1
三叉链表存储结构
typedef struct TriTNode {TElemType data;struct BiNode* lchild,*parent, * rchild;//左右孩子指针
}TriTNode,*TriTree;TriTNode是普通的结点类型
TriTree是指向有这样四个成员的指针三叉链表比二叉链表多一个指针域，指向结点的双亲。