山东大学《数据结构》讲义04树和二叉树.docx

第四章树和二叉树
内容概述
树是一种非线性数据结构。树结构经常用于描述和处理数据元素的层次关系，尤其适用于大规模的信息处理任务，例如建立数据库管理系统时所用的层次模型 就是一种树型结构。本章主要以二叉树为例，讲述树结构及其应用，主要内容包 括：
(1)树的定义、术语及性质；
(2)二叉树的定义、性质，二叉树的存储结构及二叉树的遍历等各种操作的算 法实现；
(3)线索二叉树；
(4)树、森林与二叉树的转化；
(5)赫夫曼树及其应用。
重点与难点
重点包括：二叉树的性质及遍历算法，线索二叉树的运算，树、森林与二叉树 之间的转换，Huffman树的构造算法及Huffman编码、译码。
难点包括：二叉树的遍历算法，尤其是非递归遍历算法，线索二叉树的运算，Huffman编码、译码。
思考.树型结构的结构特点
1 .树和二叉树的主要差异表现在哪些方面？
2 .二叉树具有那些重要特性？
3 .二叉树有哪些遍历策略？如何利用算法实现？
4 .某二叉树的后序遍历序列和中序遍历序列，如何求解出其前序遍历序列。
5 .一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,画出该 elsereturnOK;}//PreOrderT raverse
算法4-1二叉树的先序遍历递归算法(2)中序遍历算法
StatusInOrderTraverse(BiTreePtrT,Status(*visit)(ElemTypee)){〃采用二叉链表存储结构，visit是对数据元素操作的应用函数
〃该算法采用递归的方式，对每个数据元素调用函数visitif(T){
if(InOrderT raverse(T - > left,visit))if(visit(T->data))
if(InOrderTraverse(T->right,visit))returnOK;returnERROR;
)elsereturnOK;
}//InOrderT raverse算法4-2二叉树的中序遍历递归算法
(3)后序遍历算法StatusPostOrderTraverse(BiTreePtrT,Status(*visit)(ElemTypee)){
〃采用二叉链表存储结构，visit是对数据元素操作的应用函数〃该算法采用递归的方式，对每个数据元素调用函数visit
if(T){if(PostOrderTraverse(T->left,visit))
if( PostOrderT raverse(T- > right,visit)) if(visit(T->data))returnOK;returnERROR;
)elsereturnOK;
}//PostOrderT raverse算法4-3二叉树的后序遍历递归算法
以上的三种算法均为递归算法，在运行过程中，函数需要使用系统设立的''递归 工作栈〃存储调用函数和被调用函数之间的链接及信息的交换。下面我们以中序 算法为例，结合图4.8(a)的二叉树，分析它的执行过程。
当开始调用中序遍历算法时(此次称为第0次递归调用)，需要以指向根结点a 的指针Ta作为实参，把它传递给形参T,递归栈中应包括形参T的值和返回地 址。现假定指向每个结点的指针用该结点的值作为T的后缀，如指向结点d的指 针就用Td表示，并且假定进行第0次递归调用后的返回地址为0,以及假设访 问函数为打印输出结点的值，那么函数递归调用的过程中，递归工作栈的状态如图 4.9所不。
① StatusInOrderTraverse(BiTreePtrT,Status(*visit)(ElemTypee)){② if(T){
③ if(InOrderr raverse(T-> left, visit))(4) if(visit(T->data))
⑤if(InOrderT raverse(T- > right,visit))
⑥⑦⑧⑨s)
returnOK;
returnERROR;
)
elsereturnOK;

递归层次、语
句
行号及执行结
果
一层 1,2,3
二层 1,2,3
递归工作栈状态（返
址，指针值）
0,Ta4,Tb
0,Ta4,Td
三层 1,2,34,Tb0,Ta
4,Td4,Tb
四层1,2,90,Ta
4,Td) 三层4,5
输出d4,Tb
O,Ta
4,Td
4,Tb

四层1,2,3O,Ta
6,Tg4,Td
4,Tb
五层 1,2,9O,Ta6,Tg
4,八4,Td
) 四层4,5
输出g
4,Tb

