数据结构万扣树

《数据结构万扣树》由会员分享，可在线阅读，更多相关《数据结构万扣树（87页珍藏版）》请在金锄头文库上搜索。

1、第三章第三章 树树数据结构数据结构:n 线性结构线性结构(线性表线性表, 栈栈,队列等队列等)n 非线性结构非线性结构: 至少存在一个数据元至少存在一个数据元素有不止一个直接前驱或后继素有不止一个直接前驱或后继(树树, 图等图等)3.1 树的定义树的定义一一. .树的定义树的定义 树是树是n n个数据元素的有限集个数据元素的有限集( (记为记为T)T)，对，对任意一棵树任意一棵树T T有：有： 存在唯一一个称为存在唯一一个称为根根的数据元素；的数据元素； 当当n n1 1时，其它数据元素可分为时，其它数据元素可分为m(mm(m0) 0) 个互不相交的有限集个互不相交的有限集T T1 1,T,T

2、2 2,T,Tm m，其中每，其中每个集合个集合T Ti i(i=1,2,(i=1,2,m),m)本身又是一棵树，并本身又是一棵树，并称树称树T Ti i是根的是根的子树子树。3.1 树的定义树的定义二二. 树的表示形式树的表示形式 倒悬树倒悬树。是最常用的表示形式，如图是最常用的表示形式，如图6-1(b)。 嵌套集合嵌套集合。是一些集合的集体，对于任何两个集是一些集合的集体，对于任何两个集合，或者不相交，或者一个集合包含另一个集合。图合，或者不相交，或者一个集合包含另一个集合。图6-2(a)是图是图6-1(b)树的嵌套集合形式。树的嵌套集合形式。 广义表形式广义表形式。图图6-2(b)是树的

