第5章树的概念与操作

本章学习要点
（1） 熟悉树和二叉树的递归定义、有关的术语及基本概念。
（2） 熟练掌握二叉树的性质，了解相应的证明方法。
（3） 熟练掌握二叉树的两种存储方法、特点及适用范围。
（4） 遍历二叉树是二叉树的各种运算的基础，因此，不仅要熟练掌握各种次序的遍历算法，而且还要能灵活运用遍历算法，实现二叉树的其他各种运算。
（5） 了解二叉树的线索化及其实质，是建立结点及其在相应次序(先根、中根或后根)下的前驱和后继之间的直接联系，目的是加速遍历过程，迅速查找给定结点在指定次序下的前驱和后继。
（6） 熟练掌握树、森林与二叉树之间的转换方法。
（7） 了解最优二叉树的特性，掌握建立最优二叉树和哈夫曼编码的方法。

线性结构用于描述数据元素间的线性关系，然而实际应用中数据元素之间的关系错综复杂，很难完全用线性关系来描述。从本章开始将讨论非线性的数据结构。树是一种典型的非线性的数据结构，它描述了客观世界中事物之间的层次关系，这种结构有着广泛的应用，一切具有层次关系的问题都可以用树来描述。例如： 家族的家谱、各种社会机构的组织都呈现出树形的层次结构； 在操作系统的文件系统中，用树来表示目录结构； 在编译程序中，用树来表示源程序的语法结构等。

5.1树的概念与操作

5.1.1树的概念
1. 树(tree)的定义


首先，可以注意到，自然界中的树有树根、树枝(不妨称为子树)和树叶，由此可以给出以下关于树的定义。
定义5.1树是由n(n≥0)个结点组成的有限集合，当n＝0时称为空树； 否则，在任一非空树中： 
(1) 必有一个特定的称为根的结点； 
(2) 剩下的结点被分成m≥0个互不相交的集合T1，T2，…，Tm，而且这些集合中的每一个又都是树。树T1，T2，…，Tm被称作根的子树。

显然，这是一个递归的定义，因为它用树自身来定义树。树的定义显示了树的固有特性： 树中的每一个结点都是该树中的某一棵子树的根。在定义中，特别强调子树的互不相交特性，即每个结点只属于一棵树(或子树)，只有一个双亲。图5.1(a)表示只有一个结点的树，图5.1(b)是一般的树，有13个结点。树还可有其他的表示形式，图5.2所示为图5.1(b)中树的各类表示，其中图5.2(a)是以嵌套集合的形式表示的(即是一些集合的集合； 对于其中任意两个集合，或者不相交，或者一个包含另一个)； 图5.2(b)是以广义表的形式表示的； 图5.2(c)用的是凹入表示法(类似书的编目)。一般来说，分等级的分类方案都可用层次结构来表示，也就是说，都可表示为一个树结构。






图5.1树的示例




图5.2树的其他3种表示法


