第8章 树和二叉树
树\r二叉树\r二叉树设计\r二叉树遍历\r线索二叉树\r哈夫曼树\r等价问题\r树与二叉树的转换\r树的遍历
主要知识点
8.1 树
1.树的定义
树是由n(n≥0)个结点组成的有限集合T。n=0的树称为空树；对n>0的树，有:(1)仅有一个特殊的结点称为根结点，根结点没有前驱结点；(2)当n>1时，除根结点外其余的结点分为m(m>0)个互不相交的有限集合T1,T2，…，Tm，其中每个集合Ti本身又是一棵结构和树类似的子树。
注：树的定义具有递归性，即“树中还有树”。
若干术语
结点：由数据元素和构造数据元素之\r 间关系的指针组成
结点的度：结点所拥有的子树的个数
叶结点：度为0的结点，也称作\r 终端结点
分支结点：度不为0的结点
孩子结点：树中一个结点的子树的根结点
双亲结点：若树中某结点有孩子结点，则这个结点就\r 称作它的孩子结点的双亲结点
兄弟结点：具有相同的双亲结点的结点
树的度：树中所有结点的度的最大值
结点的层次：从根结点到树中某结点所经路径上的分支数
树的深度：树中所有结点的层次的最大值
无序树：树中任意一个结点的各孩子结点之间的次序\r 构成无关紧要的树
有序树：树中任意一个结点的各孩子结点有严格排列\r 次序的树
森林：m（m≥0）棵树的集合
2.树的表示方法
(1)直观表示法
(2)形式化表示法
(3)凹入表示法
T=（D，R） \rDF = D1∪D2∪…∪Dm （1≤i,j≤m, Di∩Dj=￠）\rR={
A
B
C
D
E
F
G
H
I
J
K
L
3.树的抽象数据类型
数据集合: 树的结点集合，每个结点由数据元素和构造数 据元素之间关系的指针组成。\r\r操作集合: \r （1）创建MakeTree(T) \r （2）撤消DestroyTree(T)\r （3）双亲结点Parent(T, curr) \r （4）左孩子结点LeftChild(T, curr) \r （5）右兄弟结点RightSibling(T, curr) \r （6）遍历树Traverse(T, Visit())\r
4.树的存储结构
树的结点之间的逻辑关系主要有双亲-孩子关系，兄弟关系。因此，从结点之间的逻辑关系分，树的存储结构主要有：双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法四种组合。\r 指针有常规指针和仿真指针
(1)双亲表示法
(a)一棵树
（b)仿真指针的双亲表示法存储结构
树及其使用仿真指针的双亲表示法
(2)孩子表示法
双亲孩子表示法存储结构
(3)双亲孩子表示法
(4)孩子兄弟表示法
常规指针的孩子兄弟表示法
8.2 二叉树
一、二叉树：是n(n≥0)个结点的有限集合。n=0的树称为空二叉树；n>0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。\r 逻辑结构： 一对二（1:2） \r 基本特征:\r ① 每个结点最多只有两棵子树（不存在度大于2的结点）；\r ② 左子树和右子树次序不能颠倒。所以下面是两棵不同的树
1.二叉树的定义
二、满二叉树：在一棵二叉树中，如果所有分支结点都存在左\r 子树和右子树，并且所有叶子结点都在同一层上，这样的\r 二叉树称为满二叉树。\r三、完全二叉树：如果一棵深度为k，有n个结点的二叉树中各\r 结点能够与深度为k的顺序编号的满二叉树从1到n标号的 \r 结点相对应的二叉树称为完全二叉树。如下图所示
(a)满二叉树
(b)完全二叉树
问题:一个高度为h的完全二叉树最多有多少个结点?最少有多少个结点?
数据集合：二叉树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。\r操作集合：\r（1）创建MakeTree(T) \r（2）撤消DestroyTree(T)\r（3）左插入结点InsertLeftNode(curr, x) \r（4）右插入结点InsertRightNode(curr, x) \r（5）左删除子树DeleteLeftTree(curr) \r（6）右删除子树DeleteRightTree(curr) \r（7）遍历二叉树Traverse(T, Visit())
2.二叉树抽象数据类型
3.二叉树的性质
性质1:在一棵非空二叉树的第i层上至多有2i个结点（i≥0）。
性质2:深度为k的二叉树至多有2k 1-1个结点。\r 说明：深度k=-1，表示没有一个结点；深度k=0，表示只有一个根结点。
性质3: 具有n个结点的完全二叉树的深度k为?log2(n 1)? -1。
证明：根据性质2，对于有n个接点的深度为k的完全二叉树有\r 2k-1 性质4 对于一棵非空的二叉树，如果叶结点个数为n0，度为2的结点数为n2，则有\r n0= n2 1。\r证明：设n为二叉树的结点总数，n1为二叉树中度为1的结点个数，则有：\rn = n0 n1 n2 \r另外，在二叉树中，除根结点外的所有结点都有一个惟一的进入分支，设M为二叉树中所有结点的进入分支数，则有：\r M = n - 1\r 从二叉树的结构可知，二叉树的所有进入分支是由度为1的结点和度为2的结点发出的，每个度为1的结点发出一个分支，每个度为2的结点发出两个分支，所以又有：\r \r M = n1 2 × n2\r\r因此有：\r n - 1 = n1 2 × n2\r\r再把n=n0 n1 n2代入，则可以得到n0=n2 1。 性质5:对于一棵有n个结点的完全二叉树，按照从上至下和从左至右的顺序对所有结点从0开始顺序编号,则对于序号为i的结点(0≤i < n),有：\r (1)如果i>0，则其双亲是结点(i-1)/2(“/”表示整除） ；如果i=0，则结点i是根结点，无双亲。\r (2)如果2i 1＜n ，其左孩子是结点2i 1；如果2i 1≥n，则结点i无左孩子。\r (3)如果2i＋2＜n，其右孩子是结点2i＋2；如果2i＋2≥n，则结点i无右孩子。 8.3.1二叉树的存储结构\r 二叉树的存储结构主要有三种：顺序存储结构、链式存储结\r构和仿真指针存储结构。\r\r1. 二叉树的顺序存储结构\r 完全二叉树的结点可按从上至下和从左至右的次序存储在一维数组中，其结点之间的关系可由公式计算得到，这就是二叉树的顺序存储结构。下面两棵树在数组中的存储结构分别为： 8.3二叉树的设计和实现 对于一般的非完全二叉树显然不能直接使用二叉树的顺序存储结构。可以首先在非完全二叉树中增添一些并不存在的空结点使之变成完全二叉树的形态，然后再用顺序存储结构存储。 (a)一般二叉树 (b)完全二叉树形态 (c) 在数组中的存储形式 2. 二叉树的链式存储结构\r 二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉树最常用的的链式存储结构是二叉链。二叉链存储结构的每个结点包含三个域，分别是数据域data、左孩子指针域leftChild和右孩子指针域rightChild。二叉链存储结构中每个结点的图示结构为： 二叉链存储结构的二叉树也有不带头结点和带头结点两种。带头结点的二叉链存储结构的二叉树见下图(b)，不带头结点的二叉链存储结构的二叉树如下图(a)所示。 图8-10 二叉链存储结构的二叉树 (a)不带头结点的二叉树 (b)带头结点的二叉树 3.二叉树的仿真指针\r 二叉树的仿真指针存储结构是用数组存储二叉树中的结点，数组中每个结点除数据元素域外，再增加仿真指针域用于仿真常规指针建立二叉树中结点之间的关系。 二叉树的仿真二叉链存储结构 8.3.2二叉链结构的二叉树设计 typedef struct Node \r{ DataType data; \r struct Node *leftChild; \r struct Node *rightChild;\r}BiTreeNode;\r/*初始化*/\rvoid Initiate(BiTreeNode **root)\r{ *root = (BiTreeNode *)malloc(sizeof(BiTreeNode));\r (*root)->leftChild = NULL;\r (*root)->rightChild = NULL;\r} /*左子树插入结点*/\rBiTreeNode *InsertLeftNode(BiTreeNode *curr, DataType x)\r{ BiTreeNode *s, *t;\r? if(curr == NULL) return NULL;\r t = curr->leftChild;\r s = (BiTreeNode *)malloc(sizeof(BiTreeNode));\r s->data = x;\r s->leftChild = t;\r s->rightChild = NULL;\r? curr->leftChild = s;\r return curr->leftChild; \r} /*删除左子树*/\rBiTreeNode *DeleteLeftTree(BiTreeNode *curr)\r{ \r if(curr == NULL || curr->leftChild == NULL) return NULL;\r? \r Destroy(