3、广义表形式。是树的广义表形式。 凹入法凹入法表示形式。表示形式。见见P120 树的表示方法的多样化说明了树结构的重要性。树的表示方法的多样化说明了树结构的重要性。3.1 树的定义树的定义A AB BD DC CE EG GF FH HI IM MJ JN NK KL L(a)(a) 一般的树一般的树(b) 嵌套集合嵌套集合形式形式H HI IJ JD DF FB BK KL LE EC CM MN NG GA A(c) (c) 广义表广义表形式形式A(B(E(K,L),F),C(G(M,N),D(H,I,J)A(B(E(K,L),F),C(G(M,N),D(H,I,J)）3.1 树的定义树的定

4、义三三. .树的基本术语树的基本术语1. 1. 树的结点树的结点: :包含一个包含一个DEDE和指向其子树的所有分支和指向其子树的所有分支; ;2. 2. 结点的度结点的度: :一个结点拥有的子树的个数；度为零的结点称为一个结点拥有的子树的个数；度为零的结点称为叶结点叶结点; ;3. 3. 树的度树的度: :树中所有结点的度的最大值树中所有结点的度的最大值Max(D(I)Max(D(I) 含义含义: :树中最大分支数为树的度树中最大分支数为树的度4. 4. 结点的层次及树的深度结点的层次及树的深度: :根为第一层根为第一层, ,根的孩子为第二层根的孩子为第二层, ,若若某结点为第某结点为第k

5、k层层, ,则其孩子为则其孩子为k+1k+1层；层； 树中结点的最大层次称为树的深度或高度；树中结点的最大层次称为树的深度或高度；5.5.森林森林: :是是m(m=0)m(m=0)棵互不相的树的集合；棵互不相的树的集合； 森林与树概念相近森林与树概念相近, ,相互很容易转换；相互很容易转换；3.1 树的定义树的定义1层2层4层3层depth= 4DACBIJHGFEMLKheight= 43.2 二叉树二叉树一一. . 二叉树的概念二叉树的概念 二叉树是结点数为二叉树是结点数为0 0或每个结点最多只有或每个结点最多只有左右两棵子树的树。二叉树是一种特殊的树左右两棵子树的树。二叉树是一种特殊的树

6、结构，它的特点是：结构，它的特点是：每个结点最多只有两棵子树，即不存在结每个结点最多只有两棵子树，即不存在结点度大于点度大于2 2的结点；的结点；子树有左右之分，不能颠倒。子树有左右之分，不能颠倒。问题：二叉树和度为问题：二叉树和度为2的树有何不同？的树有何不同？3.2 二叉树二叉树二二. . 二叉树的性质二叉树的性质性质性质1 1. . 在二叉树的第在二叉树的第i i层上至多有层上至多有2 2i-1i-1个结点个结点(i1)(i1)。证明证明: : 用归纳法用归纳法1. 1. 当当i=1,i=1,即第一层只有一个根结点即第一层只有一个根结点, , 显然显然 2 2i-1i-1= = 2 20

7、 0=1=1成立成立2. 2. 假设对所有的假设对所有的j j上述性质成立上述性质成立, , 即第即第j j层上至多有层上至多有2 2j-1j-1个结点个结点3. 3. 要证明要证明i=j+1i=j+1时时, ,命题也成立。命题也成立。 由归纳假设：第由归纳假设：第j j层上至多有层上至多有2 2j-1j-1个结点，又由于二叉树每个个结点，又由于二叉树每个结点的度最大为结点的度最大为2 2，所以第，所以第j+1j+1层上结点总数最多为第层上结点总数最多为第j j层上最大层上最大结点数的结点数的2 2倍。即倍。即2*22*2j-1j-1=2=2(j+1)-1(j+1)-13.2 二叉树二叉树性质

8、性质2 2. . 深度为深度为k k的二叉树至多有的二叉树至多有2 2k k-1-1个结点个结点(k1)(k1)。（深度一定，二叉树的最大结点数也确定）（深度一定，二叉树的最大结点数也确定）证明：证明： 深度为深度为k k的二叉树的最大结点数是二叉树的二叉树的最大结点数是二叉树中每层上结点的最大数之和。即中每层上结点的最大数之和。即 k k （第（第i i层上结点的最大数）层上结点的最大数） i=1 i=1 k k=2=2i-1 i-1 =1+2+2=1+2+22 2+ +2+2k-1k-1=2=2k k-1(-1(等比级数求和等比级数求和) ) i=1i=13.2 二叉树二叉树性质性质3 3

9、. . 二叉树中二叉树中, ,终端结点数终端结点数n n0 0与度为与度为2 2的结点数的结点数n n2 2有有如下关系如下关系: : n n0=0=n n2 2+1+1证明证明: :设二叉树中度为设二叉树中度为i i的结点数为的结点数为n ni i, , 则则 结点总数结点总数n=nn=n0 0+n+n1 1+n+n2 2 除根结点外除根结点外, ,每个结点都是另一结点的孩子每个结点都是另一结点的孩子 孩子数孩子数=n-1=n-1； 度为度为i i（i=0i=0，1 1，2 2）的结点，有）的结点，有i i个孩子。个孩子。 孩子数孩子数=2n=2n2 2+n+n1 1 n-1= 2n n-1

10、= 2n2 2+n+n1 1 即即 n n0 0+n+n1 1+n+n2 2-1=2n-1=2n2 2+n+n1 1 故故 n n0 0= = n n2 2+1 +1 3.2 二叉树二叉树满二叉树满二叉树: :深度为深度为k k，且有，且有2 2k k-1-1个结点的二叉树。个结点的二叉树。特点：（特点：（1 1）每一层上结点数都达到最大）每一层上结点数都达到最大 （2 2）度为）度为1 1的结点数的结点数n n1 1=0=0 结点层序编号方法：从根结点起从上到下逐层结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点进行连续编号。（层内从左到右）对二叉树的结点进行连续编号。

11、1237654k=3n=23-1=7 满二叉树满二叉树 3.2 二叉树二叉树完全二叉树完全二叉树: :深度为深度为k k，结点数为，结点数为n n的二叉树，的二叉树，当且仅当每个结点的编号都与相同深度的满二当且仅当每个结点的编号都与相同深度的满二叉树中从叉树中从1 1到到n n的结点一一对应时，称为完全二的结点一一对应时，称为完全二叉树。叉树。452131237654k=3n=23-1=7 满二叉树满二叉树 完全二叉树完全二叉树3.2 二叉树二叉树LHLH2 2=0=0RHRH2 2=1=11324653241LH1=3RH1=1LH1 -RH1=2 非完全二叉树非完全二叉树 非完全二叉树非完

12、全二叉树LH2-RH2=0-1=-13.2 二叉树二叉树性质性质4.4. 结点数为结点数为n n的完全二叉树，其深度为的完全二叉树，其深度为 loglog2 2n n + 1+ 1证明：设深度为证明：设深度为k k， 则则 由性质由性质2 2和完全二叉树定义有：和完全二叉树定义有： 结点数结点数n n满足：满足：2 2k-1k-1-1-1n2n2k k-1-1 或写为或写为2 2k-1k-1nn2 2k k 于是有：于是有：k-1logk-1log2 2n nk k 因为因为 k-1k-1和和k k均为整数均为整数 显然有显然有loglog2 2n n=k-1, =k-1, 故故 k=k=lo

13、glog2 2n n + 1+ 13.2 二叉树二叉树性质性质5. 5. 在按层序编号的在按层序编号的n n个结点的完全二叉树中，个结点的完全二叉树中，任意一结点任意一结点i(1in)i(1in)有：有： i=1i=1时，结点时，结点i i是树的根；否则是树的根；否则(i1)(i1)，结点，结点i i的的双亲为结点双亲为结点i/2i/2。 2i2in n时，结点时，结点i i无左孩子，为叶结点；否则，无左孩子，为叶结点；否则，结点结点i i的左孩子为结点的左孩子为结点2i2i。 2i+12i+1n n时，结点时，结点i i无右孩子；否则，结点无右孩子；否则，结点i i的的右孩子为结点右孩子为结

14、点2i+12i+1。3.2 二叉树二叉树三、二叉树的存储结构三、二叉树的存储结构 顺序存储结构顺序存储结构用一组地址连续的存储单元，以层序顺序存放二叉树用一组地址连续的存储单元，以层序顺序存放二叉树的数据元素，结点的相对位置蕴含着结点之间的关系。的数据元素，结点的相对位置蕴含着结点之间的关系。 完全二叉树完全二叉树DCGFEBA bt3的双亲为的双亲为3/23/2=1， 即在即在b t1中；中； 其左孩子在其左孩子在bt2i=bt6中；中； 其右孩子在其右孩子在bt2i+1=bt7中。中。1 2 3 4 5 6 7 8 9 10 11 A B C D E F G 0 0 0 0bt3.2 二叉

15、树二叉树一般二叉树也按完全二叉树形式存储一般二叉树也按完全二叉树形式存储,没结点处用没结点处用0表示表示D 二叉树二叉树CGFEBA1 2 3 4 5 6 7 8 9 10 11 A B C D E 0 0 0 0 F G 0 0 0 0这种存储结构适合于完全二叉树，既不浪费存储空这种存储结构适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置、以及结点的双间，又能很快确定结点的存放位置、以及结点的双亲和左右孩子的存放位置，但对一般二叉树，可能亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的浪费。造成存储空间的浪费。3.2 二叉树二叉树例如例如，深度为深度为k k，且只有，

16、且只有k k个结点的右单枝树个结点的右单枝树(每个非叶结点只有右孩子每个非叶结点只有右孩子) )，需，需2 2k k-1-1个单元，个单元，即有即有2 2k k-1-k-1-k个单元被浪费。个单元被浪费。1k3.2 二叉树二叉树 链式存储结构链式存储结构 设计不同的结点结构，可以构成不同的链式设计不同的结点结构，可以构成不同的链式存储结构。常用的有：存储结构。常用的有：n 二叉链表二叉链表n 三叉链表三叉链表n 线索链表线索链表 用空链域存放指向前驱或后继的线用空链域存放指向前驱或后继的线索索 3.2 二叉树二叉树D 二叉树二叉树CEBAACBDE二叉链表二叉链表leftChild data

17、rightChilddataleftChildrightChild用于二叉树存储的链表结构，常见的有二叉链表和三叉链表用于二叉树存储的链表结构，常见的有二叉链表和三叉链表 二叉链表二叉链表的每个结点的结构描述如下：的每个结点的结构描述如下：struct BTNode int data; /数据域数据域 BTNode *lch; /左指针域左指针域 BTNode *rch; /右指针域右指针域 3.2 二叉树二叉树三叉链表三叉链表的每个结点的结构描述如下：的每个结点的结构描述如下：struct node3 int data; /数据域数据域 node3 *lch, *par， *rch; /pa

18、r是双亲指针域是双亲指针域 ;leftChild data parent rightChildparentdataleftChildrightChild(2) 二叉树的链式存储形式二叉树的链式存储形式 例有一棵一般的二叉树，如图例有一棵一般的二叉树，如图6-8(a)所示。以二叉链所示。以二叉链表和三叉链表方式存储的结构图分别如图表和三叉链表方式存储的结构图分别如图6-8(b) 、 6-8(c)所示。所示。图图6-8 6-8 二叉树及其二叉树及其链式存储结构链式存储结构(a) (a) 二叉树二叉树a af fe ed dc cb bg g(c) (c) 三三叉链表叉链表 a a b b c c

19、d d e e f f g g T T(b) (b) 二二叉链表叉链表 a a b b c c d d e e g g f f T T3.2 二叉树二叉树性质性质6 6. . 含有含有n n个结点的二叉链表中，有个结点的二叉链表中，有n+1n+1个空链域。个空链域。证明：空链域数证明：空链域数=2n=2n0 0+n+n1 1 因为因为 n=nn=n0 0+n+n1 1+n+n2 2 （1 1） 又有又有 n n0 0=n=n2 2+1 +1 即即 -1= n-1= n2 2-n-n0 0 （2 2） （1 1）- -（2 2）得）得 n+1= 2nn+1= 2n0 0+n+n1 1 故空链域数

20、故空链域数=n+1=n+13.3 遍历二叉树遍历二叉树二叉树最主要、最基本的运算是遍历。二叉树最主要、最基本的运算是遍历。遍历二叉树是指以一定的次序访问二叉树中的每个结点，是指以一定的次序访问二叉树中的每个结点，并且每个结点仅被访问一次。并且每个结点仅被访问一次。访问结点是指对结点进行各种操作的简称。是指对结点进行各种操作的简称。例如，查询结点数据域的内容，或输出它的值，或找出结例如，查询结点数据域的内容，或输出它的值，或找出结点位置，或是执行对结点的其他操作。点位置，或是执行对结点的其他操作。遍历二叉树的过程遍历二叉树的过程实质实质是把二叉树的结点进行线性排列的是把二叉树的结点进行线性排列的

21、过程。过程。3.3 遍历二叉树遍历二叉树二叉树的遍历就是按某种次序访问树中的结二叉树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。点，要求每个结点访问一次且仅访问一次。设设访问根结点访问根结点记作记作 V 遍历根的左子树遍历根的左子树记作记作 L 遍历根的右子树遍历根的右子树记作记作 R则可能的遍历次序有则可能的遍历次序有 前序前序 VLR 中序中序 LVR 后序后序 LRV3.3 遍历二叉树遍历二叉树对于二叉树的遍历，分别讨论递归遍历算对于二叉树的遍历，分别讨论递归遍历算法和非递归遍历算法。递归遍历算法具有法和非递归遍历算法。递归遍历算法具有非常清晰的结构，但初学者往

22、往难以接受非常清晰的结构，但初学者往往难以接受或怀疑，不敢使用。实际上，递归算法是或怀疑，不敢使用。实际上，递归算法是由系统通过使用堆栈来实现控制的。而非由系统通过使用堆栈来实现控制的。而非递归算法中的控制是由设计者定义和使用递归算法中的控制是由设计者定义和使用堆栈来实现的。堆栈来实现的。3.3 遍历二叉树遍历二叉树3.3.1 先序遍历二叉树先序遍历二叉树1 递归算法递归算法算法的递归定义是：算法的递归定义是： 若二叉树为空，则遍历结束；否则若二叉树为空，则遍历结束；否则 访问根结点；访问根结点； 先序遍历左子树先序遍历左子树(递归调用本算法递归调用本算法)； 先序遍历右子树先序遍历右子树(递

23、归调用本算法递归调用本算法)。3.3.1 遍历二叉树遍历二叉树先序遍历的递归算法先序遍历的递归算法void PreorderTraverse(void PreorderTraverse(BTNode *TBTNode *T) ) if ( T != NULL ) if ( T != NULL ) visit( T-data ) ; visit( T-data ) ; /* /* 访问根结点访问根结点 * */ / PreorderTraverse( PreorderTraverse(T-LchildT-Lchild) ;) ; PreorderTraverse( PreorderTravers

24、e(T-RchildT-Rchild) ; ) ; 说明说明：visit()visit()函数是访问结点的数据域，其要求视函数是访问结点的数据域，其要求视具体问题而定。树采用二叉链表的存储结构，用指针变具体问题而定。树采用二叉链表的存储结构，用指针变量量T T来指向。来指向。3.3.1 遍历二叉树遍历二叉树3.3.1 遍历二叉树遍历二叉树/ /f fe e- -d dc cb b* *a a+ +3.3.1 遍历二叉树遍历二叉树2 非递归算法非递归算法设设T是指向二叉树根结点的指针变量，非递归算法是：是指向二叉树根结点的指针变量，非递归算法是：若二叉树为空，则返回；否则，令若二叉树为空，则返回

25、；否则，令p=T； 访问访问p所指向的结点；所指向的结点； q=p-Rchild ，若，若q不为空，则不为空，则q进栈；进栈； p=p-Lchild ，若，若p不为空，转不为空，转(1)，否则转，否则转(4)； 退栈到退栈到p ，转，转(1)，直到栈空为止。，直到栈空为止。算法实现：算法实现：#define MAX_NODE 50void PreorderTraverse( BTNode *T) BTNode *StackMAX_NODE ,*p=T, *q ;int top=0 ;if (T=NULL) cout data ) ; q=p-Rchild ; if ( q!=NULL ) st

26、ack+top=q ; p=p-Lchild ; if (p=NULL & top0) p=stacktop ; top- ; while (p!=NULL) ;3.3.2 中序遍历二叉树中序遍历二叉树1 递归算法递归算法算法的递归定义是：算法的递归定义是： 若二叉树为空，则遍历结束；否则若二叉树为空，则遍历结束；否则 中序遍历左子树中序遍历左子树(递归调用本算法递归调用本算法)； 访问根结点；访问根结点； 中序遍历右子树中序遍历右子树(递归调用本算法递归调用本算法)。3.3.2 中序遍历二叉树中序遍历二叉树中序遍历的递归算法中序遍历的递归算法void InorderTraverse(void

27、 InorderTraverse(BTNode *TBTNode *T) ) if ( T != NULL ) if ( T != NULL ) InorderTraverse( InorderTraverse(T-LchildT-Lchild) ;) ; visit(T-data) ; visit(T-data) ; /* /* 访问根结点访问根结点 * */ / InorderTraverse( InorderTraverse(T-RchildT-Rchild) ;) ; /*/*图图6-8(a) 6-8(a) 的二叉树，输出的次序是：的二叉树，输出的次序是： cbegdfa */cbeg

28、dfa */3.3.2 中序遍历二叉树中序遍历二叉树2 非递归算法非递归算法设设T是指向二叉树根结点的指针变量，非递归算法是：是指向二叉树根结点的指针变量，非递归算法是： 若二叉树为空，则返回；否则，令若二叉树为空，则返回；否则，令p=T 若若p不为空，不为空，p进栈，进栈， p=p-Lchild ； 否则否则(即即p为空为空)，退栈到，退栈到p，访问，访问p所指向的结点；所指向的结点； p=p-Rchild ，转，转(1)；直到栈空为止。直到栈空为止。算法实现：算法实现：#define MAX_NODE 50void InorderTraverse( BTNode *T) BTNode *S

29、tackMAX_NODE ,*p=T ; int top=0 , bool=1 ; if (T=NULL) printf(“ Binary Tree is Empty!n”) ; else do while (p!=NULL) stack+top=p ; p=p-Lchild ; if (top=0) bool=0 ; else p=stacktop ; -top ; visit( p-data ) ; p=p-Rchild ; while (bool!=0) ; 3.3.3 后序遍历二叉树后序遍历二叉树1 递归算法递归算法算法的递归定义是：算法的递归定义是： 若二叉树为空，则遍历结束；否则若

30、二叉树为空，则遍历结束；否则 后序遍历左子树后序遍历左子树(递归调用本算法递归调用本算法)； 后序遍历右子树后序遍历右子树(递归调用本算法递归调用本算法) ； 访问根结点访问根结点 。后序遍历的递归算法后序遍历的递归算法void PostorderTraverse(void PostorderTraverse(BTNode *TBTNode *T) ) if (T!=NULL) if (T!=NULL) PostorderTraverse( PostorderTraverse(T-LchildT-Lchild) ;) ;PostorderTraverse(PostorderTraverse(T

31、-RchildT-Rchild) ; ) ; visit(T-data) ; visit(T-data) ; /* /* 访问根结点访问根结点 * */ / /*/*图图6-8(a)6-8(a) 的二叉树，输出的次序是：的二叉树，输出的次序是： cgefdba */cgefdba */遍历二叉树的算法中基本操作是访问结点，因此，无论遍历二叉树的算法中基本操作是访问结点，因此，无论是哪种次序的遍历，对有是哪种次序的遍历，对有n n个结点的二叉树，其时间复个结点的二叉树，其时间复杂度均为杂度均为O(n) O(n) 。3.3.3 后序遍历二叉树后序遍历二叉树 如图如图6-96-9所示的二叉树表示表达

32、式：所示的二叉树表示表达式：(a+b*(c-d)-(a+b*(c-d)-e/f)e/f)按不同的次序遍历此二叉树，将访问的结点按先后次序按不同的次序遍历此二叉树，将访问的结点按先后次序排列起来的次序是：排列起来的次序是： 其先序序列为：其先序序列为： -+a*b-cd/ef-+a*b-cd/ef 其中序序列为：其中序序列为： a+b*c-d-e/fa+b*c-d-e/f 其后序序列为：其后序序列为： abcd-*+ef/-abcd-*+ef/-/ /f fe e- -d dc cb b* *a a+ +图图6-9 表达式表达式 (a+b*(c-d)-e/f)二叉树二叉树3.3.3 后序遍历二叉

33、树后序遍历二叉树2 非递归算法非递归算法 在后序遍历中，根结点是最后被访问的。因此，在在后序遍历中，根结点是最后被访问的。因此，在遍历过程中，当搜索指针指向某一根结点时，不能立即遍历过程中，当搜索指针指向某一根结点时，不能立即访问，而要先遍历其左子树，此时根结点进栈。当其左访问，而要先遍历其左子树，此时根结点进栈。当其左子树遍历完后再搜索到该根结点时，还是不能访问，还子树遍历完后再搜索到该根结点时，还是不能访问，还需遍历其右子树。所以，此根结点还需再次进栈，当其需遍历其右子树。所以，此根结点还需再次进栈，当其右子树遍历完后再退栈到到该根结点时，才能被访问。右子树遍历完后再退栈到到该根结点时，才

34、能被访问。 因此，设立一个状态标志变量因此，设立一个状态标志变量tag ：0 0 ： 结点暂不能访问结点暂不能访问1 1 ： 结点可以被访问结点可以被访问tag=tag= 其次，设两个堆栈其次，设两个堆栈S S1 1、S S2 2 ，S S1 1保存结点，保存结点，S S2 2保存结保存结点的点的状态标志变量状态标志变量tag tag 。S S1 1和和S S2 2共用一个栈顶共用一个栈顶指针。指针。 设设T T是指向根结点的指针变量，非递归算法是：是指向根结点的指针变量，非递归算法是：若二叉树为空，则返回；否则，令若二叉树为空，则返回；否则，令p=Tp=T； 第一次经过根结点第一次经过根结点

35、p p，不访问：，不访问： p p进栈进栈S1 S1 ， tag tag 赋值赋值0 0，进栈，进栈S2S2，p=p-p=p-Lchild Lchild 。 若若p p不为空，转不为空，转(1)(1)，否则，取状态标志值，否则，取状态标志值tag tag ： 若若tag=0tag=0：对栈：对栈S1S1，不访问，不出栈；修改，不访问，不出栈；修改S2S2栈栈顶元素值顶元素值(tag(tag赋值赋值1) 1) ，取，取S1S1栈顶元素的右子树，即栈顶元素的右子树，即p=S1top-Rchild p=S1top-Rchild ，转，转(1)(1)； 若若tag=1tag=1：S1S1退栈，访问该结

36、点；退栈，访问该结点；直到栈空为止。直到栈空为止。算法实现：算法实现：#define MAX_NODE 50#define MAX_NODE 50void PostorderTraverse( BTNode *T)void PostorderTraverse( BTNode *T) BTNode * BTNode *S S1 1 MAX_NODEMAX_NODE , ,*p=T ;*p=T ; int S2MAX_NODE , top=0 , bool=1 ; int S2MAX_NODE , top=0 , bool=1 ; if (T=NULL) if (T=NULL) cout“Bina

37、ry Tree is Empty!n”; coutLchild ; p=p-Lchild ; if (top=0) bool=0 ; if (top=0) bool=0 ; else if (S2top=0) p=S1top-Rchild ; S2top=1 ; else p=S1top ; top- ; visit( p-data ) ; p=NULL ; /* 使循环继续进行而不至于死循环使循环继续进行而不至于死循环 */ while (bool!=0) ;3.4 层次遍历二叉树层次遍历二叉树层次遍历二叉树，是从根结点开始遍历，按层次次序层次遍历二叉树，是从根结点开始遍历，按层次次序“自上

38、而下，从左至右自上而下，从左至右”访问树中的各结点。访问树中的各结点。为保证是按层次遍历，必须设置一个队列，初始化时为保证是按层次遍历，必须设置一个队列，初始化时为空。为空。设设T是指向根结点的指针变量，层次遍历非递归算法是指向根结点的指针变量，层次遍历非递归算法是：是： 若二叉树为空，则返回；否则，令若二叉树为空，则返回；否则，令p=T，p入队；入队； 队首元素出队到队首元素出队到p；访问访问p所指向的结点；所指向的结点； 将将p所指向的结点的左、右子结点依次入队。直所指向的结点的左、右子结点依次入队。直到队空为止。到队空为止。#define MAX_NODE 50void Levelord

39、erTraverse( BTNode *T) BTNode *QueueMAX_NODE ,*p=T ;int front=0 , rear=0 ;if (p!=NULL) Queue+rear=p; /* 根结点入队根结点入队 */while (frontdata ); if (p-Lchild!=NULL) Queue+rear=p-Lch; /* 左结点入队左结点入队 */ if (p-Rchild!=NULL) Queue+rear=p-Rch; /* 右结点入队右结点入队 */ 3.5 二叉树遍历算法的应用二叉树遍历算法的应用“遍历遍历”是二叉树最重要的基本操作，是是二叉树最重要的基

40、本操作，是各种其它操作的基础，二叉树的许多其它各种其它操作的基础，二叉树的许多其它操作都可以通过遍历来实现。如建立二叉操作都可以通过遍历来实现。如建立二叉树的存储结构、求二叉树的结点数、求二树的存储结构、求二叉树的结点数、求二叉树的深度等。叉树的深度等。3.5 二叉树遍历算法的应用二叉树遍历算法的应用1 1 二叉树的二叉链表创建二叉树的二叉链表创建 按满二叉树方式建立按满二叉树方式建立 ( (补充补充) ) 在此补充按满二叉树的方式对结点进行编号建立链在此补充按满二叉树的方式对结点进行编号建立链式二叉树。对每个结点，输入式二叉树。对每个结点，输入i i、chch。i i ： 结点编号，按从小到

41、大的顺序输入结点编号，按从小到大的顺序输入ch ch ： 结点内容，假设是字符结点内容，假设是字符 在建立过程中借助一个一维数组在建立过程中借助一个一维数组Sn Sn ，编号为，编号为i i的的结点保存在结点保存在SiSi中中。算法实现：算法实现：#define MAX_NODE 50struct BTNode char data ;struct BTNode *Lchild , *Rchild ; ;BTNode *Create_BTree(void) /* 建立链式二叉树，返回指向根结点的指针变量建立链式二叉树，返回指向根结点的指针变量 */ BTNode *T , *p , *sMAX_

42、NODE ; char ch ; int i , j ;while ( 1 ) cini ;if ( i=0 ) break ; /* 以编号以编号0作为输入结束作为输入结束 */else ch=getchar() ; p = new BTNode ; pdata=ch ; pLchild=pRchild=NULL ; si=p ; if ( i=1 ) T = p ; else j=i/2 ; /* j是是i的双亲结点编号的双亲结点编号 */ if (i%2=0) sj-Lchild=p ; else sj-Rchild=p ; return(T) ;3.5 二叉树遍历算法的应用二叉树遍历算

43、法的应用 按先序遍历方式建立按先序遍历方式建立对一棵二叉树进行对一棵二叉树进行“扩充扩充”，就可以得到有该二叉树所，就可以得到有该二叉树所扩充的二叉树。有两棵二叉树扩充的二叉树。有两棵二叉树T T1 1及其扩充的二叉树及其扩充的二叉树T T2 2如如图图6-106-10所示。所示。图图6-106-10 二叉树二叉树T T1 1及其扩充及其扩充二叉树二叉树T T2 2A AB BC CD DE EF FG G(a)(a) 二叉树二叉树T T1 1(b)(b) T T1 1的扩充的扩充二叉树二叉树T T2 2A AB BC CD DE EF FG G? ? ? ? ? ? ? ? ?3.5 二叉树

44、遍历算法的应用二叉树遍历算法的应用二叉树的扩充方法是：在二叉树中结点的每一个空链二叉树的扩充方法是：在二叉树中结点的每一个空链域处增加一个扩充的结点域处增加一个扩充的结点( (总是叶子结点，用方框总是叶子结点，用方框“”表示表示) )。对于二叉树的结点值：。对于二叉树的结点值： 是是charchar类型：扩充结点值为类型：扩充结点值为“？”； 是是intint类型：扩充结点值为类型：扩充结点值为0 0或或-1-1；下面的算法是二叉树的前序创建的递归算法，读入一下面的算法是二叉树的前序创建的递归算法，读入一棵二叉树对应的扩充二叉树的前序遍历的结点值序列。棵二叉树对应的扩充二叉树的前序遍历的结点值

45、序列。每读入一个结点值就进行分析：每读入一个结点值就进行分析： 若是扩充结点值：令根指针为若是扩充结点值：令根指针为NULLNULL； 若是若是( (正常正常) )结点值：动态地为根指针分配一个结点，结点值：动态地为根指针分配一个结点，将该值赋给根结点，然后递归地创建根的左子树和右将该值赋给根结点，然后递归地创建根的左子树和右子树。子树。#define NULLKY ?#define MAX_NODE 50struct BTNode char data ;struct BTNode *Lchild , *Rchild ;BTNode *Preorder_Create_BTree(BTNode

46、*T) /* 建立链式二叉树，返回指向根结点的指针变量建立链式二叉树，返回指向根结点的指针变量 */ char ch ; ch=getchar() ; getchar(); if (ch=NULLKY) T=NULL; return(T) ; 3.5 二叉树遍历算法的应用二叉树遍历算法的应用else T = new BTNode ;Tdata=ch ;Preorder_Create_BTree(T-Lchild) ;Preorder_Create_BTree(T-Rchild) ;return(T) ; 当希望创建图当希望创建图6-10(a)所示的二叉树时，输入的字符所示的二叉树时，输入的字符

47、序列应当是：序列应当是：ABD?E?G?CF?3.5 二叉树遍历算法的应用二叉树遍历算法的应用2 求二叉树的叶子结点数求二叉树的叶子结点数 可以直接利用先序遍历二叉树算法求二叉树的叶子结点可以直接利用先序遍历二叉树算法求二叉树的叶子结点数。只要将先序遍历二叉树算法中数。只要将先序遍历二叉树算法中vist()函数简单地进函数简单地进行修改就可以。行修改就可以。 (递归与非递归递归与非递归)#define MAX_NODE 50int search_leaves( BTNode *T) BTNode *StackMAX_NODE ,*p=T;int top=0, num=0;if (T!=NULL

48、) stack+top=p ; while (top0) p=stacktop- ; if (p-Lchild=NULL&p- Rchild=NULL) num+ ; if (p-Rchild!=NULL ) stack+top=p-Rchild; if (p-Lchild!=NULL ) stack+top=p-Lchild; return(num) ;3.5 二叉树遍历算法的应用二叉树遍历算法的应用3求二叉树的深度求二叉树的深度int Depth ( BTNode *T ) if ( T=NULL ) depthval = 0; else depthLeft = Depth( T-Lchi

49、ld ); depthRight = Depth( T-Rchild ); depthval = 1 + max( depthLeft, depthRight); return depthval; 3.5 二叉树遍历算法的应用二叉树遍历算法的应用3 求二叉树的深度求二叉树的深度 利用层次遍历算法可以直接求得二叉树的深度。利用层次遍历算法可以直接求得二叉树的深度。#define MAX_NODE 50int search_depth( BTNode *T) BTNode *StackMAX_NODE ,*p=T;int front=0 , rear=0, depth=0, level ;/* l

50、evel总是指向访问层的最后一个结点在队列的位置总是指向访问层的最后一个结点在队列的位置 */if ( T != NULL ) Queue+rear=p; /* 根结点入队根结点入队 */level=rear ; /* 根是第根是第1层的最后一个节点层的最后一个节点 */while (frontLchild!=NULL) Queue+rear=p-Lchild; /* 左结点入队左结点入队 */ if (p-Rchild!=NULL) Queue+rear=p-Rchild; /* 右结点入队右结点入队 */ if ( front=level ) /* 正访问的是当前层的最后一个结点正访问的是

51、当前层的最后一个结点 */ depth+ ; level=rear ; 3.6哈夫曼树的构造哈夫曼树的构造哈夫曼树（哈夫曼树（Huffman）树是一类带权路径长度最短的树）树是一类带权路径长度最短的树一、一、Huffman树（最优二叉树）树（最优二叉树）1、概念概念 两结点间的路径：从一个结点到另一个结点之间的分支两结点间的路径：从一个结点到另一个结点之间的分支 路径长度：路径上的分支数目路径长度：路径上的分支数目 树的路径长度：从根到每一结点的路径长度之和树的路径长度：从根到每一结点的路径长度之和2763415例例-为结点为结点1到到5之间的路径，其路之间的路径，其路径长度为径长度为2，树的

52、路径长度树的路径长度=l12 +l13+ l14 +l15+ l16 +l17 =1+1+2+2+2+2=103.6哈夫曼树的构造哈夫曼树的构造 完全二叉树是路径长度最短的二叉树。完全二叉树是路径长度最短的二叉树。 考虑带权时：设树中有考虑带权时：设树中有m个叶结点，每个叶结个叶结点，每个叶结点带一个权值点带一个权值W且根到叶结点且根到叶结点i的路径长度为的路径长度为 Li (=1，2， ，m），则），则树的带权路径长度树的带权路径长度为树中为树中所有叶结点的权值与路径长度的乘积的总和。所有叶结点的权值与路径长度的乘积的总和。 m即：即： kk k=13.6哈夫曼树的构造哈夫曼树的构造 例：例

53、：使使WPL最小的二叉树最小的二叉树称为最优二叉树称为最优二叉树 (Huffman 树树)完全二叉树完全二叉树dcab7 5 2 4 cdba2475WPLa=2*7+2*5+2*2+2*4 WPLb=7*3+5*3+2*1+4*2 =36 =463.6哈夫曼树的构造哈夫曼树的构造Huffman 树树WPLc=7*1+5*2+2*3+4*3 =35bdca7524（1）完全二叉树并）完全二叉树并不一定是不一定是Huffman树；树；（2）HT是权值越大是权值越大的越靠近根结点；的越靠近根结点；（3）HT不唯一，但不唯一，但WPL一定相等。一定相等。3.6哈夫曼树的构造哈夫曼树的构造2构造构造

54、Huffman树算法树算法(1) 以权值分别为以权值分别为W1,W2的个结点，构成的个结点，构成n棵二棵二叉树叉树T1,T2,Tn并组成森林并组成森林F=T1,T2,Tn,其中每棵其中每棵二叉树二叉树 Ti仅有一个权值为仅有一个权值为 Wi的根结点；的根结点；(2) 在在F中选取两棵根结点权值最小的树作为左右子树构造一中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和（根结点的权值点的权值之和（根结点的权值=左右孩子权值之和，叶结点的左右孩子权值之和，叶结点的权值权值= Wi）；）；

55、(3) 从从F中删除这两棵二叉树，同时将新二叉树加入到中删除这两棵二叉树，同时将新二叉树加入到F中中;(4) 重复重复(2)()直到直到F中只含一棵二叉树为止，这棵二叉树中只含一棵二叉树为止，这棵二叉树就是就是Huffman 树。树。3.6哈夫曼树的构造哈夫曼树的构造abcd7 5 2 4例例: F= abF= cd 7 5 6 2 4F= abcd116425F= abcd11642571873.6哈夫曼树的构造哈夫曼树的构造HT不唯一性不唯一性,可能出现在可能出现在:（1）构造新树时，左、右孩子未作规定。）构造新树时，左、右孩子未作规定。（2）当有多个权值相同的树，可作为候选树）当有多个权

56、值相同的树，可作为候选树时，选择谁未作规定。时，选择谁未作规定。3.6哈夫曼树的构造哈夫曼树的构造1 Huffman编码编码 在电报收发等数据通讯中在电报收发等数据通讯中，常需要将传送的文字转常需要将传送的文字转换成由二进制字符换成由二进制字符0、1组成的字符串来传输组成的字符串来传输。为了使收为了使收发的速度提高发的速度提高，就要求电文就要求电文编码要尽可能地短编码要尽可能地短。此外，。此外，要设计要设计长短不等长短不等的编码，还必须保证的编码，还必须保证任意字符的编码都任意字符的编码都不是另一个字符编码的前缀不是另一个字符编码的前缀，这种编码称为，这种编码称为前缀编码前缀编码。 Huffm

57、an树可以用来构造编码长度不等且译码不产树可以用来构造编码长度不等且译码不产生二义性的编码生二义性的编码。 设电文中的字符集设电文中的字符集C=c1,c2, ,ci, ,cn，各个字符，各个字符出现的次数或频度集出现的次数或频度集W=w1,w2, ,wi, ,wn。3.6哈夫曼树的构造哈夫曼树的构造Huffman编码方法编码方法 以以字符集字符集C作为叶子结点作为叶子结点，次数或频度集，次数或频度集W作为结作为结点的权值点的权值来构造来构造 Huffman树树。规定。规定Huffman树中左分树中左分支代表支代表“0”，右分支代表，右分支代表“1” 。 从根结点到每个叶子结点所经历的路径分支上

58、的从根结点到每个叶子结点所经历的路径分支上的“0”或或“1”所组成的字符串所组成的字符串，为该结点所对应的编码为该结点所对应的编码，称之为称之为Huffman编码编码。 由于每个字符都是叶子结点，不可能出现在根结点由于每个字符都是叶子结点，不可能出现在根结点到其它字符结点的路径上，所以一个字符的到其它字符结点的路径上，所以一个字符的Huffman编编码不可能是另一个字符的码不可能是另一个字符的Huffman编码的前缀编码的前缀。 若字符集若字符集C=a, b, c, d, e, f所对应的权值集合为所对应的权值集合为W=8, 3, 4, 6, 5, 5，如图，如图6-25所示所示，则字符，则字

59、符a,b, c,d, e,f所对应的所对应的Huffman编码分别是编码分别是：10，010，011，00 ，110，111。2 Huffman编码算法实现编码算法实现(1) 数据结构设计数据结构设计 Huffman树中没有度为树中没有度为1的结点棵有的结点棵有n个叶子结点个叶子结点的的Huffman树共有树共有2n-1个结点个结点，则可存储在大小为，则可存储在大小为2n-1的一维数组中。实现编码的结点结构如图的一维数组中。实现编码的结点结构如图6-26所示所示。原因：原因： 求编码需从叶子结点出发走一条从叶子到根的路求编码需从叶子结点出发走一条从叶子到根的路径；径； 译码需从根结点出发走一条

60、到叶子结点的路径。译码需从根结点出发走一条到叶子结点的路径。 结点类型定义结点类型定义：#define MAX_NODE 200 #define MAX_NODE 200 /* Max_Node2n-1/* Max_Node2n-1 */*/ typedef structtypedef struct unsigned int Weight ; unsigned int Weight ; /* /* 权值域权值域 * */ /unsinged int Parent , Lchild , Rchild ;unsinged int Parent , Lchild , Rchild ; HTNode

61、; HTNode ;Weight Parent Lchild RchildWeight Parent Lchild RchildWeightWeight：权值域；：权值域； ParentParent：双亲结点下标：双亲结点下标Lchild, RchildLchild, Rchild：分别标识左：分别标识左、右子树的下标右子树的下标图图6-26 Huffman6-26 Huffman编码的结点结构编码的结点结构(2) Huffman树的生成树的生成算法实现算法实现void Create_Huffman(unsigned n, HTNode HT , unsigned m) /* 创建一棵叶子结点

62、数为创建一棵叶子结点数为n的的Huffman树树 */ unsigned int w ; int k , j ;for (k=1 ; km ; k+) if (k=n) printf(“n Please Input Weight : w=?”); scanf(“%d”, &w) ;HTk.weight=w ; /* 输入时输入时，所有叶子结点都有权值所有叶子结点都有权值 */else HTk.weight=0; /* 非叶子结点没有权值非叶子结点没有权值 */HTk.Parent=HTk.Lchild=HTk.Rchild=0 ; /* 初始化向量初始化向量HT */for (k=n+1; k

63、m ; k+) unsigned w1=32767 , w2=w1 ; /* w1 , w2分别保存权值最小的两个权值分别保存权值最小的两个权值 */ int p1=0 , p2=0 ; /* p1 , p2保存两个最小权值的下标保存两个最小权值的下标 */for (j=1 ; j=k-1 ; j+) if (HTk.Parent=0) /* 尚未合并尚未合并 */ if (HTj.Weightw1) w2=w1 ; p2=p1 ; w1=HTj.Weight ; p1=j ; else if (HTj.Weightw2) w2=HTj.Weight ; p2=j ; /* 找到权值最小的两个

64、值及其下标找到权值最小的两个值及其下标 */HTk.Lchild=p1 ; HTk.Rchild=p2 ;HTk.weight=w1+w2 ;HTp1.Parent=k ; HTp2.Parent=k ; 说明说明：生成生成Huffman树后，树的根结点的下标是树后，树的根结点的下标是2n-1 ，即，即m-1 。(3) Huffman编码算法编码算法 根据出现频度根据出现频度( (权值权值) )Weight，对叶子结点的对叶子结点的Huffman编码有两种方式编码有两种方式： 从叶子结点到根逆向处理，求得每个叶子结点对从叶子结点到根逆向处理，求得每个叶子结点对应字符的应字符的Huffman编码

65、。编码。 从根结点开始遍历整棵二叉树，求得每个叶子结从根结点开始遍历整棵二叉树，求得每个叶子结点对应字符的点对应字符的Huffman编码。编码。 由由Huffman树的生成知，树的生成知，n个叶子结点的树共有个叶子结点的树共有2n-1个结点，叶子结点存储在数组个结点，叶子结点存储在数组HT中的下标值为中的下标值为1n。 编码是叶子结点的编码，只需对数组编码是叶子结点的编码，只需对数组HT1n的的n个权值进行编码；个权值进行编码； 每个字符的编码不同，但编码的最大长度是每个字符的编码不同，但编码的最大长度是n。 求编码时先设一个通用的指向字符的指针变量，求求编码时先设一个通用的指向字符的指针变量

66、，求得编码后再复制。得编码后再复制。算法实现算法实现void Huff_coding(unsigned n , Hnode HT , unsigned m) /* m应为应为n+1,编码的最大长度编码的最大长度n加加1 */ int k , sp ,fp ;char *cd , *HCm ;cd=(char *)malloc(m*sizeof(char) ;/* 动态分配求编码的工作空间动态分配求编码的工作空间 */cdn=0 /* 编码的结束标志编码的结束标志 */for (k=1 ; kn+1 ; k+) /* 逐个求字符的编码逐个求字符的编码 */ sp=n ; p=k ; fp=HTk

67、.parent ; for ( ; fp!=0 ;p=fp , fp=HTp.parent) /* 从叶子结点到根逆向求编码从叶子结点到根逆向求编码 */ if (HTfp.parent=p) cd-sp=0 ; else cd-sp=1 ;HCk=(char *)malloc(n-sp)*sizeof(char) ; /* 为第为第k个字符分配保存编码的空间个字符分配保存编码的空间 */trcpy(HCk , &cdsp) ;free(cd) ;3.6哈夫曼树的构造哈夫曼树的构造二、判定问题（二、判定问题（ Huffman 树的应用）树的应用）问题问题:将百分制的分数转换成五级分制。将百分制

68、的分数转换成五级分制。if a60 g = E; else if a70 g = D; else if a80 g = C; else if a90 g = B; else g = A;3.6哈夫曼树的构造哈夫曼树的构造但是但是, 分数的分布通常具有一定规律分数的分布通常具有一定规律:分数分数0-5960-6970-7980-8990-100比例5%15%40%30%10%a60a70a80a90G =EG =DG =CG =BG =AYYYYNNNN对对10000个数据个数据,共需共需31500次比较次比较3.6哈夫曼树的构造哈夫曼树的构造70 a8080 a9060 a70 a60G=CG

69、=BG=EG=AG=DYYYYNNNN3.6哈夫曼树的构造哈夫曼树的构造对对10000个数据个数据,共需共需22000次比较次比较a60a70a80a90G:=BG:=DG:=EG:=CYYYYNNG:=ANN习题三习题三 假设在树中，假设在树中， 结点结点x是结点是结点y的双亲时，用的双亲时，用(x,y)来来表示树边。已知一棵树的树边集合为表示树边。已知一棵树的树边集合为 (e,i), (b,e), (b,d), (a,b), (g,j), (c,g), (c,f), (h,l), (c,h), (a,c) ，用树，用树型表示法表示该树，并回答下列问题：型表示法表示该树，并回答下列问题： 哪

70、个是根结点哪个是根结点? 哪些是叶子结点哪些是叶子结点? 哪个是哪个是g的双的双亲亲? 哪些是哪些是g的祖先的祖先? 哪些是哪些是g的孩子的孩子? 那些是那些是e的子的子孙孙? 哪些是哪些是e的兄弟的兄弟? 哪些是哪些是f的兄弟的兄弟? b和和n的层次各是多少的层次各是多少? 树的深度是多少树的深度是多少? 以结以结点点c为根的子树的深度是多少为根的子树的深度是多少? 一棵深度为一棵深度为h的满的满k叉树有如下性质：叉树有如下性质： 第第h层上的层上的结点都是叶子结点，其余各层上每个结点都有结点都是叶子结点，其余各层上每个结点都有k棵非空棵非空子树。子树。 如果按层次顺序如果按层次顺序(同层自

71、左至右同层自左至右)从从1开始对全部开始对全部结点编号，问：结点编号，问： 各层的结点数是多少各层的结点数是多少? ? 编号为编号为i的结点的双亲结点的结点的双亲结点(若存在若存在)的编号是多的编号是多少少? 编号为编号为i的结点的第的结点的第j个孩子结点个孩子结点(若存在若存在)的编号的编号是多少是多少? 编号为编号为i的结点的有右兄弟的条件是什么的结点的有右兄弟的条件是什么? 其右其右兄弟的编号是多少兄弟的编号是多少? 设有如图设有如图6-27所示的二叉树。所示的二叉树。 分别用顺序存储方法和链接存储方法画出该二分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。叉树的存储结构。 写出

72、该二叉树的先序、中序、后序遍历序列。写出该二叉树的先序、中序、后序遍历序列。 已知一棵二叉树的先序遍历序列和中序遍历序列已知一棵二叉树的先序遍历序列和中序遍历序列分别为分别为ABDGHCEFI和和GDHBAECIF，请画出这棵二叉，请画出这棵二叉树，然后给出该树的后序遍历序列。树，然后给出该树的后序遍历序列。 设一棵二叉树的中序遍历序列设一棵二叉树的中序遍历序列和后序遍历序列分别为和后序遍历序列分别为BDCEAFHGBDCEAFHG和和DECBHGFA DECBHGFA ，请画出这棵二叉树，然，请画出这棵二叉树，然后给出该树的先序序列。后给出该树的先序序列。图图6-27 6-27 二叉树二叉树

73、a ad de eb bf fg gc ch hk km mn n 已知一棵二叉树的中序遍历序列和后序遍历序列已知一棵二叉树的中序遍历序列和后序遍历序列分别为分别为dgbaekchif和和gdbkeihfca，请画出这棵二叉树，请画出这棵二叉树对应的中序线索树和后序线索树。对应的中序线索树和后序线索树。 以二叉链表为存储结构，请分别写出求二叉树的以二叉链表为存储结构，请分别写出求二叉树的结点总数及叶子结点总数的算法。结点总数及叶子结点总数的算法。 设设图图6-27所示的二叉树是森林所示的二叉树是森林F所对应的二叉树，所对应的二叉树，请画出森林请画出森林F。 设有一棵树，如图设有一棵树，如图6-

74、28所示。所示。 请分别用双亲表示法请分别用双亲表示法、孩子表示法孩子表示法、孩子兄弟孩子兄弟表示法给出该树的存储结构。表示法给出该树的存储结构。 请给出该树的先序遍历序列和后序遍历序列。请给出该树的先序遍历序列和后序遍历序列。 请将这棵树转换成二叉树。请将这棵树转换成二叉树。 设给定权值集合设给定权值集合w=3,5,7,8,11,12 w=3,5,7,8,11,12 ，请构造关，请构造关于于w w的一棵的一棵huffmanhuffman树，并求其加权路径长度树，并求其加权路径长度WPL WPL 。 假设用于通信的电文是由字符集假设用于通信的电文是由字符集a, b, c, d, e, a, b

75、, c, d, e, f, g, hf, g, h中的字符构成中的字符构成， 这这8 8个字符在电文中出现的概个字符在电文中出现的概率分别为率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 0.21, 0.10 。 请画出对应的请画出对应的huffmanhuffman树树( (按左子树根结点的权按左子树根结点的权小于等于右子树根结点的权的次序构造小于等于右子树根结点的权的次序构造) )。 求出每个字符的求出每个字符的huffmanhuffman编码。编码。a ad de eb bf fg gm mh h k kc cn n图图6-28 6-28 一般的树一般的树