2. 树的基本术语
下面给出树结构中的一些基本术语。
树包含若干个结点以及若干指向其子树的分支。
结点拥有的子树数称为结点的度(degree)。例如在图5.1(b)中A的度为3，C的度为1，F的度为0。
度为0的结点称为叶子(leaf)或终端结点。图5.1(b)中的结点K、L、F、G、M、I、J都是树的叶子。度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。
树的度是树中各结点的度的最大值。如图5.1(b)中树的度为3。结点的子树的根称为该结点的孩子(child)，相应地，该结点称为孩子的双亲(parent)。例如，在图5.1(b)所示的树中，D为A的子树的根，则D是A的孩子，而A则是D的双亲。
同一个双亲的孩子之间互称兄弟(sibling)。例如，在图5.1(b)所示的树中，H、I和J互为兄弟。
将这些关系进一步推广，可认为D是M的祖父。结点的祖先是从根到该结点所经分支上的所有结点，例如M的祖先为A、D、H。反之，以某结点为根的子树中的任一结点都称为该结点的子孙，如B的子孙为E、K、L和F。
结点的层次(level)从根开始定义起，根为第1层，根的孩子为第2层。若某结点在第C层，则其子树的根就在第C+1层。
其双亲在同一层的结点互称为堂兄弟。例如，结点G与E、F、H、I、J互为堂兄弟。
树中结点的最大层次称为树的深度(depth)或高度。图5.1(b)所示的树的深度为4。
如果将树中结点的各子树看成从左至右是有次序的(即不能互换)，则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的子树的根称为最后一个孩子。
森林(forest)是m(m≥0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。
5.1.2树的基本操作
树的基本操作有下列几种。
(1) 初始化操作： INITATE(T)，置T为空树。
(2) 求根函数： ROOT(T)或ROOT(x)，求树T的根或求结点x所在的树的根结点。若T是空或x不在任何一棵树上，则函数值为“空”。
(3) 求双亲函数： PARENT(T，x)，求树T中结点x的双亲结点，若结点x是树T的根结点或结点x不在树T中，则函数值为“空”。
(4) 求孩子结点函数： CHILD(T，x，i)，求树T中结点x的第i个孩子结点，若结点x是树T的叶子或无第i个孩子或结点x不在树T中，则函数值为“空”。
(5) 求右兄弟函数： RIGHT_SIBLING(T，x)，求树T中结点x右边的兄弟，若结点x是其双亲的最右边的孩子结点或结点x不在树T中，则函数值为“空”。
(6) 建树函数： CRT_TREE(x，F)，生成一棵以x结点为根，以森林F为子树森林的树。
(7) 插入子树操作： INS_CHILD(y，i，x)，置以结点x为根的树是结点y的第i棵子树，若原树中无结点y或结点y的子树个数小于i-1，则为空操作。
(8) 删除子树操作： DEL_CHILD(x，y)，删除结点x的第i棵子树，若无结点x或结点x的子树个数小于i，则为空操作。
(9) 遍历操作： TRAVERSE(T)，按某个次序依次访问树中各个结点，并使每个结点只被访问一次。
(10) 清除结构操作CLEAR(T)，将树T置为空树。


5.2二叉树

树形结构和自然界的树一样具有各种各样的形态，这增加了研究树形结构的问题的复杂性。为此，首先定义并研究规范化的二叉树，讨论二叉树的性质、存储结构和运算，然后给出二叉树与一般树之间的转换规则，这样就解决了树的存储结构及其运算复杂性的问题。
5.2.1二叉树的概念
1. 二叉树(binary tree)的定义

定义5.2二叉树是结点的有限集合，这个集合或者是空的，或者由一个根结点或两棵互不相交的称为左子树的和右子树的二叉树组成。
这个递归定义表明二叉树或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的互不相交的二叉树组成。由于这两棵子树也是二叉树，则由二叉树的定义，它们也可以是空树。由此，二叉树可以有五种基本形态，如图5.3所示。


图5.3二叉树的五种基本形态


二叉树的特点是： 树中的每个结点最多只能有两棵子树，即树中任何结点的度数不大于2； 二叉树的子树有左、右之分，而且，子树的左、右次序是重要的，即使在只有一棵子树的情况下，也应分清是左子树还是右子树。
前面引入的有关树的术语也都适用于二叉树。
为了说明二叉树的性质，下面先给出满二叉树和完全二叉树的定义。
定义5.3一棵深度为k的满二叉树，是有2k-1个结点的深度为k的二叉树。
2k-1个结点是二叉树所具有的最大结点个数。例如，图5.4所示为一棵深度为4的满二叉树。为便于访问满二叉树的结点，对满二叉树从第1层的结点(即根)开始，自上而下，从左到右，按顺序给结点编号，便得到满二叉树的一个顺序表。
定义5.4一棵具有n个结点，深度为k的二叉树，当且仅当其所有结点对应于深度为k的满二叉树中编号由1~n的那些结点时，该二叉树便是完全二叉树。
若用一个一维数组tree来表示完全二叉树，则其编号为i的结点对应于数组元素tree［i］。图5.5所示为一棵完全二叉树。



图5.4满二叉树




图5.5完全二叉树



2. 二叉树的基本操作
与树的基本操作相类似，二叉树有如下一些基本操作。
(1) 初始化操作： INITATE(BT)，置BT为空树。
(2) 求根函数： ROOT(BT)或ROOT(x)，求二叉树BT的根结点或求结点x所在二叉树的根结点，若BT是空树或x不在任何二叉树上，则函数值为“空”。
(3) 求双亲函数： PARENT(BT，x)，求二叉树BT中结点x的双亲结点，若结点x是二叉树BT的根结点或二叉树BT中无x结点，则函数值为“空”。
(4) 求孩子结点函数： LCHILD(BT，x)和RCHILD(BT，x)，分别求二叉树BT中结点x的左孩子和右孩子结点，若结点x为叶子结点或不在二叉树BT中，则函数值为“空”。
(5) 求兄弟函数： LSIBLING(BT，x)和RSIBLING(BT，x)，分别求二叉树BT中结点x的左兄弟和右兄弟结点； 若结点x是根结点，或不在BT中，或是其双亲的左/右子树根，则函数值为“空”。
(6) 建树操作： CRT_BT(x，LBT，RBT)，生成一棵以结点x为根，以二叉树LBT和RBT为左、右子树的二叉树。
(7) 插入子树操作： INS_LCHILD(BT，y，x)和INS_RCHILD(BT，y，x)，将以结点x为根且右子树为空的二叉树分别置为二叉树BT中结点y的左子树和右子树，若结点y有左子树/右子树，则插入后y的左子树/右子树成为结点x的左子树/右子树。
(8) 删除子树操作： DEL_LCHILD(BT，x)和DEL_RCHILD(BT，x)，分别删除二叉树BT中以结点x为根的左子树或右子树，若x无左子树或右子树，则为空操作。
(9) 遍历操作： TRAVERSE(BT)，按某个次序依次访问二叉树中各个结点，并使每个结点只被访问一次。
(10) 清除结构操作： CLEAR(BT)，将二叉树BT置为空树。
在已知二叉树的逻辑结构和运算后就可以定义二叉树的抽象数据类型。ADT5.1是二叉树的抽象数据类型描述，其中只包含最常见的二叉树运算。
ADT5.1二叉树ADT
ADT BTree{
数据对象： 

D={ai|ai∈元素集合，i=1，2，…，n，n≥0}
数据关系R： 
若D=，则R=，称BTree为空二叉树。
若D≠，则R={H}，H是如下二元关系。
(1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱。
(2) 若D-{root}≠，则存在D-{root}={Dl，Dr}，且Dl∩Dr=。
(3) 若Dl≠，则Dl中存在唯一的元素xl，〈root，xl〉∈H，且存在Dl上的关系HlH； 若Dr≠，则Dr中存在唯一的元素xr，〈root，xr〉∈H，且存在Dr上的关系HrH； H={〈root，xl〉，〈root，xr〉，Hl，Hr}。 
(4) (Dl，{Hl})是一棵符合本定义的二叉树，称为根的左子树。(Dr，{Hr})是一棵符合本定义的二叉树，称为根的右子树。

基本操作： 
creat()： 创建一个空二叉树。
destroy()： 撤销一个二叉树。
isempty()： 若二叉树空，则返回1； 否则返回0。
clear()： 移去所有结点，成为空二叉树。
root(x)： 若二叉树非空，则x为根的值，并返回1，否则返回0。
maketree(x，left，right)： 构造一棵二叉树，根的值为x，以left和right为左、右子树。
breaktree(x，left，right)： 拆分二叉树为三部分，x为根的值，以left和right分别为原树的左右子树。
preorder(visit)： 使用函数visit()访问结点，先根遍历二叉树。
inorder(visit)： 使用函数visit()访问结点，中根遍历二叉树。
postorder(visit)： 使用函数visit()访问结点，后根遍历二叉树。
}ADT BTree
5.2.2二叉树的性质
二叉树具有下列重要性质。

性质5.1在二叉树的第i层上至多有2i-1个结点(i≥1)。
利用归纳法容易证得此性质。
当i=1时，只有一个根结点。显然，2i-1＝20＝１是对的。
现假设对所有的j，1≤j<i，命题成立，即第j层上至多有2j-1个结点。那么可以证明j=i时命题成立。
由此归纳假设： 第i-1层上至多有2i-2个结点。由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2*2i-2＝2i-1。
性质5.2深度为k(k≥1)的二叉树至多有2k-1个结点。
由性质5.1可见，深度为k的二叉树的最大结点数为
∑ki=1(第i层上的最大结点数)=∑ki=12i-1=2k-1
性质5.3对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
设n1为二叉树T中度为1的结点数。因为二叉树中所有结点的度均小于或等于2，所以其结点总数为
n=n0+n1+n2(5.1)
再看二叉树中的分支数。除根结点外，其余结点都有一个分支进入，设B为分支数，则n=B＋1。由于这些分支是由度为1或2的结点引出的，所以又有B=n1+2n2。于是得
n=n1+2n2+1(5.2)
由式(5.1)和式(5.2)可得
n0=n2+1
性质5.4具有n个结点的完全二叉树的深度为log2n+1。
证明： 假设深度为k，则根据性质5.2和完全二叉树的定义有
2k-1-1<n≤2k-1
或
2k-1≤n<2k
于是
k-1≤lbn<k
因为k是整数，所以
k=lbn+1
性质5.5如果对一棵有n个结点的完全二叉树(其深度为lbn+1)的结点按层序号编号(从第1层到lbn+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有
(1) 如果i=1，则结点i是二叉树的根，无双亲； 如果i>1，则双亲是结点i/2。
(2) 如果2i>n，则结点i无左孩子(结点i为叶子结点)； 否则其左孩子是结点2i。
(3) 如果2i+1>n，则结点i无右孩子； 否则其右孩子是结点2i+1。
只要先证明(2)和(3)，便可从(2)和(3)导出(1)。
对于i=1，由完全二叉树的定义，其左孩子是结点2，若2>n，即不存在结点，此时，结点i无左孩子。结点1的右孩子也只能是结点3，若结点3不存在，即3>n，此时，结点i无右孩子。
对于i>1，可分两种情况讨论。
(1) 设第j(1≤j≤lbn)层的第一个结点的编号为i(由二叉树的定义和性质5.2可知i＝2i-1)，则左孩子必为第j+1层的第一个结点，其编号为2j＝2(2j-1)＝2i，若2i>n，则无左孩子； 其右孩子必为第j+1层的第二个结点，其编号为2i+1，若2i+1>n，则无右孩子。
(2) 假设第j(1≤j≤lbn)层上某个结点的编号为i(2j-1≤i<2j－1)，且2i+1<n，则左孩子为2i，右孩子为2i+1。又编号为i+1的结点是编号为i的结点的右兄弟或者堂兄弟，若它有左孩子，则编号必为2i+2=2(i+1)，若它有右孩子，则编号必为2i+3=2(i+1)+1。
图5.6所示为完全二叉树中结点及其左、右孩子结点间的关系。


图5.6完全二叉树中结点及其左、右孩子结点间的关系


5.2.3二叉树的存储结构及其实现
1. 顺序存储结构

用一组连续的存储单元存储二叉树的数据元素，将二叉树中编号为i的结点的数据元素存放在分量tree［i-1］中，如图5.7所示。对于图5.5中的完全二叉树，可以用向量(一维数组)tree［0..11］作为它的相应存储结构； 对于如图5.8所示的一般二叉树，其顺序存储结构如图5.9所示。











123456789101112


图5.7完全二叉树的顺序存储结构




图5.8一般二叉树








12345000067


图5.9一般二叉树的顺序存储结构



根据完全二叉树的特性，结点在向量中的相对位置蕴含着结点间的关系，如tree［i］的双亲为tree［(i+1)/2-1］，而其左、右孩子则分别为tree［2i］和tree［2i+1］中。显然，这种顺序存储结构仅适于完全二叉树，因为在顺序存储结构中，仅以结点在向量中的相对位置表示结点之间的关系，因此，一般的二叉树也必须应按完全二叉树的形式来存储，这就有可能造成存储空间的浪费。如图5.8所示的一般二叉树，其存储结构如图5.9所示，图中“0”表示不存在此结点。在最坏的情况下，一个深度为k且只有k个结点的单支树(树中无度为2的结点)却需2k-1个存储分量。
2. 链式存储结构

由二叉树的定义可知，二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成，如图5.10(a)所示。也就是说，二叉树的链表中的结点


图5.10二叉树的结点及其存储结构



至少包含三个域： 数据域和左、右指针域，如图5.10(b)所示。但是，设计不同的结点结构可构成不同形式的链式存储结构。有时，为了便于找到结点的双亲，还可以在结构中增加一个指向其双亲结点的指针域，如图5.10(c)所示。利用这两种结点结构所得二叉树的存储结构分别称为二叉链表和三叉链表,如图5.11所示。链表的头指针指向二叉树的根结点。
在不同的存储结构中实现二叉树的操作方法也不同，如查找结点x的双亲parent(tree，x)，在三叉链表中很容易实现，而在二叉链表中则需从根结点出发巡查。由此，在具体应用中采用什么存储结构，除考虑二叉树的形态之外还应考虑需要进行何种操作。


图5.11二叉树的链式存储结构



5.3二叉树的遍历

5.3.1递归的遍历算法
遍历(traversal)是树的一种最基本的运算。所谓遍历二叉树，就是按一定的规则和次序走遍二叉树的所有结点，使得每个结点都被访问一次，而且只被访问一次。遍历二叉树的目的在于得到二叉树中各结点的一种线性序列，使非线性的二叉树线性化，从而简化有关的运算和处理。对于线性结构，遍历的问题十分简单，因其结构本身就是线性的。但二叉树是非线性的，要得到树中各结点的一种线性序列就不那么容易。因为从二叉树的任意结点出发，既可向左走，也可向右走，存在两种可能。所以，必须为遍历确定一个完整而有规则的走法，以便按同样的方法处理每个结点及其子树。
二叉树的基本结构形态如图5.3所示，如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，并遵循先左后右的规则，那么，遍历二叉树可以有三种不同的走法： DLR、LDR、LRD。分别称为先根遍历、中根遍历、后根遍历。三种走法的定义如下。
1. 先根遍历(DLR)
若二叉树为空，则返回，否则依次执行以下操作： 
访问根结点； 
按先根遍历左子树； 
按先根遍历右子树； 
返回。
2. 中根遍历(LDR)
若二叉树为空，则返回，否则依次执行以下操作： 
按中根遍历左子树； 
访问根结点； 
按中根遍历右子树； 
返回。
3. 后根遍历(LRD)
若二叉树为空，则返回，否则依次执行以下操作： 
按后根遍历左子树； 
按后根遍历右子树； 
访问根结点； 
返回。
根据上述描述，对于图5.5所示的二叉树： 
按先根遍历，得到的结点序列是1，2，4，8，9，5，10，11，3，6，12，7； 
按中根遍历，得到的结点序列是8，4，9，2，10，5，11，1，12，6，3，7； 
按后根遍历，得到的结点序列是8，9，4，10，11，5，2，12，6，7，3，1。
对于图5.4所示的二叉树： 
按先根遍历得到的结点序列是1，2，4，8，9，5，10，11，3，6，12，13，7，14，15； 
按中根遍历得到的结点序列是8，4，9，2，10，5，11，1，12，6，13，3，14，7，15； 
按后根遍历得到的结点序列是8，9，4，10，11，5，2，12，13，6，14，15，7，3，1。
显然，先根遍历、中根遍历和后根遍历这些术语本身，就反映着根结点相对于其子树的位置关系。
遍历算法的语言描述形式随存储结构的不同而不同。若定义二叉树的存储结构为如下说明的二叉链表： 

typedef int datatype;

struct bnodept

{

datatype data;

struct bnodept *lchild，*rchild;

};

typedef  struct bnodept *bitreptr;

则三种遍历的递归算法如下。
算法5.1二叉树的先根遍历递归算法。

//按先根遍历二叉树t，t的每个根结点有三个域:lchild，data，rchild 

void  preorder(bitreptr t)

{ 

if(t) //为非空二叉树 

{

visit(t->data);  //访问根结点 

preorder(t->lchild); //先根遍历左子树 

preorder(t->rchild); //先根遍历右子树 

}

}

算法5.2二叉树的中根遍历递归算法。

//按中根遍历二叉树t，t的每个结点有三个域:lchild，data，rchild 

void inorder(bitreptr t)

{

if(t)

{

inorder(t->lchild); 

visit(t->data);

inorder(t->rchild);

}

}

算法5.3二叉树的后根遍历递归算法。

//按后根遍历二叉树t，t的每个结点有三个域:lchild，data，rchild 

void  postorder(bitreptr t)

{

if(t)

{

postorder(t->lchild);

postorder(t->rchild);

visit(t->data);

}

}



图5.12表达式(a+b*(c-d)-e/f)
的二叉树



例如，图5.12所示的二叉树表示下述表达式
a+b*(c-d)-e/f
若先根遍历图5.12所示的二叉树，按访问结点的先后次序将结点排列起来，可得二叉树的先根序列为： 
- +a*b-cd/ef(5.3)
类似地，中根遍历图5.12所示的二叉树，可得此二叉树的中根序列为： 
a+b*c-d-e/f(5.4)
后根遍历图5.12所示的二叉树的序列为： 
abcd-*+ef/-(5.5)
从表达式来看，以上三个序列恰好为表达式的前缀表示(波兰式)、中缀表示和后缀表示(逆波兰式)。
从上述二叉树遍历的定义可知，三种遍历算法的不同之处仅在于访问根结点和遍历左、右子树的先后次序不同。如果在算法中暂且抹去与递归无关的visit语句，则三个遍历算法完全相同。因此，从递归执行的过程角度来看，先根、中根和后根遍历也是完全相同的。图5.13(b)中用带箭头的虚线表示了这三种遍历算法的递归执行过程。其中向下的箭头表示更深一层的递归调用，向上的箭头表示从递归调用退出返回，虚线旁的字符表示了中根遍历二叉树过程中访问结点时输出的信息。由于中根遍历中访问根结点是在遍历左子树之后、遍历右子树之前进行的，则带圆形的字符标在向左递归返回和向右调用之间。由此，只要沿虚线从1出发到2结束，将沿途所见的圆形内的字符记下，便得到二叉树的中根序列，例如，从图5.13(b)可得图5.13(a)所示表达式的中根序列为： a*b-c。


图5.13三种遍历过程示意图


执行一个递归程序，需要借助栈的作用，因此可以直接使用栈，把上面的递归算法改写成一个等价的非递归算法。
在遍历二叉树的过程中，通过根结点可以立刻找到它的左孩子(即左子树的根结点)和右孩子(即右子树的根结点)，但不能直接从左孩子或右孩子到达它的双亲，除非重新从二叉树的根开始扫描。对于前根遍历二叉树而言，在访问根结点之后，可以直接到达左子树进行遍历； 在左子树遍历完毕之后，还必须设法从左子树返回到根结点，再到达它的右子树进行遍历。因此，在从根结点走向左子树之前，必须将根结点的指针送入一个栈中暂存起来。这样，在左子树遍历完毕之后，再从栈中取回根结点的指针，便得到了根结点的地址，再走向右子树进行遍历。
算法5.4前根遍历二叉树的非递归算法。

void  preorder(bitreptr t)

{

bitreptr stack［MAX+1］; //顺序栈 

int top=0; //栈顶指针 

do 

{

while(t)

{

visit(t->data); //访问根结点 

if(top==MAX) //栈已满 

{

printf("stack full");

return;  //不能再遍历下去 

}

stack［++top］=t; //根指针进栈 

t=t->lchild;  //移向左子树 

}

if(top!=0)  //栈中还有根指针 

{

t=stack［top--］;  //取出根指针 

t=t->rchild;  //移向右子树 

}

}while(top!=0||t!=NULL); //栈非空或为非空子树 

}

对二叉树进行遍历的搜索路径除了按先根、中根或后根外，还可以从上到下、从左到右按层次进行。

显然，遍历二叉树的算法中的基本操作是访问根结点，无论按哪一种次序进行遍历，对含n个结点的二叉树，其时间复杂度均为O(n)。所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n，则空间复杂度也为O(n)。遍历时也可采用二叉树的其他存储结构，如带标志域的三叉链表，此时因存储结构中已存储遍历所需的足够信息，则遍历过程中不需另设栈。另外，采用带标志域的二叉链表做存储结构，并在遍历过程中利用指针域暂存遍历路径，也可省略栈的空间，但这样做将使时间上有很大损失。

5.3.2二叉树遍历操作应用举例
遍历是二叉树各种操作的基础，可以在遍历过程中对结点进行各种操作，如对于一棵已知二叉树可求结点的双亲、求结点的孩子结点、判定结点所在层次等，反之，也可以在遍历过程中生成结点，建立二叉树的存储结构。
(1) 求二叉树中以值为x的结点为根的子树的深度。
算法5.5求二叉树中值为x的结点为根的子树的深度算法。

//求子树深度的递归算法

int Get_Depth(bitreptr T) 

{

int m，n;

if(!T) return 0;//递归函数有返回值时注意对每个分支赋值

else

{

m=Get_Depth(T->lchild);

n=Get_Depth(T->rchild);

return (m>n?m:n)+1;

}

}

//求二叉树中以值为x的结点为根的子树深度 

void Get_Sub_Depth(bitreptr T， datatype x)

{

if(T->data==x)

{

printf("%d＼n"，Get_Depth(T)); //找到了值为x的结点，求其深度 

exit(1);

}

else

{

if(T->lchild) 

Get_Sub_Depth(T->lchild，x);

if(T->rchild) 

Get_Sub_Depth(T->rchild，x); //在左、右子树中继续寻找 

}

}

(2) 在二叉树中求指定结点的层数。
算法5.6在二叉树中求指定结点的层数算法。

//在二叉树root中求值为ch的结点所在的层数 

int preorder(bitreptr root，datatype ch)

{

int lev，m，n;

if(root==NULL)

lev=0;//空树 

else if (root->data==ch) 

lev=1;//ch所在结点为根结点 

else

{

m=preorder(root->lchild，ch); //在左子树中查找ch所在结点 

n=preorder(root->rchild，ch); //在右子树中查找ch所在结点 

if (m==0&&n==0) lev=0;  //在左、右子树中查找失败 

else lev=((m>n)?m:n)+1; //在左子树或右子树中查找成功时，层数加1 

}

return(lev);

 }

(3) 按先根序列建立二叉树的二叉链表。

对图5.11(b)所示的二叉树，按下列次序顺序读入字符，其中#作为结束标志。
A B C # # D E  #  G  #  #  F  #  #  # 
算法5.7按先根序列建立二叉树的二叉链表算法。

//按先根序列建立二叉树的二叉链表。函数的返回值指向根结点 

bitreptr crt_bt_pre() 

{

char ch;

bitreptr bt;

ch=getchar();//从键盘上输入一个字符

if (ch=='#') return(NULL);//#作为结束标志

else

{

bt=(bitreptr)malloc(sizeof(struct bnodept));//产生新结点 

bt->data=ch;

bt->lchild= crt_bt_pre();

bt->rchild= crt_bt_pre();

return (bt);

}

}

(4) 求二叉树的叶子数。
可以将此问题视为一种特殊的遍历问题，这种遍历中“访问一个结点”的具体内容为判断该结点是不是叶子，若是则将叶子数加1。显然可以采用任何遍历方法，这里用先根遍历。
算法5.8求二叉树的叶子数算法。

//先根遍历根指针为root的二叉树以计算其叶子数 

int countleaf(bitreptr root)

{

int i;

if(root==NULL) 

i=0;

else if((root->lchild==NULL)&&(root->rchild==NULL))

i=1;

else

i=countleaf(root->lchild)+countleaf(root->rchild);

return(i);

}


5.4线索二叉树

5.4.1线索二叉树的定义
当用二叉链表作为二叉树的存储结构时，由于每个结点中只有指向其左、右孩子结点的指针域，所以从任一结点出发只能直接找到该结点的左、右孩子，一般情况下无法直接找到该结点在某种遍历序列中的前驱和后继结点。为此，若在每个结点中增加两个指针域来存放遍历时得到的前驱和后继信息，则将大大降低存储空间的利用率。由于在n个结点的二叉链表中含有n+1个空指针域，因此可以利用这些空指针域，存放指向结点在某种遍历次序下的前驱和后继结点的指针，这种附加的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(threaded binary tree)。
为了区分一个结点的指针域是指向其孩子的指针，还是指向其前驱或后继的线索，可在每个结点中增加两个标志域，这样，线索链表中的结点结构为： 






lchildltagdatartagrchild

其中： 左标志ltag=0表示lchild是指向结点的左孩子的指针； 否则，为指向结点的前驱的左线索。右标志rtag=0表示rchild是指向结点的右孩子的指针； 否则，为指向结点的后继的右线索。
如图5.14(a)所示的中根线索二叉树，它的线索链表见图5.14(b)。图中的实线表示指针，虚线表示线索。结点C的左线索为空，表示C是中根序列的开始结点，它没有前驱； 结点E的右线索为空，表示E是中根序列的终端结点，它没有后继。显然在线索二叉树中，一个结点是叶子结点的充要条件是： 它的左、右标志均是1。


图5.14中根线索二叉树及其存储结构


将二叉树转换为线索二叉树的过程称为线索化。按某种次序将二叉树线索化，只要按该次序遍历二叉树，在遍历过程中用线索取代空指针即可。为此，附加一个指针pre始终指向刚访问过的结点，而指针p指向当前正在访问的结点。显然结点*pre是结点*p的前驱，而*p是*pre的后继。下面给出将二叉树按中根线索化的算法。该算法与中根遍历算法类似，只需要将遍历算法中访问结点*p的操作具体化为在*p及其中根前驱*pre(若pre!=NULL)之间建立线索的操作即可。显然pre的初值应为NULL。
算法5.9二叉树中根线索化算法。

typedef int  datatype;

typedef enum {link，thread} pointertag;//枚举值link和thread分别为0，1

typedef struct node

{

datatype data;

pointertag ltag，rtag; //左、右标志

struct node *lchild，*rchild;

}binthrnode;

typedef binthrnode *binthrtree;

binthrnode *pre=NULL;//全局变量

void in_thread(binthrtree p) 

{

if(p) //p非空时，当前访问结点是*p 

{

in_thread(p->lchild); //左子树线索化

//以下直至右子树线索化之前相当于遍历算法中访问结点的操作

p->ltag=(p->lchild)?link:thread;

//左指针非空时左标志为link(即为0)，否则为thread(即1)

p->rtag=(p->rchild)?link:thread;

if (pre)  //若*p的前驱*pre存在

{if(pre->rtag==thread) //*p的前驱右标志为线索

pre->rchild=p; //令*pre的右线索指向中根后继

if(p->ltag==thread) //*p的左标志为线索

p->lchild=pre; //令*p的左线索指向中根前驱

}

pre=p;  //令pre时下一访问结点的中根前驱

in_thread(p->rchild);

}

}

显然，和中根遍历算法一样，递归过程中对每个结点仅做一次访问，因此对于n个结点的二叉树，算法的时间复杂度也为O(n)。
类似地可得前根线索化和后根线索化算法。
5.4.2线索二叉树的常用运算
下面介绍线索二叉树上两种常用的运算。
1. 查找某结点*p在指定次序下的前驱和后继结点
在中根线索二叉树中，查找结点*p的中根线索后继结点分以下两种情形。
(1) 若*p的右子树为空(即p>rtag为thread)，则p>rchild为右线索，直接指向*p的中根后继。例如，图5.14中D的中根后继是A。
(2) 若*p的右子树非空(即p>rtag为link)，则*p的中根后继必是其右子树中第一个中根遍历到的结点，也就是从*p的右孩子开始，沿该孩子的左链往下查找，直到找到一个没有左孩子的结点为止。该结点是*p的右子树中最左下的结点，它就是*p的中根线索后继结点。如图5.15所示，*p的中根线索后继结点是Rk(k≥1)。Rk可能有右孩子也可能无右孩子，若Rk无右孩子，则它必定是叶结点。若k=1，则表示*p的右孩子R1是*p的中根线索后继，如图5.14中，A的中根线索后继是F，它有右孩子； F的中根线索后继是H，它无右孩子； B的中根线索后继是D，它是B的右孩子(即D相当于是R1)。


图5.15结点*p的右子树非空时其中根线索后继结点是Rk


基于上述分析，不难给出中根线索二叉树中求中根线索后继结点的算法。
算法5.10中根线索二叉树中求中根线索后继结点算法。

//在中根线索树中找结点*p的中根线索后继，设p非空

binthrnode *in_succ(binthrnode *p)

{

binthrnode *q;

if (p->rtag==thread)  //*p的右子树为空

return p->rchild;  //返回右线索所指的中根线索后继

else

{

q=p->rchild;

while (q->ltag==link)

q=q->lchild;  //左子树非空时，沿左链往下查找

return q;  //当q的左子树为空时，它就是最左下结点

}

}

显然，该算法的时间复杂度不超过树的高度h，即O(h)。
由于中根遍历是一种对称遍历操作，故在中根线索二叉树中查找结点*p的中根线索前驱结点与找中根线索后继结点的方法完全对称。若*p的左子树为空，则p>lchild为左线索，直接指向*p的中根线索前驱结点； 若*p的左子树非空，则从*p的左孩子出发，沿右指针链往下查找，直到找到一个没有右孩子的结点为止。该结点是*p的左子树中最右下的结点，它是*p的左子树中最后一个中根线索遍历到的结点，即*p的中根线索前驱结点，如图5.16所示。


图5.16结点*p的左子树非空时，其中根线索前驱结点是Rk


由上述讨论可知： 若结点*p的左子树(或右子树)非空，则*p的中根线索前驱(或中根线索后继)是从*p的左孩子(或右孩子)开始往下查找，由于二叉链表中结点的链域是向下链接的，所以在非线索二叉树中也同样容易找到*p的中根线索前驱(或中根线索后继)； 若结点*p的左子树(或右子树)为空，则在中根线索二叉树中是通过*p的左线索(或右线索)直接到找到*p的中根线索前驱(或中根线索后继)，但中根线索一般都是向上指向其祖先结点，而二叉链表中没有向上的链接，因此在这种情况下，对于非线索二叉树，仅从*p出发无法找到其中根线索前驱(或中根线索后继)，而必须从根结点开始中根线索遍历，才能找到*p的中根线索前驱(或中根线索后继)。由此可见，线索使得查找中根线索前驱和中根线索后继变得简单有效，而对于查找指定结点的前根线索前驱和后根线索后继却没有什么帮助。

在后根线索二叉树中，查找指定结点*p的后根线索前驱结点的规律是： 
(1) 若*p的左子树为空，则p>lchild是前驱线索，指示其后根线索前驱结点。例如，在图5.17中，H的后根线索前驱是B，F的后根线索前驱是G。
(2) 若*p的左子树为非空，则p>lchild不是前驱线索。但因为在后根遍历时，根是在遍历其左右子树之后被访问的，故*p的后根线索前驱必是两子树中最后一个遍历到的结点。因此，当*p的右子树非空时，*p的右孩子必是其后根线索前驱，例如，图5.17中A的后根线索前驱是E； 当*p无右子树时，*p的后根线索前驱必是其左孩子，如图5.17中E的后根线索前驱是F。


图5.17后根线索二叉树


在后根线索二叉树中，查找指定结点*p的后根线索后继结点的规律是： 
(1) 若*p是根，则*p是该二叉树后根遍历过程中最后一个访问到的结点，因此，*p的后根线索后继为空。
(2) 若*p是其双亲的右孩子，则*p的后根线索后继结点就是其双亲结点，如图5.17中，E的后根线索后继是A。
(3) 若*p是其双亲的左孩子，但*p无右兄弟时，*p的后根线索后继结点是其双亲结点，如图5.17中，F的后根线索后继是E。
(4) 若*p是其双亲的左孩子，但*p有右兄弟时，则*p的后根线索后继结点是其双亲的右子树中第一个后根线索遍历到的结点，它是该子树中“最左下的叶结点”。例如图5.17中，B的后根线索后继是双亲A的右子树中最左下的叶结点H。注意，F是孩子树中最左下结点，但它不是叶子。
由上述讨论可知，在后根线索树中，仅从*p出发就能找到其后根线索前驱结点； 而找*p的后根线索后继结点，仅当*p的右子树为空时，才能直接由*p的右线索p>rchild得到，否则就必须知道*p的双亲结点才能找到其后根线索后继。因此，如果线索二叉树中的结点没有指向其双亲结点的指针，就可能要从根开始进行后根线索遍历才能找到结点*p的后根线索后继。由此可见，线索对查找指定结点的后根线索后继并无多大帮助。
类似地，在先根线索二叉树中，找某一点*p的先根线索后继也很简单，仅从*p出发就可以找到； 但找其先根线索前驱也必须知道*p的双亲结点，当树中结点未设双亲指针时，同样要进行从根开始的先根线索遍历才能找到结点*p的先根线索前驱。详细过程建议读者自行分析。
2. 遍历线索二叉树
遍历某种次序的线索二叉树，只要从该次序下的开始结点出发，反复找到结点在该次序下的后继，直至终端结点。这对于中根和先根线索二叉树是十分简单的。下面给出中根遍历算法。
算法5.11遍历中根线索二叉树算法。

void traverseinorderthrtree(binthrtree p)//遍历中根线索二叉树

{

if(p)  //树非空

{

while (p->ltag==link)

p=p->lchild; //从根往下找最左下结点，即中根序列的开始结点

do

{

printf("%c"，p->data);  //访问结点

p=in_succ(p);  //找*p的中根线索后继

}while(p);

}

}

由于中根序列的终端结点的右线索为空，所以do语句的终止条件是p==NULL。显然，该算法的时间复杂度为O(n)，但因为它是非递归算法，所以在常数因子上小于递归的遍历算法。因此，若对一棵二叉树要经常遍历，或查找结点在指定次序下的前驱和后继，则应采用线索链表作为存储结构为宜。
本节介绍的线索二叉树是一种全线索树，即左、右线索均要建立，但在许多应用中只要建立左、右线索中的一种即可。此外，若在线索链表中增加一个头结点，令头结点的左指针指向根，右指针指向其遍历序列的开始或终端结点会更方便。

5.5一般树的表示和遍历

5.5.1一般树的表示
在实际应用中，树(这里特指非二叉树)有多种存储结构。下面介绍三种常用的链表结构。
1. 双亲表示法
假设以一组连续的空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置，其形式说明如下： 

#define MAXNODE  //最大结点数

typedef struct  

{datatype data;//数据域 

int parent:;//双亲域(静态指针域) 

}tnode

typedef   tnode tree［MAXNODE+1］;//静态双亲链表 

图5.18展示了一棵树及其双亲表示的存储结构。


图5.18树的双亲表示法


这种存储结构利用了每个结点(除根以外)只有唯一双亲的性质。反复进行求双亲的操作，直到遇到无双亲的结点时，便找到了树的根。但是，在这种表示法中，求结点的孩子时，需要遍历整个向量。
2. 孩子表示法
这种存储方式可以有两种结点结构。一种结构根据树中每个结点可以有多棵子树，则可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，此时链表中的结点可以有两种格式： 一种格式称为同构格式，即若树的度是d，则每个结点就有d个指针域。但是，如果树中很多结点的度小于d，链表中就会有许多空链域，造成较大的空间浪费。另一种格式称为异构格式，每个结点的指针域的个数与该结点的度数相同，这种方式虽能节约空间，但操作不便。
还有一种办法是把每个结点的孩子结点排列成一个线性表，以单链表作为存储结构，则n个结点就有n个孩子链表(叶子的孩子链表为空表)。而n个头指针又组成一个线性表，为了便于查找，由这n个头指针组成的线性表可用向量表示。这种存储结构形式说明如下： 

typedef struct node 

{int child;

struct node *next;

}*link;

typedef link tree［MAXNODE+1］;

图5.19(a)是图5.18中的树的孩子表示法。与双亲表示法相反，孩子表示法便于那些涉及孩子的操作，却不适用于求双亲的操作。也可以把双亲表示法和孩子表示法结合起来，即将双亲向量和孩子表头指针向量合在一起。图5.19(b)就是这样一种存储结构，它和图5.19(a)表示的是同一棵树。


图5.19图5.18所示树的另外两种表示法


3. 孩子兄弟表示法
孩子兄弟表示法又称二叉树表示法或二叉链表表示法。即以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为fch域和nsib域。

typedef struct tnodetp

{

datatype data;

tnodetp  *fch，*nsib;

}*tlinktp;

图5.20是图5.18中的树的孩子兄弟链表表示法。利用这种存储结构便于实现各类树的操作。首先易于实现找结点孩子等的操作。例如： 若要访问结点x的第i个孩子，则只要先从fch域找到第一个孩子结点，然后沿着孩子结点的nsib域连续走i-1步，便可找到x的第i个孩子。当然，如果为每个结点增设一个parent域，也同样能方便地实现求双亲的操作。


图5.20图5.18中树的二叉链表表示法


5.5.2二叉树与树、森林之间的转换
1. 二叉树与树之间的转换

由于二叉树和树都可用二叉链表作为存储结构，因此以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。也就是说，给定一棵树，可以找到唯一的一棵二叉树与之对应，从物理结构来看，它们的二叉链表是相同的，只是解释不同而已。
图5.21直观地展示了树与二叉树之间的对应关系。


图5.21树与二叉树之间的对应关系示例


2. 二叉树与森林之间的转换
从树的二叉链表表示的定义可知，任何一棵与树对应的二叉树，其根的右子树必为空。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。
图5.22展示了森林与二叉树之间的对应关系。



图5.22森林与二叉树的对应关系示例


这种一一对应的关系使得森林或树与二叉树可以相互转换，其形式定义如下。
1) 森林转换成二叉树

如果F={T1，T2，…，Tm}是森林，则可按如下规则转换成一棵二叉树B＝(root，LB，RB)。
① 若F为空，即m=0，则B为空树。
② 若F为非空，即m≠0，则B的根root即为森林中第一棵子树的根root(T1)； B的左子树LB是从T1中根结点的子树森林F1={T11，T12，…，T1m}转换而成的二叉树； 其右子树RB是从森林F'={T2，T3，…，Tm}转换而成的二叉树。
2) 二叉树转换成森林
如果B＝(root，LB，RB)是一棵二叉树，则可按如下规则转换成森林F={T1，T2，…，Tm}。 
① 若B为空，则F为空。
② 若B为非空，则F中第一棵树T1的根root(T1)即为二叉树Ｂ的根root； T1中根结点的子树森林F1是由B的左子树LB转换而成的森林； F中除T1之外其余的树组成的森林F'={T2，T3，…，Tm}是由B的右子树RB转换而成的森林。
从上述递归定义容易写出相互转换的递归算法。这样，森林和树的操作就可以转换成二叉树的操作来实现，从而简化了操作方法。
5.5.3一般树的遍历
与二叉树类似，遍历是树的一种重要运算。树的主要遍历方法有以下三种。
1. 先根遍历(与对应的二叉树的先根遍历序列一致)
若树非空，则： 
(1) 访问根结点。
(2) 依次先根遍历根的各个子树。
2. 后根遍历(与对应的二叉树的中根遍历序列一致)
若树非空，则： 
(1) 依次后根遍历根的各个子树。
(2) 访问根结点。
3. 层次遍历
(1) 若树非空，访问根结点。
(2) 若第1~i(i≥1)层结点已被访问，且第i+1层结点尚未访问，则从左到右依次访问第i+1层。
显然，按层次遍历所得的结点访问序列中，各结点的序号与按层编号所得的编号一致。
例如，对图5.23所示树来说： 

先根遍历结点序列为A，B，D，E，H，I，J，C，F，G； 
后根遍历结点序列为D，H，I，J，E，B，F，G，C，A； 
层次遍历结点序列为A，B，C，D，E，F，G，H，I，J。


图5.23一般树示例



5.6哈夫曼树及其应用


哈夫曼(Huffman)树又称最优二叉树，是一种带权路径长度最短的树，有着广泛的应用。本节先讨论哈夫曼树的概念，然后讨论它的应用： 最佳判断过程和哈夫曼编码。
5.6.1哈夫曼树
1. 树的路径长度和带权路径长度

结点间的路径长度： 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称为这两个结点之间的路径长度。
树的路径长度： 从树根到每个结点的路径长度之和。这种路径长度最短的树是前面定义的完全二叉树。
在许多应用中，常常将树中结点赋予一个有某种意义的实数，称为该结点的权。
结点的带权路径长度为： 从该结点到树根之间的路径长度与结点上权的乘积。
树的带权路径长度为： 树中所有叶子结点的带权路径长度之和，通常记作
WPL=W1L1+W2L2+W3L3+…+WiLi+…+WnLn

=∑ni=1WiLi
其中，n为二叉树的叶子结点的个数，Wi为第i个叶子结点的权值，Li为从根结点到第i个叶子结点的路径长度。
例如，图5.24中的三棵二叉树，都有4个叶子结点a，b，c，d，权值分别为7，5，2，4，它们的带权路径长度分别为
WPL＝7×2＋5×2＋2×2＋4×2＝36

WPL＝7×3＋5×3＋2×1＋4×2＝46

WPL＝7×1＋5×2＋2×3＋4×3＝35


图5.24具有不同带权路径的二叉树


2. 哈夫曼树和哈夫曼算法

假设有n个权值W1，W2，…，Wn，试构成一棵有n个叶子结点的二叉树，每个叶子结点权值为Wi，则其中带权路径长度WPL最小的二叉树称作哈夫曼树(或最优二叉树)。
在图5.24(c)中的树的WPL最小。可以验证，它恰为哈夫曼树，即其带权路径长度在所有权值为7，5，2，4的4个叶子结点的二叉树中最小。
怎样根据n个权值W1，W2，…，Wn构造哈夫曼树呢？哈夫曼在1952年提出了一种算法，很好地解决了这个问题。该算法被称为哈夫曼算法，简述如下。
(1) 根据给定的n个权值W1，W2，…，Wn，构成n棵二叉树的集合F＝{T1，T2，…，Tn}，其中每棵二叉树Ti中只有一个权为Wi的根结点，其左、右子树均为空。
(2) 在F中任选两棵根结点的权值最小的树作为左、右子树，构成一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
(3) 从F中删除这两棵树，同时将新得到的二叉树加入到F中。
(4) 重复(2)和(3)步，直到F中只含一棵树为止。这棵树便是哈夫曼树。
例如有4个叶子结点a，b，c，d，权值分别为6，5，3，4，其哈夫曼树的构造过程如图5.25所示。


图5.25哈夫曼树的构造过程



下面讨论哈夫曼树的存储结构及哈夫曼算法的实现。
由哈夫曼算法可知，初始森林中共有n棵二叉树，每棵树中都仅有一个孤立的结点，它们既是根，又是叶子。算法的第（2）步是： 将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新二叉树。每合并一次，森林中就减少一棵树。显然，要进行n-1次合并，才能使森林中的二叉树的数目由n棵减少到剩下一棵最终的哈夫曼树。并且，每次合并都要产生一个新结点，合并n-1次共产生n-1个新结点，显然它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中共有2n-1个结点，其中n个叶子结点是初始森林中的n个孤立结点。显然，哈夫曼树中没有度为1的分支结点，这类树常称为严格的二叉树。实际上，所有具有n个叶子结点的严格二叉树都恰有2n-1个结点。可以用一个大小为2n-1的向量来存储哈夫曼树中的结点，其存储结构为： 

#define n 叶子数

#define m 2*n-1//树中结点总数 

typedef struct

{  //结点类型 

int weight;//权值 

int plink，llink，rlink;//双亲及左右孩子指针(静态指针) 

}node;

node tree［m+1］;//下标取值从1到m，0作为空指针标志 


在上述存储结构上实现的哈夫曼树算法可大致描述为： 
(1) 初始化。将tree［1..m］中每个结点里的三个指针均置为空(即置为0)。
(2) 输入。读入n个叶子的权值，分别保存于tree的前n个分量中，它们是初始森林中n个孤立的根结点上的权值。
(3) 合并。
对森林中的树共进行n-1次合并，所产生的新结点依次放入tree的第i个分量中(n<i≤m)。每次合并分两步： 
① 在当前森林tree［1..i-1］的所有结点中，选取权值最小和次小的两个根结点tree［x1］和tree［x2］作为合并对象，这里1≤x1，x2≤i-1。
② 将根为tree［x1］和tree［x2］的两棵树作为左右子树合并成为一棵新的树，新树的根是新结点tree［i］。因此，应将tree［x1］和tree［x2］的双亲plink置为i，将tree［i］的llink和rlink分别置为x1和x2，而新结点tree［i］的权值应置为tree［x1］和tree［x2］的权值之和。注意，合并后tree［x1］和tree［x2］在当前森林中已不再是根，因为它们的双亲指针均已指向了tree［i］，所以下一次合并时不会被选为合并对象。
哈夫曼算法实现如下。
算法5.12哈夫曼树的构造。

void sethuftree(node tree［］)

{

int i，x1，x2;

inithafumantree(tree);//将tree初始化 

inputweight(tree);//输入叶子权值 

for(i=n+1;i<=m;i++)//共进行n-1次合并，新结点依次存于tree［i］中 

{

select(i-1，&x1，&x2);

//在tree［1..i-1］中选择两个权值最小的根结点，其序号分别为x1 和x2 

tree［x1］.plink=i;

tree［x2］.plink=i;

tree［i］.llink=x1;//权值最小的根结点是新结点的左孩子 

tree［i］.rlink=x2; //权值次小的根结点是新结点的右孩子 

tree［i］.weight=tree［x1］.weight+tree［x2］.weight;

}

}

5.6.2哈夫曼树的应用
1. 最佳判定算法

在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法。例如，要编制一个将百分制转换成五级分制的程序，只需利用条件语句便可完成。如： 

if(a<60)

b="bad";

else if(a<70)

b="pass";

else if(a<80)

b="general";

else if(a<90)

b="good";

else b="excellent";


这个判定过程可用图5.26(a)的判定树来表示。如果上述程序需反复使用，而且每次的输入量很大，则应考虑上述程序的执行效率问题，即其操作所需时间。因为在实际问题处理中，学生的成绩在五个等级上的分布是不均匀的。假设其分布如表5.1所示，显然，80%以上的数据需进行3次或3次上的比较才能得出结果。


表5.1学生成绩分布表



分数0~5960~6970~7980~8990~100
比例数0.050.150.400.300.10

假定以5、15、40、30、10为权值构成一棵有五个叶子结点的哈夫曼树，则可得到如图5.26(b)所示的判定过程，它可使大部分数据经过较少的比较次数即得到结果。但由于每个判定框都有两次比较，将这两次比较分开，即得到如图5.26(c)所示的判定树，按此判定树写出相应的程序。假设现有10000个输入数据，按图5.26(a)所示的判定过程操作总共需进行31500次比较； 而按图5.26(c)所示的判定过程进行操作，则总共需进行22000次比较。显然，优化的判定过程极大地提高了效率。


图5.26转换五级分制的判定过程


2. 哈夫曼编码
电报是进行快速远距离的通信手段之一。发送电报时需将传送的文字转换成二进制的字符组成的字符串。例如，假设需传送的电文为'ＡＢＡＣＣＤＡ'，它只有四种字符，只需两位二进制字符串便可分辨。假设A、B、C、D的编码分别为00，01，10和11，则上述七个字符的电文编码为'00010010101100'，总长14位，对方接收时可按二位一分进行译码。
当然，在传送电文时，希望总长尽可能的短。如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长度便可减短。如果设计A、B、C、D的编码分别为0、00、1和01，则上述电文被编码成长度为9的字符串'000011010'。但是，这样的电文无法翻译。例如，传送过去的字符串中前四个字符的子串'0000'就可有多种译法，或是'AAAA'或是'ABAA'等。产生该问题的原因是Ａ的编码与Ｂ的编码的开始部分(前缀)相同。因此，若对某字符集进行不等长编码，就要求字符集中任一字符的编码都不是其他字符编码的前缀，这种编码称为前缀编码。显然，等长编码也是前缀编码。
问题是应该怎样设计前缀编码？什么样的前缀编码才能使得电文的总长最短？可以利用哈夫曼树设计二进制的前缀编码来解决此问题。



图5.27前缀编码示例


假设有一棵如图5.27所示的二叉树，其四个叶子结点分别表示Ａ、Ｂ、Ｃ、Ｄ四个字符，且约定左分支表示字符'0'，右分支表示字符'1'，则可将从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。不难理解，如此得到的必为二进制前缀编码，如图5.27所示，Ａ、Ｂ、Ｃ、Ｄ的二进制前缀编码分别为0、10、110和111。

那么如何得到使电文总长最短的二进制前缀编码呢？假设每种字符在电文中出现的次数为Wi，其编码长度为Li，电文中只有n种字符，则电文总长为W1L1+W2L2+…+WiLi+…+WnLn。对应到二叉树上，若置Wi为叶子结点的权，Li 恰为从根到叶子的路径长度。则W1L1+W2L2+…+WiLi+WnLn恰为二叉树的带权路径长度。由此可见，设计电文总长最短的二进制前缀编码，也就是以n种字符出现的频率作叶子结点的权，设计一个哈夫曼树的问题，由此得到的二进制前缀编码便称为哈夫曼编码。
在求出了给定字符集的哈夫曼树后，求该字符集的哈夫曼编码的具体过程是： 依次以叶子tree［i］(1≤i≤n)为出发点，向上回溯至根为止。上溯时走左分支则生成编码0，走右分支则生成编码1。显然，这样生成的编码与要求的编码反序。因此，将生成的代码从后往前依次存放在一个临时向量中，并设一个指针start指示编码在该向量中的起始位置。当某字符编码完成时，从临时向量的start处将编码复制到该字符相应的位串bits中即可。因为字符集大小为n，故变长编码的长度不会超过n，加上一个结束符'＼0'，bits的大小应为n+1。
字符集编码的存储结构及其算法描述如算法5.13。
算法5.13哈夫曼编码。

typedef struct

{  //结点类型 

int weight;//权值 

int plink，llink，rlink;//双亲及左右孩子指针(静态指针)

}node;

typedef struct

{

int start;//存放起始位置 

char bits［n+1］;//存放编码位串 

}codetype;

typedef struct

{

char symbol;//存储字符 

codetype code;//存储编码

}element;

element table［n+1］;

void huffcode(node tree［］，element table［］)//根据哈夫曼树tree求哈夫曼编码表table 

{

int i，s，f;//s 和f分别指示tree中孩子和双亲的位置 

codetype c;//临时存放编码 

for(i=1;i<=n;i++)//依次求叶子tree［i］的编码 

{

c.start=n+1;

s=i;//从叶子tree［i］开始上溯 

while(f=tree［s］.plink)//直至上溯到树根为止 

{

c.bits［--c.start］=(s==tree［f］.llink)?'0':'1';

s=f;

f=tree［s］.plink;

};

table［i］.code=c;//临时编码复制到最终位置 

}

}





图5.28例5.1的哈夫曼树



例5.1已知某系统在通信网络中只可能出现八种字符(A、B、C、D、E、F、G、H)，其频率分别为0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11，试设计哈夫曼编码。
设权W＝(5，29，7，8，14，23，3，11)，字符数目n=8，按照哈夫曼算法可构造一棵哈夫曼树，如图5.28所示，根据哈夫曼树得到的哈夫曼编码如图5.29所示。
有了字符集的哈夫曼编码表之后，对数据文件的编码过程是： 依次读入文件中的字符C，在哈夫曼编码表table中找到此字符，若table［i］.symbol==C，则将字符C转换为table［i］.code中存放的编码串。
对压缩后的数据文件进行解码则必须借助于哈夫曼树tree。其过程是： 依次读入文件的二进制码，从哈夫曼树的根结点出发，若当前读入0，则走向左孩子，否则走向右孩子，一旦达到某一叶子tree［i］时便译出相应的字符table［i］.symbol，然后重新从根出发继续译码，直至文件结束。



图5.29哈夫曼编码




5.7C++中的树

5.7.1C++中的二叉树结点类
例5.2是二叉链表结点的C++类BTNode，每个结点包含三个数据成员和三个构造函数。
例5.2二叉树结点类。

template<class T>

struct BTNode

{

BTNode(){ lChild=rChild=NULL;}  

//lChild和rChild分别是指向左孩子和右孩子的指针

BTNode(const T& x)             

{

element=x; lChild=rChild=NULL;

}

BTNode(const T& x, BTNode<T>* l,BTNode<T>* r)

{

element=x; lChild=l; rChild=r;

}

T element;

BTNode<T> *lChild, *rChild;

};

5.7.2C++中的二
叉树类
例5.3定义了由二叉链表表示的二叉树类BinaryTree。类BinaryTree包含唯一的数据成员，它指向一个二叉链表根结点的指针root。请务必注意区分二叉树对象和由二叉树对象的根指针root所指示的二叉树(即二叉链表)。一个二叉树对象的根指针root所指示的二叉树，是该二叉树对象所包含的一棵二叉树。在不引起混淆的情况下，将二叉树对象和它所包含的二叉树统称为二叉树。例5.4是二叉树类BinaryTree的部分运算。例5.5是二叉树类BinaryTree的递归方式先根遍历二叉树运算。
例5.3二叉树类。

template<class T>

class BinaryTree

{

public:

BinaryTree(){root=NULL;}                

~BinaryTree(){Clear();}

bool IsEmpty()const;

void Clear();

bool Root(T &x)const;

void MakeTree(const T &e ,BinaryTree<T>&left, BinaryTree<T>& right); 

//构造二叉树

void BreakTree(T &e ,BinaryTree<T>&left, BinaryTree<T>& right); 

void PreOrder(void (*Visit)(T& x));    //递归方式先根遍历二叉树

void InOrder(void (*Visit)(T& x));     

void PostOrder(void (*Visit)(T& x));   

protected:

BTNode<T>* root;

private:

void Clear(BTNode<T>* t);

void PreOrder(void (*Visit)(T& x),BTNode<T>*t);

void InOrder(void (*Visit)(T& x),BTNode<T>*t); 

void PostOrder(void (*Visit)(T& x),BTNode<T>*t);     

};


例5.4部分二叉树运算。

template <class T>

bool BinaryTree<T>::Root(T &x)const

{

if(root){

x=root->element; return true;

}

else return false;

}

template <class T>

void BinaryTree<T>::MakeTree(const T &x ,BinaryTree<T>&left,BinaryTree<T>& right)

{

if(root||&left==&right) return;

root=new BTNode<T>(x,left.root, right.root);

 left.root=right.root=NULL;

}

template <class T>

void BinaryTree<T>::BreakTree(T &x, BinaryTree<T>&left, BinaryTree<T>& right)

{

if (!root||&left==&right||left.root||right.root)return;

x=root->element;

left.root=root->lChild;right.root=root->rChild;

delete root;root=NULL;     

}

例5.5递归方式先根遍历二叉树。

template <class T>

void BinaryTree<T>::PreOrder(void (*Visit)(T& x))

{

PreOrder(Visit,root);

}

template <class T>

void BinaryTree<T>::PreOrder(void (*Visit)(T& x),BTNode<T>* t)

{

if (t){

Visit(t->element);             //递归遍历根结点

PreOrder(Visit,t->lChild);     //递归遍历左子树

PreOrder(Visit,t->rChild);     //递归遍历右子树

}

}

5.7.3C++中二叉树的非递归遍历
二叉树的遍历可分为递归方式和非递归方式。用C++来描述二叉树的非递归遍历如例5.6所示的遍历器类BIterator，由它可派生三个具体实施先根、中根和后根遍历的遍历器类，例5.7是非递归方式的中根遍历器类。
例5.6遍历器类。

template <class T>

class BIterator

{

public:

virtual T* GoFirst(const BinaryTree<T>& bt)=0;

virtual T* Next (void)=0;

virtual void Traverse(void (*Visit)(T& x),const BinaryTree<T>& bt);

protected:

BTNode<T>* r, *current;

};

template <class T>

void BIterator<T>::Traverse(void (*Visit)(T& x),const BinaryTree<T>& bt)

{

T* p=GoFirst(bt);

while (p){

Visit(*p);p=Next();

}

}

例5.7中根遍历器类。

template <class T>

class IInOrder:public  BIterator<T>

{

public:

IInOrder(BinaryTree<T>& bt,int mSize)

{ 

r=bt.root; current=NULL;

s=new SeqStack<BTNode<T>* >(mSize);

}

T* GoFirst(const BinaryTree<T>& bt);

T* Next (void);

private:

SeqStack<BTNode<T>*> *s;

};	

template <class T>

T* IInOrder<T>::GoFirst(const BinaryTree<T>&bt)

{

 current=bt.root;

if (!current) return NULL;

while (current->lChild!=NULL){

s->Push(current); current=current->lChild;

}

return &current->element;

}

template <class T>

T* IInOrder<T>::Next(void)

{

BTNode<T>* p;

if (current->rChild!=NULL){

  p=current->rChild;		   

while (p->lChild!=NULL){			

s->Push(p);p=p->lChild;

}

  current=p;

}

else if (!s->IsEmpty()){

s->Top(current); s->Pop();

}

else {

current=NULL; return NULL;

}

return &current->element;

}


习题5

1. 已知一棵树边的集合为(I，M)、(I，N)、(E，I)、(B，E)、(B，D)、(A，B)、(G，J)、(G，K)、(C，G)、(C，F)、(T，L)、(C，T)、(A，C)，画出这棵树，并回答下列问题： 
(1) 哪个是根结点？
(2) 哪些是叶子结点？
(3) 哪个是结点Ｇ的双亲？
(4) 哪些是结点Ｇ的祖先？
(5) 哪些是结点Ｇ的孩子？
(6) 哪些是结点Ｅ的子孙？
(7) 哪些是结点Ｅ的兄弟？哪些是结点Ｆ的兄弟？
(8) 结点Ｂ和Ｎ的层次号分别是什么？
(9) 树的深度是多少？
(10) 以结点Ｃ为根的子树的深度是多少？
2. 一棵度为2的树与一棵二叉树有何区别？
3. 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
4. 一棵深度为N的满K叉树有如下性质： 第N层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树。如果按层次顺序从1开始对全部结点编号，问:
(1) 各层的结点数目是多少？
(2) 编号为n的结点的父结点(若存在)的编号是多少？
(3) 编号为n的结点的第i个儿子(若存在)的编号是多少？
(4) 编号为n的结点有右兄弟的条件是什么？其右兄弟的编号是多少？
5. 已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，…，nm个度为m的结点，问该树中有多少个叶子结点？



图5.30二叉树示例

6. 试列出图5.30所示的二叉树的终端结点、非终端结点以及每个结点的层次。
7. 对于图5.30所示的二叉树，分别列出先根遍历、中根遍历、后根遍历的结点序列。
8. 在二叉树的顺序存储结构中，实际上隐含着双亲的信息，因此可和三叉链表对应。假设每个指针域占4字节的存储空间，每个信息占k字节的存储空间。试问对于一棵有n个结点的二叉树，且在顺序存储结构中最后一个结点的下标为m，在什么条件下顺序存储结构比二叉链表更节省空间？
9. 假定用两个一维数组L(1∶n)和R(1∶n)作为有n个结点的二叉树的存储结构，L(i)和R(i)分别指示结点i的左孩子和右孩子，0表示空。
(1) 试写一个算法判别结点u是否为结点v的子孙； 
(2) 先由L(1∶n)和R(1∶n)建立一维数组T(1∶n)，使T中第i(i=1，2，…，n)个分量指示结点i的双亲，然后编写判别结点u是否为结点v的子孙的算法。
10. 假设n和m为二叉树中的两结点，用1、0、Φ(分别表示肯定、恰恰相反和不一定)填写表5.2。



表5.2第10题表


先根遍历时中根遍历时后根遍历时


已知n在m前？n在m前？n在m前？
n在m的左方
n在m的右方
n是m的祖先
n是m的子孙


注： ① 如果离a和b最近的共同祖先p存在，且②a在p的左子树中，b在p的右子树中，则称a在b的左方(即b在a的右方)。

11. 假设以二叉链表作为存储结构，试分别写出先根遍历和后根遍历的非递归算法，可直接利用栈的基本运算。
12. 假设在二叉链表中增设两个域： 双亲域(parent)以指示其双亲结点； 标志域(mark)为0..2，以区分在遍历过程中到达该结点时应该继续向左或向右或访问该结点。试以此存储结构编写不用栈的后根遍历的算法。
13. 试编写算法在一棵以二叉链表存储的二叉树中求这样的结点： 它在先根序列中第K个位置。
14. 试以二叉链表作为存储结构，编写计算二叉树中叶子结点数目的递归算法。
15. 以二叉链表作为存储结构，编定算法将二叉树中所有结点的左、右子树相互交换。
16. 已知一棵二叉树以二叉链表作为存储结构，编写完成下列操作的算法： 对于树中每个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
17. 已知一棵以二叉链表作存储结构的二叉树，试编写复制这棵二叉树的非递归算法。
18. 已知一棵以二叉链表为存储结构的二叉树，试编写层次顺序(同一层自左向右)遍历二叉树的算法。
19. 试以二叉链表作为存储结构，编写算法判别给定二叉树是否为完全二叉树。

20. 已知一棵完全二叉树存在于顺序存储结构A(1∶max)中，A［1∶n］含结点值。试编写算法由此顺序结点建立该二叉树的二叉链表。
21. 编写一个算法，输出以二叉树表示的算术表达式，若该表达式中含有括号，则在输出时应该添上，已知二叉树的存储结构为二叉链表。
22. 一棵二叉树的直径定义为，从二叉树的根结点到所有叶子结点的路径长度的最大值。假设以二叉链表作为存储结构，试编写算法求给定二叉树的直径和其长度等于直径的一条路径(即从根到该叶子结点的序列)。
23. 试分别画出图5.31中各二叉树的先根、中根、后根的线索二叉树。


图5.31二叉树示例



24. 试编写一个算法，在中根线索二叉树中，结点p之下插入一棵以结点x为根，只有左子树的中根全线索化二叉树，使x为根的二叉树成为p的左子树，若p原来有左子树，则令它为x的右子树。完成插入之后二叉树应保持线索化特性。
25. 已知一棵以线索链表作为存储结构的中根线索二叉树，试编写在此二叉树上找后根线索后继的算法。
26. 将图5.32所示森林转换为相应的二叉树，并按中根遍历进行线索化： 


图5.32森林示例


27. 画出图5.31所示各二叉树相应的森林。
28. 对以下存储结构分别写出计算树的深度的算法。
(1) 双亲表示法； 
(2) 孩子链表表示法； 
(3) 孩子兄弟表示法。
29. 假设一棵二叉树的层序序列为A B C D E F G H I J，中根序列为D B G E H J A C I F。请画出该树。
30. 证明： 树中结点u是结点v的祖先，当且仅当在先根序列中u在v之前，且在后根序列中u在v之后。
31. 证明： 在结点数大于１的哈夫曼树中不存在度为１的结点。
32. 设有一组权WG＝1、4、9、16、25、36、49、64、81、100，试画出其哈夫曼树，并计算带权的路径长度。
33. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，试为这8个字母设计哈夫曼编码，使用0~7的二进制表示形式是另一编码方案。对于上述实例，比较两个方案的优缺点。
34. 证明： 由一棵二叉树的先根序列和中根序列可唯一确定这棵二叉树。
35. 已知一棵二叉树的先根序列和中根序列分别存在于两个一维数组中，试编写算法建立该二叉树的二叉链表。

上机练习5

1. 建立一棵二叉排序树并中根遍历(根据题目完善程序)。

#include "stdio.h"

#include "malloc.h"

struct node{

 char data;

 struct node  *lchild， *rchild;

} bnode;



typedef struct node * blink;



blink add(blink bt，char ch)//二叉排序树的插入算法

{ 

if(bt==NULL)

{

bt=nalloc(sizeof(bnode));

bt->data = ch;

bt->lchild = bt->rchild =NULL;

}

else 

if ( ch < bt->data)

bt->lchild = add(bt->lchid，ch);

	else 

bt->rchild = add(bt->rchild，ch);

return bt;

}



void inorder(blink bt)

{

 if(bt)

{  inorder(bt->);

printf("%c"，);

inorder(bt->);

}

}

void main()

{

 blink root = NULL;

 int i，n; 

 char x;

 scanf("%c"，&n);

 for(i=1;i<=n;i++)

 {

x=getchar();

root=add(root，x);

 }

 inorder(root);

 printf("＼n");

}

2. 由前缀表达式建立二叉树的二叉链表结构，求该表达式对应的后缀、中缀表达式。
3. 编写程序，实现按层次遍历二叉树。
4. 建立由合法的表达式字符串确定的只含二元操作符的非空表达式树，其存储结构为二叉链表，用二叉树的遍历算法求该中缀表达式对应的后缀、前缀表达式。