2.5 树与二叉树
2.5 树与二叉树
2.5.1 基本概念与定义
树是数据结构中的一种非线性表，具有很高的实用价值。学习这部分内容，首先要对树和二叉树有关的定义、术语、存储结构、基本性质等有一个基本了解。本节的重点是二叉树。有关二叉树的算法大多数采用递归调用方式，我们将首先通过遍历二叉树的算法作为二叉树其他算法的基础，并逐渐由此引出其他几种算法，找出其一般规律，使我们对递归技术有更深一步的了解，有利于提高算法设计的能力。
1.有关树的概念综述
（1）在树的定义中应体会递归定义的特点，即在定义树的时候就用了与树具有相同定义的子树。
（2）充分了解有关树的术语，如树根、树枝、树的度、层次、深度树的双亲和孩子等。
（3）由于树为非线性结构，除了特殊形式的树以外，一般采用链式存储结构，即树中每一个结点由于存放该结点元素的数据域及指向所有子树的根结点的指针域组成。
2.有关二叉树概念综述
（1）二叉树是一种特殊形式的树，同样采用递归方式来定义。应着重比较树与二叉树的异同点。
（2）熟练掌握有关二叉树的3个基本性质，这在以后的分析设计中十分有用，它们是：
①二叉树的第i层上至多2i-1个结点。
②深度为h的二叉树中至多含有2h-1个结点。
③在任意二叉树中若有n0个叶子结点，n2个度为2结点，必须满足n0= n2+1。
（3）二叉树的存储结构同样以链式存储结构为主，即每个结点由存放该结点的数据域及两个指向其左、右子树根结点的指针域组成。
（4）了解3种特殊形式的二叉树
①满二叉树
②二叉树
③平衡二叉树
（5）掌握将一般树转换成二叉树的方法 
2.5.2二叉树的遍历算法及其变化
1.二叉树的遍历算法
二叉树的遍历是为了有序地访问二叉树中每一个结点，且每一个结点仅被访问一次。二叉树的遍历算法是二叉树运算的基础。
从二叉树的定义出发，对二叉树的遍历可以由以下三部分组成：
(1)访问根结点
(2)访问左子树
(3)访问右子树
首先来分析其正确性
(1)若二叉树为空，由于不存在结点，因此不必执行访问操作。
(2)若二叉树非空，用上述方法遍历左、右子树时既不重复，也没有遗漏，再加上对根结点的访问，就构成了对二叉树所有结点的访问。
由于三部分访问的次序可以不同，因而可以有先序、中序和后序三种遍历方式。由于二叉树的左、右子树本身也是一棵二叉树，因此对左、右子树的遍历可以采用与二叉树同样的方式进行。
通过上述的分析，可以得到队二叉树遍历的递归算法，以先序遍历为例，算法为：
(1)若二叉树为空树，访问结束，即为递归出口。
(2)若二叉树非空，访问根结点、先序遍历左子树、先序遍历右子树。
访问二叉树结点的方式可以有多种，不失一般性，我们在算法中用write语句来表示遍历操作。若p 为指向二叉树根结点的指针，L、R分别为二叉树结点中指向左、右子树根结点的指针域名，data为结点的数据域名。则以p为根结点指针的二叉树（以下简称p树）先序遍历的算法为：
Preorder（p）
1. if(p≠nil) then
2. {write (data(p))
3. Preorder（L（p））
4. Preorder（R（p））
5. return
读者可以用同样方法，写出中序、后序遍历算法。
和其他递归程序一样，我们也可以用图解方式表示对一棵二叉树遍历的执行过程。
例2.18设已有二叉树如图2.21中（a）所示，其中每一个结点由指针域L、R及数据域data组成，如图2.21（b）所示，则对该二叉树进行先序遍历的执行过程及输出结果如图2.21（c）所示。
输出结果：a b d c e
2.遍历算法的几种变化
遍历算法是对每个结点进行一次访问操作，而对结点的访问可以是形式多种操作。利用这一特点，适当修改访问操作的内容便可得到求解其他问题的算法。
a) 打印二叉树中所有叶子结点的值
算法思想：本算法与遍历算法有相同之处，所不同的是只打印子结点而不是全部结点。因此只要将先序遍历算法中的访问操作（write语句）改为条件打印即可。算法如下：
PREL（p）
1. if（p≠nil）then
2. {if（L（p）=nil）and （R（p）=nil）
3. then write （data（p））
4. PREL（L（p））
5. PREL（R（p））}
6. return
（2）求二叉树中的结点数
算法思想：本算法不是要打印每个结点的值，而是要求出二叉树中结点数。可以适当修改遍历算法，将某一种遍历算法中访问结点的操作修改为计数操作。在算法设计中有可以通过不同的参量、全局变量的设置形式，形成几种不同的表达式。
①采用全局变量n（初始值为0），将二叉树中结点的数目累加到n中求得结果。算法如下：
NODE1 （p）
1. if （p≠nil）then
2． {NODE（L（p）） //左子树中结点累加到n中//
3. n←n+1 //根结点累加到n中//
4. NODE1 (R(p))} //右子树中结点累加到n中//
5. return
②设置全局变量n，将二叉树的结点数赋给全局变量。实现的过程为：
（1） 若树为空，其结点数为0，因此执行n←0。
（2） 若树不空，需分别求出根和左、右子树的结点数，合并后即得总的结点数。由于求左、右子树的结果都要送入n中，因此第2次调用将破坏第1次的结果，为此在第2次调用之前设置一个变量n
以保存第1次调用的结果。算法如下：
NODE2 （p）
1. if（p=nil）then n←0
2. else {NODE2 （L（p））
3. n
←n
4. NODE2（R（p））
5. n←n+ n
+1}
6. return
由于上述算法中是将二叉树的结点数赋给全局变量n，与NODE1算法中累加不同，因此n不必事先置为0。
③函数形式
实现过程为：
l 若树为空，其结点数为0。
l 若树不空，与遍历二叉树一样，将其分解为三部分求解，然后再合并其解。即将二叉树分解为根和左、右子树三部分，其中根结点数为1，而其左、右子树的结点数的求解，可以通过递归调用其本身来求得。算法如下：
NODE3（p）
1. if（p=nil）then n←0
2. else n←1+NODE3（L（p）+NODE3（R(p)）
3. return
(3)求二叉树中叶子结点数
算法思想：求二叉树中叶子结点数是用遍历方式计算二叉树中左、右子树都为空的结点数。若被遍历的结点只要有一个子树不为空，它本身就不是叶子结点，应继续计算该结点的左或右子树中的叶子结点数。和前面的算法类似，本算法也可以有多种形式表达。
①用全局变量n，将叶子结点数累加到变量n中，因此调用前n要清0。算法如下：
LEAF1 （p）
1. if （p≠nil）then
2. if （L（p）=nil）and （R（p）=nil）
3．then n←n+1
4. else {LEAF1 (L(p))
5. LEAF1 (R(p))}
6. return
②求二叉树的叶子结点数并送到全局变量n中。算法如下：
LEAF2 （p）
1. if （p≠nil）then n←0
2. else if （L（p）=nil）and （R（p）=nil）
3. then n←1
4. else {LEAF2（L（p））；n1←n
5. LEAF2（R（p））；n←n1+n }
6. return
由于此时为赋值操作，因此调用前不必清0。
③函数形式
l 当二叉树为空时，叶子数为0。
l 当二叉树为非空时有两种情况；
当二叉树无左、右子树时，叶子数为1。
当二叉树左、右子树中至少有一个不为空时，它本身不是叶子结点，叶子结点数算应当是它的左或右子树叶子结点数。
算法如下：
LEAF3 （p）
1. if （p≠nil）then n←0
2. else if （L（p）=nil）and （R（p）=nil）
3. then n←1
4. else n←LEAF3 （L（p）+LEAF3（R（p））
5. return（n）
通过对上述三种表达式形式的算法，希望能对递归算法设计中的基本技术有进一步的认识，即在设计的过程中，首先对设计中的命题、假设方法进行分析，以确定递归出口及相应的操作。然后对算法中的参量、全局变量、局部变量的含义进行设置，决不能模棱两可，否则会出现逻辑上的错误。
（4）求二叉树的高度
算法思想：二叉树的高度即二叉树的层次数。
l 当树为空时，高度为0。
l 当树不为空时，其高度时左、右子树高度的最大值再加1。而其左、右子树的高度的求解可以通过递归调用本算法来完成。
本算法也可以有多种表达形式，这里只用一种全局变量的表达形式，其他形式由读者作为练习完成。
HIGH1（p）
1. if（p=nil）then h←0
2. else {HIGH1 （L(p)）；h
←h
3. HIGH1 （R（p））
4. h←max（h
，h）+1}
5. return
2.5.3二叉树的应用
本结介绍的是二叉排序树和哈夫曼树，它们都是具有特殊结构形式的二叉树。关于它们的定义及相应算法在教材中已有较详细的介绍，在此主要讨论它们的一些特性及算法实现中的原理，以便在阅读算法时能起辅助作用。
1.二叉排序树
二叉排序树是按一定方式生产的二叉树，可以用来实现对一无序序列进行排序。其定义为，二叉排序树或是空树，或是具有如下性质的二叉树：左子树上所有的结点的数据值均小于根结点的数据值；右子树上所有结点的数据值均大于或等于根结点的数据值。左、右子树本身又各是一棵二叉排序树。因此是一个递归过程。
我们在上一结中介绍了二叉树的遍历算法以及由遍历算法引出的几种求解其他问题的算法，没有介绍一般二叉树的插入和删除算法。在这里要介绍这种特殊结构的二叉树的建立、插入和删除算法。
l 建立二叉排序树
根据二叉排序树的定义，建立一棵二叉排序树的过程是按照待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。若p为根结点指针，b为当前待插入元素，其过程可以描述为：
（1） 若为空树（p=nil），动态生成一个结点，其数据域为当前待插入元素b，左、右指针域为“空”，p指向该结点。
（2） 若非空树，比较b与根结点数据data（p）
如果b＜data(p), 将b插入左子树中；
如果b≥data（p），将b插入右子树中；
左、右子树的插入方式与二叉排序树的插入方式相同。
不断调用上述的插入过程，直到所有待排序序列均排入后，就形成一棵二叉排序树。
由此可见，建立二叉排序树就是多次调用二叉排序树的插入算法。
例2.19给定序列{52，8，5，16，78，19}，画出生产一棵二叉排序树的过程，见图2.22。
|
插入结点 |
比较 |
操作 |
对应 图2.22 |
|
52 |
p=nil |
52为根结点 |
(1) |
|
8 |
p1nil,8<data(p),L(p)=nil |
插入左子树L(p),8为L(p)根结点 |
(2) |
|
5 |
p1nil,5<data(p),L(p) 1nil 5<data(L(p)),LL(p)=nil |
插入左子树L(p),插入左子树LL(p),5为L(p)根结点 |
(3) |
|
16 |
p1nil,16<data(p),L(p) 1nil 16>data(L(p)),LR(p)=nil |
插入左子树L(p),插入右子树LR(p),16为L(p)根结点 |
(4) |
|
78 |
p1nil,78<data(p), R(p)=nil |
插入右子树R(p),78为L(p)根结点 |
(5) |
|
19 |
p1nil,19<data(p),L(p) 1nil 19<data(L(p)),LR(p)1nil 19>data(LR(p)),LRR(p)=nil |
插入左子树L(p),插入右子树LR(p), 插入右子树LRR(p),19为LRR(p)根结点 |
(6) |
注意：每次插入过程都是从根结点p开始比较，然后不断向下延伸。
生成二叉排序树以后，对它进行中序遍历结果就成为以有序序列，对例2.19生成的二叉排序树进行中序遍历结果为：{5，8，16，19，52，78}。
l 删除二叉排序树上的结点
删除二叉排序树上一个结点其结果不仅要求删除该结点，而且要求删除后其余的结点仍然构成一棵二叉排序树。
删除算法较建立算法复杂，分几分钟情况分别处理，为说明方便，设t为二叉排序树根结点指针，p指向被删除结点，f指向p的父结点。当被删除结点本身为根结点时，p=t，f=nil。
① 当p的左子树为空时，s←R（p），如图2.23（a）所示。
② 当p的右子树为空时，s←L（p），如图2.23（b）所示。
以上两种情况要考虑被删除结点p是否为根结点：
① 当f=nil，被删除结点是根结点
t←s，s成为新的根结点
② 当f≠nil，按①、②不同情况，把L（p）或R（p）指向f完成对p结点的删除，同时收回p结点。
③ 当p的左右子树均非空时，沿着p的左子树的根结点不断寻找右子树为空的结点s，同时q指针紧随其后，如图2.23（c）所示。
将s的左子树变为q的右子树：R（q）←L（s），将data（s）送入data（p）中：
data（p）←data（s），然后收回s结点，完成删除工作，如图2.23（d）所示。
建议大家在读懂了算法以后，一定要通过一些实例走通算法中每一条路，并通过上机试验来加深理解。
2.哈夫曼树
哈夫曼树是带权路径最短的二叉树。
带权路径 WPL=
其中:n为二叉树的叶子结点数。
W为每个叶子结点的权值。
l为每个叶子结点到根结点的路径长度（叶子结点与根结点之间的树枝数）
(1) 构造哈夫曼树
给定由n个权值组成的集合，构成n个权值为根结点的二叉树集合，从中选出两个权值最小的根结点作为左、右子树的根结点，以左、右子树根结点的权值的和作为新树根结点的权值，构成一棵新的二叉树来取代原来的两棵二叉树，形成一个新的二叉树集合。重复上述动作，直到把给定的n个权值构成一棵二叉树为止。
例2.20给定权值w={8，2，5，3，2，17，4}画出由此生成的哈夫曼树。生成过程如图2.24所示。
WPL=(2*5*2+3*4+4*3+5*3+8*3+17)=100
(2) 最佳判定算法
从哈夫曼树的生成过程中能看出，为使WPL最小，在哈夫曼树中力求使权值大的结点尽量接近根结点，而权值最小的结点远离根结点，以求得总体最优。由这个思想引发出我们在编制多分支判断程序时，当各分支的执行次数分布不均匀时，应考虑把各分支执行次数作为权值来设置各分支执行的先后次序，以便最大程度提高程序执行效率。
(3) 哈夫曼编码
哈夫曼编码是一种长度最短的二进制通信编码。它是以传输字符的权值作为叶子结点构成的一棵哈夫曼树，树中从根结点到每个叶子结点有一条路径，规定路径上指向左子树的分支为“0”码，指向右子树的分支为“1”码。取每条路径上的“0”或“1”序列作为每个叶子结点字符的编码。
例2.21 字符S、C、T、A、空格的权值为{6，2，4，5，3}以此构成的哈夫曼树如图2.25所示。
相应的字符的哈夫曼编码为：T（0 0）、A（0 1）、C（1 0 0）、空格（1 0 1）、S（1 1）。
现设有哈夫曼编码电文“1000100”出发后，在接收方进行译码时，逐个读入电文代码，从哈夫曼的根结点出发，若是“0”向左走，否则向右走，一旦达到叶子结点便译出相应的一个字符，然后重新从根结点出发继续译码，直到电文结束。上述电文译码结束为“CAT”。