O,Ta
6,Tg4,Td
4,Tb五层 1,2,9O,Ta
6,Tg6, a
4,Td4,Tb
：10）四层6O,Ta
6,Tg4,Td
：11）三层 64,TbO,Ta
2）二层 4,54,Tb
输出bO,Ta
6, a3）三层 1,2,9
4,TbO,Ta
4,Tb：14）二层 6
15） 一层 4,5O,Ta
O,Ta输出a
6,Tc6）二层 1,2,3
O,Ta4,Te
7）三层 1,2,36,Tc
O,Ta
4,Te
8）四层 1,2,96,Tc
O,Ta

4,八4,Te

L9）三层4,5
6,Tc输出e
O,Ta
4,Te
6,Tc

））四层 1,2,9O,Ta
6, a4,Te

6,Tc
：21）三层6

O,Ta
6,Tc

?2）二层 4,5输出c
O,Ta
6,Tf

3）三层 1,2,3

6,Tc

4）四层 1,2,94,八
25）三层4,5输出f
6）四层 1,2,9：27）三层6
O,Ta
6,Tf
6,TcO,Ta
6,Tf6,Tc
O,Ta
6,Tf
6,TcO,Ta
6, a6,Tf
6,Tc

O,Ta6,Tc
：28)二层 6O,Ta
：29) 一层 6O,Ta(30)。层0栈空
图4.9二叉树中序遍历调用的过程中，递归工作栈的状态
上述分析的中序遍历的算法，最终打印出的结点序列为：dgbaecf
假设按照前序遍历算法和后序遍历算法遍历图4.8所示的二叉树，那么打印出的结点
序列分别为：abdgcef ^0 gdbefca
对于上述遍历递归算法执行过程中递归工作栈状态的变化，我们可以通过人工建
立栈仿照上述过程。具体算法描述如下：
StatusInOrderTaverse(BiTreePtrT,Status(*visit)(ElemTypee)){
〃中序遍历二叉树T的非递归算法，对每个数据元素调用函数visito
InitStack(S);p=T;
while(p| | !StackEmpty(S)){
if(p){Push(S,p);p=p->left;} 〃根指针进栈后，先遍历左子树
else{〃根指针退栈，访问根结点，遍历右子树
Pop(S,p); if(!visit(p->data))returnERROR;
p=p->right;
}//else
}//while
returnOK;
}//InOrderT raverse
算法4-4二叉树的中序遍历非递归算法
对于二叉树进行遍历操作的路径除了上述的按先序、中序或后序外，还可以从上 到下、从左到右按层次进行。
在二叉树的遍历算法中，访问每个结点的每一个域，并且每个结点的每一个域仅 被访问一次，所以算法的时间复杂度为0(n)。
7、二叉树中序遍历非递归算法
7、二叉树中序遍历非递归算法
StatusInOrderTaverse(BiTreePtrT,Status(*visit)(ElemTypee)){
〃中序遍历二叉树T的非递归算法，对每个数据元素调用函数visito
InitStack(S);p=T;
while(p| | !StackEmpty(S)){
if(p){Push(S,p);p=p->left;} 〃根指针进栈后，先遍历左子树
else{〃根指针退栈，访问根结点，遍历右子树
Pop(S,p); if(!visit(p->data))returnERROR;
p=p->right;
}//else
}//while
returnOK;
}//InOrderT raverse
算法4-4二叉树的中序遍历非递归算法
8、二叉树的其他运算
8、二叉树的其他运算(二叉树生成算法、二叉树的深度求解算法、删除二叉树 中指定结点的算法、清空二叉树的算法)
生成二叉树
建立二叉树的过程中，既可以使用逐个输入结点的方式，也可以一次性输入 树的所有结点。本算法采用后者的方式建立树，对于这种方式，我们可使用广义 表一次性输入所有结点。二叉树广义表表示的规定如下：
1)每棵树的根结点作为由子树构成的表的名字而放在表的前面；
2)每个结点的左子树和右子树用逗号隔开，假设只有右子树，那么逗号不能省略。
例如，对于图4.10所示的二叉树，其广义表表示为：
a(b(,e(h)),c(f(,i)))通过二叉树的广义表建立二叉树的链式存储结构的基本思路是：
从保存二叉树广义表的字符串tree中读取每个字符，
i, 假设遇到空格那么不进行任何操作；
ii, 假设遇到左括号，那么说明子表开始，应首先用栈存储指向它前面的字母所在结
点的指针，以便括号内的孩子结点向双亲结点链接，然后由于左括号后面紧跟的 字母(假设存在)必为刚进栈结点的左孩子，设定变量k=l,表示将进行左孩子结 点链接(k=2表示将进行右孩子结点链接)；
iii, 假设遇到的是字母(假设以字母作为结点的值)，应为它建立一个新结点，并把
该结点(假设它不是根结点)作为左孩子(假设k=l)或右孩子(假设k=2)链接到其 双亲结点上，即当前栈顶元素所指向的结点；
iv, 假设遇到逗号，那么说明应开始处理右孩子结点向其双亲结点的链接，使k=2;
v, 假设遇到右括号，那么说明该子表结束，应退栈。
按照如上所述方式处理每个字符，直到字符串读完为止。具体算法如下：
voidCreatBiTreel(BiTreePtr&T,char*tree){〃通过保存二叉树广义表的字符串tree建立链式存储结构
BiTreePtrp,e; //p为指向二叉树结点的指针intk；〃用k作为链接结点的左子树和右子树的标记
〃k=l表示左子树，k=2表示右子树inti=0;〃用i扫描字符串tree
InitStack(S);〃建立链栈，栈元素为二叉树结点的指针T=NULL;〃树初始化为空
while(tree[i]){〃每循环一次处理一个字符，直到扫描到字符串结束符为止
switch(tree[i]){case”:〃对空格不作任何处理
break;case'。：
Push(S,p);k=l;
break;case')':
if(StackEmpty(S)){print，'存储二叉树广义表的字符串有错误〃)；
exit(l);)
Pop(S,e);break;
case',':
k=2;break;
default:
p=(BiTreePtr)malloc(sizeof(BiTreeNode));p->data=tree[i];p->left=p->right=NULL;
if(T==NULL)T=p;else{GetTop(S,e);
if(k==l)e->left=p;else e->right=p;
)}//switch
i++；〃扫描下一个字符}//while
)算法4-6二叉链表的生成算法
在上述算法中，我们使用栈存储指向二叉树结点的指针，那么，我们能否不 通过定义栈直接按照上述算法中的思想完成树的建立呢？在栈的遍历中，我们看 到递归思想的应用，下面给出的改写算法，也是通过递归的方式完成上述操作, 本算法具体思想由读者去进一步思考。
StatusCreatBiT ree2(BiT reePtr&T){staticchartree[100];
staticintx=O;if(x==O)scanf("%snztree);
switch(tree[x]){case n:break;〃读入空格后继续读取
casex++;
CreatBiTree2(T->left)); 〃开始递归处理该结点的左子树if (tree [x]==7){x++; CreatBiT ree2(T-> right));}
〃对于逗号，退出到该层递归后处理结点右子树
if(tree[x]==')'){x++;CreatBiT ree2(T);}
〃对于右括号，退出到该层递归后处理新结点 break;case'『break;〃对于右括号不作任何处理，退出一层递归
二叉树的先序线索二叉树。
7.有一份电文中共使用5个字符：a、b、c、d、e,它们的出现频率依次为4、 7、5、2、9,试画出对应的赫夫曼树(请按左子树根结点的权小于等于右子树 根结点的权的次序构造)，并求出每个字符的赫夫曼编码。
第一节树
树是一种非线性数据结构，这种非线性结构有哪些特点？具有那些特有性质？ 如何描述树结构？本节从树的定义、抽象类型定义、树的基本概念与相关术语、 树的性质、树的表示等方面阐述上述问题。
工、树的递归与非递归定义
1 .树的递归定义
树(Tree)是n(n20)个结点的有限集合T,不含有任何结点(元素)的树称为 空树，否那么它满足如下两个条件：有且仅有一个称为根(Root)的结点；其余所有 结点被分成m(mNO)个互不相交的集合Ti,T2,T3,…,Tm,其中每个集合又构成一 棵树，称其为根结点的子树(SubTree)。树的根结点Root是每棵子树根结点的前 驱，每棵子树的根结点是根结点Root的后继。
例如,在图4.1中,(a)表示只有一个根结点的树;(b)表示有8个结点的树, 其中A是根结点，其余结点分成3个互不相交的子集：
Ti={B,E,FzG},T2={C},T3={D,H}o T1、丁2和T3都是根结点A的子树,且本身也 是一棵树。如Ti的根结点为B,其余结点分为3个互不相交的子集： Tii={E},Ti2={F}zTi3={G}o Tii> T12和 T13 都是 T1 的根结点 B 的子树。
2 .树的非递归定义
树是n(nNO)个结点的有限集合T,不含有任何结点(元素)的树称为空树， 而在任一非空树中定义了一个关系，它满足：
(1) T中存在唯一的一个结点，它没有前驱，称为树的根；(2)除根结点外，T中每一个结点都有且仅有一个前驱结点；
(3)除根结点外，T中每一个结点a,都存在一个从根结点到a的结点序列 ai...ak，使得比为根结点，ak=a,而结点ai+i是ai的后继(l<i<k-l),这个结点 序列称为从根结点到结点a的路径。
例如，在图4.1(b)中，A为树的根结点。对于结点G,存在一个结点序列ABG, 使得A为根结点，B为A的后继，G为B的后继，这个序列就是从根结点A到结 点G的路径。
2、树的抽象数据类型
2、树的抽象数据类型
树的抽象数据类型定义如下：
ADTT ree{数据对蓑 D： D={ai|aiGEIemSet,i=l,2,...,nzn>0}
数据关系R：假设D为空集，那么称为空树。
假设D仅含一个数据元素，那么R为空集，否那么R= {H} , H满足关系：
(1)T中存在唯一的一个结点，它没有前驱，称为树的根，用root表示，在集合
D中用比表示;case 7：break;〃对于逗号，退出一层递归后处理结点右子树
case NULL:break; 〃数组 tree 尾部default:
if(!(T=(BiTreeNode*)malloc(sizeof(BiTreeNode)))) exit(OVERFLOW);T->data=tree[x];T->left=T->right=NULL;x++;
CreatBiTree2(T);)
returnOK;算法4-7二叉链表的递归生成算法
求二叉树的深度
该算法采用递归的思想：假设一棵二叉树为空，那么它的深度为0,否那么它的深 度等于左子树和右子树中的最大深度加1。设depthL为左子树的深度，depthR 为右子树的深度，那么二叉树的深度为：
max(depthL,depthR)+l其中max函数表示取参数中的较大者。该算法具体描述如下：
IntBiT reeDepth(BiT reePtrT){jf(T==NULL)
returnO;〃对于空树，返回0并结束递归else{
i ntdepth L=BiT reeDepth(T - > left); 〃计算左子树的深度intdepthR=BiTreeDepth(T->right); 〃计算右子树的深度
return(depthL>depthR)?depthL+l:depthR+l; 〃返回树的深度算法4-8二叉树的深度求解算法
要删除指定结点及其左右子树，需分三种情况讨论：
i, 被删除结点无前驱，即树的根结点，那么先清空根结点的左子树，再清空 右子树，最后删除(即释放)根结点，并把根指针置空。
ii, 被删除结点无后继，即叶子结点，那么释放该结点，并且将其双亲结点指
向该结点的指针置空。
Hi.被删除结点有后继和前驱，那么清空该结点左右子树，然后释放该结点，且
将其双亲结点指向该结点的指针置空。
以上三种情况可归结为，判断该结点是否有后继，假设有，那么以递归的方式清 空左右子树，假设无那么不操作；判断该结点是否有双亲结点，假设有那么将其指向该结 点的指针置空，假设无那么不操作；释放该结点空间。具体算法描述如下：
StatusDelBiTreeNode(BiTreePtr&T){ 〃删除 T 指向的结点及其子树if(T!=NULL){
DelBiTreeNode(T->left);〃删除左子树Del BiTreeNode(T-> right);〃册 U 除右子树
if(Parent(T,T->data,P))〃双亲结点中指向该结点的指针置空if(p!=NULL){
if(P->left==T)P->left=NULL;if(P->right==T)P->nght=NULL;
)free(T);〃释放该结点
)returnOK;
)算法4-10删除二叉树中指定结点的算法
清空二叉树
该算法与删除指定结点的算法类似，即为删除根结点。算法描述如下：
StatusClearBiT ree(BiT reePtr&T){if(T!=NULL){
ClearBiTree(T-> left);〃册 U 除左子树ClearBiT ree(T- > right);〃删除左子树
free(T);〃释放根结点T=NULL;〃根指针置空
)
)算法4・11清空二叉树的算法
第三节线索二叉树
遍历二叉力实现了树型非线性结构的线性化，形成了二叉树结点的线性序列。为 了便于查找某个结点在线性序列中的前驱和后继信息，需要将二叉树线索化。
工、线索链表的数据类型
1、线索链表的数据类型
作为二叉树基本的操作，遍历二叉树是以一定规那么将二叉树中的结点排成一个线 性序列，这可看成是对树这种非线性结构进行线性化的操作，它使得每个结点(除 第一个和最后一个外)在这个线性序列中都有唯一的直接前驱和直接后继。当以 二叉链表作为存储结构时，只能较为方便地找到结点的左右孩子的信息，而不能 直接得到在结点的线性序列中的前驱与后继信息，这种信息只有在遍历的动态过 程中才能得到。为了能方便获得和利用某种遍历过程中的前驱与后继结点的信息, 可以在每个结点中设置两个指针分别保存它们，但我们注意到在二叉链表中有大 量的空指针(n个结点的二叉链表中有n+1个空链域)，我们可以充分利用这些 空链域来存放结点的前驱和后继的信息。具体来说，每个结点有左(右)子结点 时，其左(右)指针指向该子结点，或无左(右)子结点，那么其左(右)指针指 向其前驱(后继)结点。当然为了区分这些指针是指向其子结点还是指向其前驱 或后继结点，需要在结点的数据类型中增加两个标志域Itag、rtag,如图4.11 所示。以这种结点类型构成的二叉链表作为二叉树的存储结构，叫做线索链表， 其中指向结点前驱或后继的指针称为线索，加上线索的二叉树称为线索二叉树。 其中：
而以，线索二叉树结点的存储结构为：
typedefenum{Link,Thread}PTag; //Link==0：指针，Thread==l：线索 typedefstructBiThrNode{
ElemType data;
structBiThrNode *left,*right;〃左右孩子指针
PTagltag,rtag; 〃左右标志
}BiThrNode,*BiThrTree;
2、二叉树的中序线索化算法
2、二叉树的中序线索化算法
这个过程实际上就是将已经建立好的二叉链表中的空指针改为指向前驱或者后 继的线索。由于在二叉树的遍历过程中，我们可以得到结点的前驱或后继的信息, 因此，线索化的过程即为在遍历过程中修改空指针的过程。为了能在遍历过程中 记录访问结点的先后关系，我们附设一个全局变量指针pre始终指向刚刚访问过 的结点。假设指针指向当前访问的结点，那么pre指向它的前驱，而当前访问的结点 又是pre的后继。pre的初值为NULL。二叉树的中序线索化算法如下所示： StatusInOrderThreading(BiThrTree&T){
〃中序遍历二叉树T,并将其中序线索化，T指向树或子树的根结点。
P=T； if(P){ InOrderThreading(T->left);〃左子树线索化
if(!p->left){p->ltag=Thread;p->left=pre;} 〃前驱线索标记 if(pre&&!pre->right){pre->rtag=Thread;pre->right=p;} 〃pre为全局变量，初值为NULL；后继线索标记 pre=p;//pre始终指向前驱
InOrderThreading(T->right);〃右子树线索化
) returnOK;
}//InOrderThreading
算法4-13二叉树的中序线索化算法
3、中序线索二叉树的遍历算法
3、中序线索二叉树的遍历算法
在线索二叉树上进行遍历，只需要从序列的第一个结点开始访问，然后通过依次 寻找结点的后继进行遍历，当后继为空时，遍历即可结束。当然，线索二叉树总 是与某种遍历次序相关的，我们下面主要以中序遍历为主来考虑线索二叉树。 以图4.12为例，树中所有叶子结点的左、右链是线索，此时，右链域直接指示 了结点的后继，如结点g的后继为结点b。树中所有存在右孩子结点的右链均为 指针，那么无法直接得到该结点后继的信息。但是，根据中序遍历的规那么，该结点 的后继应是遍历其右子树时访问的第一个结点，即为该结点的右子树中最左下的 结点。例如，找结点a的后继，首先应沿着其右指针，找到它的右孩子结点c, 然后，顺着左指针一直往下，直到左标志为1时，意味着该结点无左子结点，即 该结点为a的后继，在图中是结点e。
根据如上所述，那么遍历中序线索二叉树的算法为：
StatusInOrderTaverse_Thr(BiThrTreeT,Status(*visit)(ElemTypee)){
〃T指向根结点，遍历市序线索二叉树
p=T;〃p指向根结点
while(p!=NULL){〃空树或遍历结束时，p==NULL
while(p->ltag==Link)p=p->left;
if(!visit(p->data))returnERROR;〃访问其左子树为空的结点
while(p->rtag==Thread&&p->right!=NULL){
p=p->right;visit(p->data); 〃访问后继结点
)
p=p->right;
)
returnOK;
}//InOrderT raverse_Thr
算法4-12中序线索二叉树的遍历算法
由此算法可以看出，对于中序线索二叉树的遍历，虽然时间复杂度为0(n),但 是算法的实际频数要比二叉链表的递归遍历算法低，而且不需要设栈。因此，假设 在某程序中所使用的二叉树经常需要遍历或查找结点在遍历所得线性序列中的 前驱和后继，那么应采用线索链表作为存储结构。
第四节树和森林
为了便于树的操作，通常将树转化为二叉树。本节讨论树的表示及基本的遍历操 作，并说明树、森林与二叉树的转化关系。
工、一般树转化成二叉树的规那么
2、森林转化成二叉树的规那么
2、森林转化成二叉树的规那么
任何一棵树都能按照一定的方式表示成二叉树，这样对树的计算机表示和操作等, 只要利用二叉树即可。一般树转化为二叉树的规那么为：
(1) 一般树的根对应二叉树的根；
(2)对树中任意结点，转化为二叉树的结点后，该结点原最左边的孩子结点作 为转化后它的左孩子结点，该结点原右边相邻的第一个兄弟结点作为转化后它的 右孩子结点，并依此类推。例如，设它的孩子结点依次为Tsi,Ts2,…，兄弟结点 依次为TB1,TB2,…，那么对应二叉树时，该结点的左孩子为Tsi,右孩子为TB1, Tsi的右孩子结点为Ts2, TB1的右孩子结点为TB2。
这样树中任一结点的子结点对应二叉树中结点的左子树根结点及沿着该子结点 的右分支路径至末端的各结点，显然这样转化的二叉树根结点无右子树，这是根 结点没有兄弟结点的必然结果。图4.16给出了一个具体的树转化成二叉树的例 子。
如果把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟结点，那么同样可 推导出森林和二叉树的转化。
森林转化成二叉树的规那么是：
(1)假设森林为空，那么对应的二叉树为空；
(2)假设森林非空，将森林中所有的树按照规那么转化为二叉树；
(3)设置一个虚拟根结点，该结点的子树从左到右依次为森林中从左到右的树， 即将所有的二叉树连接到虚拟根结点上；
(4)将这棵树按照规那么转化为二叉树(实际仅需一层操作，即原各棵树的根结 点按照兄弟结点的规那么进行转化，在此过程中各根结点带上原子树一起移动)；
(5)去掉虚拟根结点，那么二叉树的根结点为原第一棵树的根结点。
二叉树转化成森林的规那么是：
（1）假设二叉树为空，那么对应的森林为空；
（2）假设二叉树非空，那么对应的森林中第一棵树的根结点为二叉树的根结点，根 结点的子树森林是由二叉树的左子树转化而成的森林；森林中除第一棵树之外其 余树组成的森林是由二叉树的右子树转化而成的森林。
3、森林的遍历策略
3、森林的遍历策略
有两种次序遍历树的方法：一种是先根（次序）遍历树，另一种是后根（次序）遍历 树。前者先访问树的根结点，然后依次先根遍历根结点的每棵子树；后者那么是先 依次后根遍历每棵子树，然后再访问根结点。
按照森林和树相互递归的定义，可以得到森林的两种遍历方法：
L先序遍历森林
假设森林非空，那么可按下述规那么对其进行遍历：
（1）访问森林中第一棵树的根结点；
（2）先序遍历第一棵树中根结点的子树森林；
（3）先序遍历除去第一棵树之后剩余的树构成的森林。
2. 中序遍历森林
假设森林非空，那么可按下述规那么对其进行遍历：
（1）中序遍历森林中第一棵树的根结点的子树森林；
（2）访问第一棵树的根结点；
（3）中序遍历除去第一棵树之后剩余的树构成的森林。
根据前面讨论的森林和二叉树的转化的规那么，当森林转化为二叉树时，其第一棵 树的子树森林转化成左子树，剩余树的森林转化成右子树，那么上述森林的先序和 中序遍历即为其对应的二叉树的先序和中序遍历。因此，当以二叉链表作树的存 储结构时，树的先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历的算法 实现之。
第五节赫夫曼树及其应用
赫夫曼树（HuffmanTree）,又称最优树，是一类带权路径长度最短的二叉树, 在数据远程通信、数据压缩存储等方面有着广泛的应用。本节对赫夫曼树定义、 构造及赫夫曼树的应用进行讨论。
1、赫夫曼树
1、赫夫曼树
赫夫曼树
n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树称作 最优二叉树或赫夫曼树。因为构造这种树的算法最早是由赫夫曼于1952年提出 的，所以被称之为赫夫曼树。
例如，有四个叶子结点a,b,c,d,分别带权为8, 3, 4, 2,由它们构成的三棵不 同的二叉树（当然还有其它许多种）分别如图4.18（a）、（b）、（c）所示。
每一棵二叉树的带权路径长度WPL分别为：
（a）WPL=8x2+3x2+4x2+2x2=34
（b）WPL=3xl+2x2+4x3+8x3=43
(c)WPL=8xl+4x2+2x3+3x3=31
其中(c)树的WPL最小，可以验证，此树就是赫夫曼树，即其带权路径长度在所 有带权为8, 3, 4, 2的4个叶子结点构成的二叉树中居最小。
由此可以看出，根据n个带权叶子结点所构成的二叉树中，满二叉树或完全二叉 树不一定是最优二叉树。权值越大的结点离根越近的二叉树才是最优二叉树。
2、赫夫曼树构造规那么与算法
2、赫夫曼树构造规那么与算法
最优二叉树的构造算法是由赫夫曼提出的，所以称之为赫夫曼算法，具体表达如 下：
(1)给定n个权值{wl,w2,…,wn},对应n个结点，构成具有n棵二叉树的森林 F={Tl,T2,..,Tn},其中每棵二叉树Ti (lWiWn)都只有一个权值为wi的根结点， 其左右子树均为空。
(2)在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且 置新树的根结点的权值为其左、右子树上根结点的权值之和。
(3)从F中删除构成新树的那两棵树，同时把新树加入F中。
(4)重复(2)和(3),直到F中只含有一棵树为止，此树就是赫夫曼树。
根据上述构造赫夫曼树的方法可以写出相应的算法，具体如下：
BiTreePtrCreatHuffman(ElemTypee[]zintn){
〃根据数组e中n个权值建立一棵赫夫曼树，函数返回该树的根指针
a=(BiTreePtr*)malloc(n*sizeof(BiTreePtr)); 〃动态申请一个由 a 指向的指针数组 for(i=0;i<N;i++){
〃初始化指针数组a,使每个指针元素指向数组e中对应元素的结点
a[i]=(BiTreePtr)malloc(sizeof(BiTreeNode));
a[i]->data=e[i];a[i]->left=a[i]->right=NULL;
)
for(i=l;i<N;i++){
〃通过循环建立赫夫曼树
//tl表示具有最小权值根结点的下标，t2表示具有次小权值根结点的下标
for0=O;j<N;j++){
〃让tl初始指向森林中第一棵树，t2初始指向森林中第二棵树
if(a[j]!=NULL&&tl==-l){tl=j;continue;}
if (a [j ]!=N U LL){ t2=j; b rea k;}
)
for0=t2;j<N;j++){
〃从a中求出最小权值树和次小权值树
if(a[j]!=NULL){
if(a[j]->data<A[Tl]->data){t2=tl;tl=j;}
elseif(a[j]->data<A[T2]->data)t2=j;
)
)
〃由最小权值树和次最小权值树建立一棵新树，p指向树根结点
p=(BiTreePtr)malloc(sizeof(BiTreeNode));
p->data=a[tl]->data+a[t2]->data;p->left=a[tl];p->right=a[t2];
a[tl]=p;a[t2]=NULL;〃将指向新树的指针赋给a指针数组中tl位置，t2位置置为空
)free(a);
returnp;
)
算法4-14赫夫曼树的构造算法
假设仍采用图中的四个带权叶子结点来构造一棵赫夫曼树，按照上述算法，其构 造过程如图4.19所示。其中(d)就是最后生成的赫夫曼树，它的带权路径长度为 31,由此可知,图4.18(c)是一棵赫夫曼树。
在构造赫夫曼树的过程中，每次由两棵权值最小的树生成一棵新树时，新树的左 子树和右子树可以任意安排，这样将会得到具有不同结构的多个赫夫曼树，但它 们都具有相同的带权路径长度。为了使得到的赫夫曼树的结构尽量唯一，通常规 定生成的赫夫曼树中每个结点的左子树根结点的权小于等于右子树根结点的权。 上述赫夫曼树的构造过程就是遵照这一规定进行的。
3、赫夫曼编码算法3、赫夫曼编码算法
voidHuffManCoding(BiTreePtrT,intlen){〃根据T所指向的赫夫曼树输出每个结点的编码，len初值为0
staticinta[10];〃通过静态数组存储编码if(T!=NULL){
if(T->left==NU LL&&T- > rig ht ==N U LL){〃输出叶子结点的编码序列
printf("\n权值为％d的结点的编码：〃,T->data);
for(i=0;i<LEN;i++)a[i]);
)
else{
〃访问左右子树，并输出编码
a[len]=0;HuffManCoding(T->leftJen+l); a[len]=l;HuffManCoding(T->right,len+l);
算法4・15赫夫曼编码的算法
例如，假设电文中只使用a,b,c,d这四种字符，出现的频率分别为8, 3, 4, 2。 由这些字符构成的赫夫曼树如图4.19(d)所示，那么a,b,c,d这四个字符的赫夫曼编 码(见图4.20)依次是：
0, 111, 10, 110
电文的最短传送长度为：(n表示电文中使用的字符种数，wi和li分别表示对应 字符在电文中的出现频率和编码长度。)
(2) _假设D中元素个数大于1,对于任意的数据元素aj£D且心2,存在唯一的数据 元素 ai£D,有vA,aj>£H；假设D中元素个数大于1,对于任意的数据元素dj£D,存在k个(kNO)数据元 素 aeD且泛j,有vaj,a>£H；
(3) 对于任意的数据元素访£D且a2,存在DjD,Dj={ |eElemSetzk=l,2,...zm,m>0},有唯一鬲 Pj={v,这
个集合Pj表示从根结点到结点司的一条路径。
基本操作P：
InitTree(&T);操作结果：构造空树T。
CreateT ree(&T,tree);初始条件：tree给出T的表示形式。
操作结果：按tree构造T。
TreeEmpty(T);初始条件：树T存在。
操作结果：假设T为空树，贝I」返回TRUE,否那么返回FALSE。
TreeDepth(T);初始条件：树T存在。
操作结果：返回T的深度。
Root(T);初始条件：树T存在。
操作结果：返回T的根。
Value(Tze);初始条件：树T存在，e是需寻找的结点的值。
操作结果：假设找到该结点，那么函数返回TRUE,否那么返回FALSE。
Assign(Tze,value);初始条件：树T存在，e是需寻找的结点的值。
操作结果：假设找到该结点