平衡二叉树
（2）结点的平衡因子balance
balance＝该结点的右子树高度-该结点的左子树高度
对于AVL树：balance=1。即balance只能取-1，0，1三者之一。换言之，若一棵二叉树上任一结点的平衡因子的绝对值都不大于1，则该树是就平衡二叉树。
我们为图3-44的各结点加上平衡因子，得到图3-45。其中：图3-45c中的结点60的平衡因子为-2，故该二叉树不是平衡二叉树。
（3）平衡二叉树的高度
我们能够获得一棵n个节点的A VL树的高度的范围。假设Nh是一棵高度为h的AVL 树中最小的节点数。在最坏情况下，根节点的两个左右子树中一棵子树的高度是h-1，另一棵子树的高度是h-2，而且两棵子树都是A VL树。因此有：
树的根结点，小写字母代表子树的深度。
（5）平衡二叉树的删除
如果被删除的结点x最多只有一个孩子，那么问题比较简单，将结点x从树中删去。因为结点x最多有一个孩子，我们可以简单的把x的双亲结点中原来指向x的指针改指到这个孩子结点上。如果结点x没有孩子，即是一个叶结点，则删除x后x双亲结点的相应指针应置为NULL。如果被删结点x即有左孩子又有右孩子，则首先搜索x在中序遍历中的直接前驱y（同样可以找直接后继），把结点y的内容传送给结点x，现在问题转移到删除结点y。
【习题及解析】
【例3-37】下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。
A.二叉排序树
B.赫夫曼树
C.A VL树
D.堆
【分析】本题主要考查了选项中出现的几种树的结构特点。对于选项A，根据二叉排序树的结构特点我们可以知道，二叉排序树的中序遍历结果是一个有序序列，而在中序遍历中，父结点并不总是出现在孩子结点的前面（或后面），故该选项不正确。例如我们用关键字5,2,3建立一棵二叉排序树，则从结点3出发到根的路径上所经过的结点序列为3,2,5，并不是一个有序的序列。对于选项B，赫夫曼树在后续的章节中会介绍，根据赫夫曼树的结构特点我们可以知道，在赫夫曼树中所有的关键字只出现在叶结点上，其非叶结点上并没有关键字值，显然不正确。对于选项C，A VL树其本质上也是一种二叉排序树，只不过是平衡化之后的二叉排序树，故该选项也是不正确的。例如我们用序列5,1,8,6,9建立一棵AVL树，从结点6出发到根的路径上所经过的结点序列为6,8,5，也不是一个有序的序列。对于选项D，堆的概念我们会在堆排序中给大家介绍，根据建堆的过程，不断地把大者"上浮"，将小者"筛选"下去，最终得到的正是一个从任一结点出发到根的路径上所经过的结点序列按其关键字有序的树状结构，故D是正确的。
本题中的A和C同时出现，没有起到干扰的作用，因为A VL树和二叉排序树只是在平衡性上有区别，在结点的排列方式上没有区别。
【解答】D。
【例3-38】输入关键码序列为(16,3,7,11,9,26,18,14,15)，据此建立平衡二叉树，给出插入和调整的具体过程。
【分析】本题主要考查如何从空树通过插入结点的方法建立一棵平衡二叉树，由于插入结点而造成树的不平衡的时候，需要进行平衡化处理。
插入结点7后，结点16的平衡因子变为-2，需要对结点16,3,7进行LR型调整。插入结点11后，结点16的平衡因子变为-2，需要对结点16,11,9进行LL型调整。插入结点26后，结点7的平衡因子变为2，需要对结点7,11,16进行RR型调整。插入结点18后，结点16的平衡因子变为2，需要对结点16,26,18进行RL型调整。插入结点15后，结点16的平衡因子变为-2，需要对结点16,14,15进行LR型调整。
【解答】
【例3-39】 有一棵平衡二叉树的初始状态如图3-49a 所示，请给出删除图中结点p 后经调整得到的新的平衡二叉树。
【分析】 本题主要考查如何从一棵平衡二叉树中删除结点。由于结点p 既有左孩子，又有右孩子，故在删除结点p 的时候应该先找到中序遍历中结点p 的直接前驱结点，即结点o ，如图中b 所示。然后用o 取代p ，删除o ，如图中c 所示。此时结点o 的平衡度变为2，发生不平衡，故应对子树o,r,t 进行RR 型调整，如图中d 所示。此时，结点m 的平衡度变为-2，发生不平衡，故应对子树m,e,j 进行LR 调整，最终的调整结果如图中的e 所示。
【解答】
3.3 树、森林
3.3.1 树的存储结构
树的存储结构根据应用的不同，有多种形式。在此，我们介绍如下三种比较常用的方法。
（1）双亲表示法
在这种方法中，用一组连续的存储单元存储树中的结点，结点的形式如图3-50所示。
其中，data用于存放有关结点本身的信息，parent用于指示该结点的双亲位置。例如，图3-51a所示的树，其双亲表示法如图3-51b所示。
这种存储结构利用了每个结点(除根以外)只有唯一双亲的性质。在这种存储结构下，求结点的双亲十分方便，也很容易求树的根。但是在这种表示法中，在求结点的孩子时需要遍历整个存储空间。
（2）孩子表示法
由于树中每个结点可能有多个孩子，所以自然想到用多重链表存储树。在这种多重链表的每个结点中除了用于存放数据信息的data域外，还有若干指针域，分别用于指向该结点的孩子结点。但是一棵树中，不同结点的度数是不同的，那么每个结点中到底需要多少个指针域呢？我们有如下二种方案：
①定长结点的多重链表
在这种方法中，我们取树的度数作为每个结点的指针域数目。不难推导，一棵具有n 个结点的度为K的树中必有n(k-1)+1个空指针。显然，这会造成存储空间的极大浪费。例如，图3-51a所示的树，其定长结点的多重链表如图3-52a所示。
②不定长结点的多重链表
在定长结点的多重链表中，由于各结点指针的数目是根据树的度而定，所以造成了存储空间的浪费。下面我们考虑每个结点的指针域数目取它自己的度数。另外，在每个结点中设置一个度数域(degree)，以指出该结点的度数，其表示方法如图3.52b所示。显然这种方法
的存储密度较前者有所提高，但由于各结点的结构不同，自然会造成操作上的不方便。
（3）孩子-兄弟表示法
这种方法又称二叉树表示法（或二叉链表表示法）。在这种二叉链表的每个结点中除了用于存放数据信息的data域外，还有两个指针域fch和nsib，分别用于指向该结点的第一个
孩子结点和它的下一个兄弟结点。图3-53为图3-51a所示的树的孩子-兄弟链表。在这种存储结构中，树的操作比较方便，且存储密度较高。
不难发现它与一棵二叉树十分相似。二叉树结构规范、简单并具有一些重要性质，因此常将一般树结构转换为二叉树结构进行处理。
注意：这种存储结构的最大优点是它和二叉树的二叉链表表示完全一样。可利用二叉树的算法来实现对树的操作。
下面图3-54a所示的树可转换为图3-54d所示的二叉树。
注意：由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。
2)将一个森林转换为二叉树
森林是树的有限集合，如图3-55a所示。由上节可知，一棵树可以转换为二叉树（没有右子树），一个森林就可以转换为二叉树（没有右子树）的森林。将森林转换为二叉树的一般步骤为：
①将森林中每棵子树转换成相应的二叉树。形成有若干二叉树的森林，如图3-55b所示。
②按森林图形中树的先后次序，依次将后边一棵二叉树作为前边一棵二叉树根结点的右子树，这样整个森林就生成了一棵二叉树，实际上第一棵树的根结点便是生成后的二叉树的根结点。图3-55是将一个森林转化为一棵二叉树的示例。图3-55d是转化后的一棵二叉树。
下图中，图a包含三棵树的森林可转换为图d的二叉树。
（2）二叉树到树、森林的转换
1)二叉树转换为一般树
此时的二叉树必须是由某一树（一般树）转换而来的没有右子树的二叉树。并非随便一棵二叉树都能还原成一般树。
其还原过程也分为三步：
①加线：若某结点i 是双亲结点的左孩子，则将该结点i 的右孩子以及当且仅当连续地沿着右孩子的右链不断搜索到所有右孩子，都分别与结点i 的双亲结点用虚线连接。
②抹线：把原二叉树中所有双亲结点与其右孩子的连线抹去。这里的右孩子实质上是原一般树中结点的兄弟，抹去的连线是兄弟间的关系。
③进行整理：把虚线改为实线，把结点按层次排列。
下图把二叉树还原为一般树：
2)二叉树转换为森林
将一棵二叉树转化成森林，可按如下步骤进行：
①抹线：将二叉树根结点与其右孩子之间的连线，以及沿着此右孩子的右链连续不继搜索到的右孩子间的连线抹掉。这样就得到了若干棵根结点没有右子树的二叉树。
②将得到的这些二叉树用前述方法分别转化成一般树。
3.3.3 树和森林的遍历
(1)树的遍历
1)先序（先根）遍历树
先访问树的根结点，然后依次先序遍历根的每棵子树。例如，对图3-54a所示的树，其先序遍历所得的先序序列为：A、B、E、C、F、H、G、D。
2)后序（后根）遍历树
先依次后序遍历根的每棵子树，然后再访问根结点。例如，对图3-54a所示的树，其后序遍历所得的后序序列为：E、B、H、F、G、C、D、A。
从前面树与二叉树之间的转换关系可以得到：树的先序遍历和后序遍历可分别借助于对应二叉树的先序遍历和中序遍历完成。
(2)森林的遍历
1)先序遍历森林
若森林非空，则可按如下步骤遍历森林：
①访问森林中第一棵树的根结点；
②先序遍历第一棵树中根的子树森林；
③先序遍历除第一棵树以外的其余树组成的森林。
2)后序遍历森林
若森林非空，则可按如下步骤遍历森林：
①后序遍历森林中第一棵树的根结点的子树森林；
②访问第一棵树的根结点；
③后序遍历除去第一棵树之后剩余的树构成的森林。
例如，对图3-55a所示的森林进行先序遍历和中序遍历，可得到森林的先序序列为：A、B、C、D、E、F、G、H、I、J；中序序列为：B、C、D、A、F、E、H、J、I、G。
当用二叉链表作树和森林的存储结构时，树和森林的前序遍历和后序遍历，可用二叉树的前序遍历和中序遍历算法来实现。
【习题及解析】
【例3-40】树的基本遍历策略可分为先序遍历和后序遍历。二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。则以下结论中正确的是：
A.树的先序遍历序列与其对应的二叉树的先序遍历序列相同
B.树的后序遍历序列与其对应的二叉树的后序遍历序列相同
C.树的先序遍历序列与其对应的二叉树的中序遍历序列相同
D.以上都不对
【分析】本题主要考查知识点二叉树与树的转换。我们知道，树和森林的前序遍历和后序遍历，可用对应二叉树的前序遍历和中序遍历来实现。故选项中的B、C、D都不正确。
【解答】A。
【例3-41】设树T采用孩子-兄弟链表存储结构，设计算法输出一棵树T的各边。
【分析】本题主要考查如何遍历采用孩子-兄弟链表形式存储的树。根据前面的知识我们知道，在孩子-兄弟链表存储结构中，每一个结点N分别与一个单链表中的所有结点之间存在一条边，而该单链表是以结点N的fch域指向的结点为首、靠nsib域链接起来的一个单链表。我们以图3-53中所示的树为例，结点A与单链表BCD中的每一个结点之间都存在一条边，结点B与单链表EF中的每一个结点之间都存在一条边，结点D与单链表GHI 中的每一个结点之间都存在一条边，结点F与单链表J（只有一个结点的单链表）中的每一个结点之间都存在一条边。由此我们可以得到如下的递归算法：
【解答】算法如下：
1.void Print_CSTree(CSTree T)∥输出孩子兄弟链表表示的树T的各边
2.{
3.for(child=T->fch;child;child=child->nsib)
4. {
5. printf("(%c,%c),",T->data,child->data);
6. Print_CSTree(child);
7. }
8.}∥Print_CSTree
将该算法作用于图3-53中所示的树，将得到结果（如图3-57所示）：
(A,B),(B,E),(B,F),(F,J),(A,C),(A,D),(D,G),(D,H),(D,I)
【例3-42】设树T采用孩子-兄弟链表存储结构，设计算法求树T的叶子数目。
【分析】本题主要考查如何遍历采用孩子-兄弟链表形式存储的树。根据前面的知识我们知道，在孩子-兄弟链表存储结构中，叶结点是那些fch域为NULL的结点。我们还是利用上题中的方法来遍历一棵树，每当遇到一个fch域为NULL的结点时，我们返回一个1。如果当前结点的fch域不为NULL，说明该结点为非叶结点，递归的去遍历它的孩子。
由此我们得到如下的递归算法：
【解答】算法如下：
1.int LeafCount_CSTree(CSTree T)
2.∥求孩子兄弟链表表示的树T的叶子数目
3.{
4.if(!T->fch)return 1;∥叶子结点
5.else
6. {
7. count=0;
8.for(child=T->fch;child;child=child->nsib)
9. count+=LeafCount_CSTree(child);
10.return count;∥各子树的叶子数之和
11. }
12.}∥LeafCount_CSTree
将该算法作用于图3-53中所示的树，返回结果为6。
类似的题目还有求孩子-兄弟链表表示的树T的度及深度等。
【例3-43】设树T采用孩子-兄弟链表存储结构，设计算法求树T的度。【解答】算法如下：
1.int GetDegree_CSTree(CSTree T)∥求孩子兄弟链表表示的树T的度
2.{
3.if(!T->fch)return 0;∥空树
4.else
5. {
6. degree=0;
7.for(p=T->fch;p;p=p->nsib)degree++;∥本结点的度
8.for(p=T->fch;p;p=p->nsib)
9. {
10. d=GetDegree_CSTree(p);
11.if(d>degree)degree=d;∥孩子结点的度的最大值
12. }
13.return degree;
14. }∥else
15.}∥GetDegree_CSTree
【例3-44】设树T采用孩子-兄弟链表存储结构，设计算法求树T的深度。【解答】算法如下：
1.int GetDepth_CSTree(CSTree T)∥求孩子兄弟链表表示的树T的深度
2.{
3.if(!T)return 0;∥空树
4.else
5. {
6.for(maxd=0,p=T->fch;p;p=p->nsib)
7.if((d=GetDepth_CSTree(p))>maxd)maxd=d;∥子树的最大深度
8.return maxd+1;
9. }
10.}∥GetDepth_CSTree
【例3-45】假设一棵树的存储结构采用双亲表示法，双亲指针数组为int parent ［MaxSize］，其中MaxSize表示双亲指针数组的最大结点个数。树中各个结点按先根遍历次序存放，根结点存于parent［0］。试编写一个函数，计算p所指结点和q所指结点的最近公共祖先结点。
【分析】这是一个二重循环。外层循环从结点p向双亲方向循环，每变动一个结点，即对从结点q到根的路径上各结点进行检测，遇到外层循环当前标定的结点即终止。此结点即为所求的p所指结点和q所指结点的最近公共祖先结点。
【解答】算法如下：
1.int CommonAncestry(int parent［］,int MaxSize,int p,int q){
2.int i,j;
3.for(i=p;i !=-1;i=parent［i］)
4.for(j=q;j !=-1;j=parent［j］)
5.if(i==j)return i;
6.}