树和二叉树讲义

1、第六章第六章 树和二叉树树和二叉树6.1 树的概念及术语树的概念及术语6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.6 哈夫曼树及其应用哈夫曼树及其应用树是树是n(n0)n(n0)个结点的有限集。个结点的有限集。 在任意一棵非空树中：在任意一棵非空树中： (1) (1) 有且仅有一个特定的称为根有且仅有一个特定的称为根( (Root)Root)的结点；的结点； (2) (2) 当当 n1n1时时, , 其余结点可分为其余结点可分为m(m0)m(m0)个互不相个互不相交的有限集交的有限集T T1 1,T,T2 2, ,T,Tm m, , 其中

2、每一个集合本身又是一棵树其中每一个集合本身又是一棵树, , 并且称为根的并且称为根的子树子树( (SubTreeSubTree) )。树的抽象数据类型定义如下：树的抽象数据类型定义如下：数据关系数据关系 R: R: 若若D D为空集，则称为空树；为空集，则称为空树；6.1 6.1 树的概念及术语树的概念及术语树的抽象数据类型定义如下：树的抽象数据类型定义如下：ADT TreeADT Tree 数据对象数据对象 D: DD: D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。 数据关系数据关系 R: R: 若若D D为空集，则称为空树；为空集，则称为空树； 若若D D仅含一个数据

3、元素仅含一个数据元素, ,则则R R为空集为空集, ,否则否则R=H,HR=H,H是如下二是如下二元关系元关系: :(1) (1) 在在D D中存在中存在唯一的唯一的称为根的数据元素称为根的数据元素rootroot, ,它在关系它在关系H H下下无前驱无前驱; ;(2) (2) 若若D-root,D-root,则存在则存在, ,则存在则存在D Drootroot的一个的一个划分划分D D1 1,D,D2 2, , ,D Dm m(m(m0),0),对任意对任意jk(1j,km)jk(1j,km)有有D Dj jDDk k=,=,且对任意的且对任意的i(1im),i(1im), 唯一存在数据元素

4、唯一存在数据元素X Xi iDDi i, ,有有 H;H;(3) (3) 对应于对应于D-rootD-root的划分的划分, ,H-H-,有唯一的一个划分有唯一的一个划分H H1 1,H,H2 2, ,H Hm m(m(m0),0),对任意对任意jk(1j,km)jk(1j,km)有有H Hj jHHk k=,=,且对任意且对任意i(1im), i(1im), H Hi i是是D Di i上的二元关系，上的二元关系， ( ( D Di i, H, Hi i)是一棵符合本定是一棵符合本定义的树义的树, ,称为根称为根rootroot的子树。的子树。例如例如A只有根结点的树只有根结点的树ACGBD

5、EFKLHMIJ有有13个结点的树个结点的树其中：其中：A A是根；其余结点分成三个互不相交的子集，是根；其余结点分成三个互不相交的子集，T T1 1=B,E,F,K,L=B,E,F,K,L； T T2 2=C,G=C,G； T T3 3=D,H,I,J,M,=D,H,I,J,M,T T1 1,T,T2 2,T,T3 3都是根都是根A A的子树，且本身也是一棵树。的子树，且本身也是一棵树。AJIMHDGCFLKEB凹入表示凹入表示ABFEKLGCDHMIJ嵌套集合嵌套集合(A(B(E(K,L),F),C(G),D(H(M),I,J)广义表广义表树的其它表示方式树的其它表示方式ACGBDEFKL

6、HMIJ 树的结构定义是一个递归的定义树的结构定义是一个递归的定义, ,即在即在树的定义中又用到树的概念树的定义中又用到树的概念, ,它道出它道出了树的固有特性了树的固有特性。 结结 论论树的基本术语树的基本术语1层2层4层3层height= 4ACGBDEFKLHMIJ 二叉树二叉树( (Binary Tree)Binary Tree)是一种树型结构是一种树型结构, , 特点是每个特点是每个结点至多只有二棵子树结点至多只有二棵子树, ,并且二叉树为有序树。并且二叉树为有序树。 二叉树的五种基本形态如下二叉树的五种基本形态如下: :6.6.2 2 二叉树二叉树(a)(b)(c)(d)(e)6.

7、2.1 6.2.1 二叉树的定义二叉树的定义性质性质1 1 在二叉树的第在二叉树的第i i层上至多有层上至多有2 2i-1i-1个结点个结点( (i1)i1)。由于二叉树的每个结点的度至多为由于二叉树的每个结点的度至多为2 2，故在第，故在第i i层上的层上的最最大结点数为第大结点数为第i-1i-1层上的最大结点数的层上的最大结点数的2 2倍，倍，即即2 2* *2 2i i2 2= = 2 2i-1i-1。归纳法证明：当归纳法证明：当i=1i=1时，只有根结点，时，只有根结点，2 2i-1i-1=2=20 0=1=1。假设对所有假设对所有j j，ijij 1 1，命题成立，即第命题成立，即第

8、j j层上至多有层上至多有2 2j-1j-1 个个结点。结点。由归纳假设第由归纳假设第i-1i-1层上至多有层上至多有2 2i i2 2个结点。个结点。6.2.2 6.2.2 二叉树的性质二叉树的性质性质性质2 2 深度为深度为k k的二叉树至多有的二叉树至多有2 2k k1 1个结点个结点( (k1)k1)。证明：由性质证明：由性质1 1可见，深度为可见，深度为k k的二叉树的最大结点数为的二叉树的最大结点数为 kii11220 + 21 + + 2k-1 = 2k - -1kii1(层上的最大结点数）第性质性质3 3 对任何一棵二叉树对任何一棵二叉树T,T,如果其终端结点数为如果其终端结点

9、数为n n0 0, ,度度为为2 2的结点数为的结点数为n n2 2, , 则则n n0 0= = n n2 2+1+1。 推出推出 n n2 2 = = n n0 0 - 1 - 1 证明：若度为证明：若度为1 1的结点有的结点有 n n1 1 个，总结点个数为个，总结点个数为 n n，分，分支总数为支总数为 B B，则根据二叉树的定义，则根据二叉树的定义， n = nn = n0 0 + n + n1 1 + n + n2 2 B = 2n B = 2n2 2 + n + n1 1 = n - 1= n - 1因此，有因此，有 2 2n n2 2 + n + n1 1 = n= n0 0

10、+ n + n1 1 + n + n2 2 - 1 - 1 或或 n n0 0 = = n n2 2 + 1 + 1 1 满二叉树满二叉树 (Full Binary Tree) 一棵深度为一棵深度为k且有且有2k -1个结点的二叉树称为满二叉树。个结点的二叉树称为满二叉树。两种特殊形态的二叉树两种特殊形态的二叉树621754389 10 1113 14 1512满二叉树满二叉树1. 满二叉树满二叉树 (Full Binary Tree) 一棵深度为一棵深度为k且有且有2k -1个结点的二叉树称为满二叉树。个结点的二叉树称为满二叉树。两种特殊形态的二叉树两种特殊形态的二叉树621754389 1

11、0 1113 14 1512满二叉树满二叉树若设二叉树的高度为若设二叉树的高度为h h，则共有则共有h h层。除第层。除第 h h 层外，其它层外，其它各层各层 (1 (1 h-1 h-1) ) 的结点数都达到最大值，的结点数都达到最大值，第第 h h 层从右层从右向左连续缺若干结点向左连续缺若干结点，这就是完全二叉树。，这就是完全二叉树。6217543891011122. 完全二叉树完全二叉树 (Complete Binary Tree)62175438910 111.1.深度为深度为h h的完全二叉树其结点个数的取值范围的完全二叉树其结点个数的取值范围2h-1h-1 2h h-12.2.完

12、全二叉树中叶结点只可能出现在倒数第一层和倒数完全二叉树中叶结点只可能出现在倒数第一层和倒数第二层。第二层。3.3.且当完全二叉树的结点个数为偶数时，有且仅有一个且当完全二叉树的结点个数为偶数时，有且仅有一个单分支结点，为奇数时无单分支结点。单分支结点，为奇数时无单分支结点。有关完全二叉树的重要结论有关完全二叉树的重要结论n n0 0=(n=(n奇数奇数+1)/2+1)/2n n0 0=n=n偶数偶数/2/2一棵完全二叉树有一棵完全二叉树有50005000个结点，可以计算出个结点，可以计算出其叶结点的个数是（其叶结点的个数是（ ）。）。 练习练习2500两边同取对数得：两边同取对数得： h h1

13、log1log2 2n n h h证明：设完全二叉树的深度为证明：设完全二叉树的深度为 h h，则根据性质则根据性质2 2和完全二和完全二叉树的定义叉树的定义2 2h h1 1 - 1 n - 1 n 2 2h h - 1- 1由于由于n n是正整数因此上式等价于是正整数因此上式等价于2 2h h1 1 n 2 n 1, i1, 则其双亲则其双亲PAREBT(iPAREBT(i) )是结点是结点 i/2i/2 。(2)(2) 如果如果2 2in,in,则结点则结点i i无左孩子无左孩子, ,否则其左孩子否则其左孩子LCHILD(i)LCHILD(i)是结点是结点2 2i i；(3) (3) 如

14、果如果2 2i+1n,i+1n,则结点则结点i i无右孩子无右孩子, ,否则其右孩子否则其右孩子RCHILD(i)RCHILD(i)是结点是结点2 2i+1i+1。 182345679 101.1.顺序存储结构顺序存储结构 # # define MAX-TREE-SIZE 100define MAX-TREE-SIZE 100 typedeftypedef TElemTypeTElemType SqBiTreeMAX_TREE_SIZESqBiTreeMAX_TREE_SIZE; SqBiTreeSqBiTree btbt; ; 用一组地址连续的存储单元依次自上而下，自左用一组地址连续的存储单

15、元依次自上而下，自左至右存储完全二叉树上的结点元素，即将完全二叉树至右存储完全二叉树上的结点元素，即将完全二叉树上编号为上编号为 i i 的结点元素存储在如上定义的一维数组的结点元素存储在如上定义的一维数组中下标为中下标为 i-1 i-1 的分量中。的分量中。 6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构完全二叉树的顺序存储表示图解完全二叉树的顺序存储表示图解完全二叉树完全二叉树1 2 3 4 5 6 7 8 91012489 1056730217365849 对于一般二叉树，则应将其每个结点与完全二叉对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应

16、分量中。树上的结点相对照，存储在一维数组的相应分量中。9123654789 10一般二叉树一般二叉树1 2 3 4 0 5 6 7 8 0 0 0 0 9 10 3 1310 2 1 0 11 9 8 7 6 5 4 14 12 在最坏的情况下，一棵深度为在最坏的情况下，一棵深度为k k且只有且只有k k个结点的单支树，却需要长度为个结点的单支树，却需要长度为2 2K K-1-1的一维数的一维数组。组。( (请思考那种情况是最坏的情况？为什么？请思考那种情况是最坏的情况？为什么？) ) 思思 考考左单支左单支123右单支右单支132datalChildrChild二叉链表lChild data

17、 rChild含两个指针域的结点结构含两个指针域的结点结构lChild data parent rChild含三个指针域的结点结构含三个指针域的结点结构parentdatalChildrChild三叉链表typedef char TreeData;/结点数据类型结点数据类型typedef struct node /结点定义结点定义 TreeData data; struct node * leftChild, * rightchild; BinTreeNode;typedef BinTreeNode * BinTree; /根指针根指针 二叉链表的定义二叉链表的定义单支树的二叉链表（单支树的二

18、叉链表（a a） BADCABCD 二叉链表二叉链表( (b)b)BAEDFCGABEDFGC观察可得，n个结点的二叉链表具有n+1个空链域证明：对于具有证明：对于具有n n个结点的二叉链表共有个结点的二叉链表共有2n2n个链域，个链域，但仅有但仅有n-1n-1个非空链域。个非空链域。所以空链域数所以空链域数2n-2n-（n-1)n-1)性质：含有性质：含有n n个结点的二叉链表中有个结点的二叉链表中有n+1n+1个空链域。个空链域。=n+1=n+1 重要性质的证明重要性质的证明6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树遍历定义遍历定义所谓遍历即如何按某条搜索路径巡所谓遍历即

19、如何按某条搜索路径巡访树中每个结点访树中每个结点, ,使得每个结点均被使得每个结点均被访问一次访问一次, ,且仅被访问一次。且仅被访问一次。遍历用途遍历用途它是树结构插入、删除、修改、查它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一找和排序运算的前提，是二叉树一切运算的基础和核心。切运算的基础和核心。 ROOTLCHILDRCHILDDLRDLRLDRLRDDRLRDLRLD先左后右先左后右6.3.1 6.3.1 遍历二叉树遍历二叉树先序遍历二叉树算法的定义：先序遍历二叉树算法的定义： 若二叉树为空，则空操作；若二叉树为空，则空操作； 否则否则访问根结点访问根结点 (D)(D)；

20、先序遍历左子树先序遍历左子树 (L)(L)；先序遍历右子树先序遍历右子树 (R)(R)。先序遍历先序遍历 (Preorder Traversal)遍历结果遍历结果a+f*eb-/c-d先序遍历二叉树的递归算法先序遍历二叉树的递归算法void PreOrder( BinTreeNode *T ) if ( T != NULL ) Visit( T-data); PreOrder ( T-leftChild ); PreOrder ( T-rightChild ); / PreOrder中序遍历二叉树算法的定义：中序遍历二叉树算法的定义： 若二叉树为空，则空操作；若二叉树为空，则空操作； 否则否则

21、中序遍历左子树中序遍历左子树 (L)(L)；访问根结点访问根结点 (D)(D)；中序遍历右子树中序遍历右子树 (R)(R)。中序遍历中序遍历 (Inorder Traversal)遍历结果遍历结果a+fbe*-/c-d中序遍历二叉树的递归算法中序遍历二叉树的递归算法void Inorder( BinTreeNode *T ) if ( T != NULL ) InOrder ( T-leftChild ); Visit( T-data); InOrder ( T-rightChild ); / InOrder后序遍历二叉树算法的定义：后序遍历二叉树算法的定义： 若二叉树为空，则空操作；若二叉树

22、为空，则空操作； 否则否则后序遍历左子树后序遍历左子树 (L)(L)；后序遍历右子树后序遍历右子树 (R)(R)；访问根结点访问根结点 (D)(D)。后序遍历后序遍历 (Postorder Traversal)遍历结果遍历结果a+fbe*-/c-d后序遍历二叉树的递归算法后序遍历二叉树的递归算法void Postorder( BinTreeNode *T ) if ( T != NULL ) PostOrder ( T-leftChild ); PostOrder ( T-rightChild ); Visit( T-data); / PostOrder二叉树遍历应用二叉树遍历应用n以递归方式

23、建立二叉树。以递归方式建立二叉树。n输入结点值的顺序必须对应二叉树结点先序遍历的输入结点值的顺序必须对应二叉树结点先序遍历的顺序。并约定以输入序列中不可能出现的值作为空顺序。并约定以输入序列中不可能出现的值作为空结点的值以结束递归结点的值以结束递归, , 此值在此值在RefValueRefValue中。例如用中。例如用“”或用或用“-1”-1”表示字符序列或正整数序列空结点。表示字符序列或正整数序列空结点。按先序建立二叉树按先序建立二叉树(递归算法递归算法)ABCDEGFA B C D E G F 如图所示的二叉树的先序遍历顺序为如图所示的二叉树的先序遍历顺序为V27.2 7.2 图的存储结构

24、图的存储结构7.2.17.2.1 数组（邻接矩阵）表示法数组（邻接矩阵）表示法7.2.2 7.2.2 图的邻接表表示法图的邻接表表示法普通二叉树只能找到结点的左右孩子信息，而该结普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得点的直接前驱和直接后继只能在遍历过程中获得若将遍历后对应的有关前驱和后继预存起来，则从若将遍历后对应的有关前驱和后继预存起来，则从第一个结点第一个结点开始就能很快开始就能很快“顺藤摸瓜顺藤摸瓜”而遍历整棵树。而遍历整棵树。例如中序遍历结果：例如中序遍历结果：B D C E A F H GB D C E A F H G，实际上，实际上已

25、将二叉树转为线性排列，显然具有唯一前驱和已将二叉树转为线性排列，显然具有唯一前驱和唯一后继！唯一后继！可能是根、或最左（右）叶子可能是根、或最左（右）叶子6.3.2 6.3.2 线索二叉树线索二叉树两种解决方法两种解决方法增加两个指针域：增加两个指针域：fwdfwd和和bwdbwd；利用空链域（利用空链域（n+1n+1个空链域）个空链域）如何保存二叉树遍历过程中所得到如何保存二叉树遍历过程中所得到的前驱、后继信息？的前驱、后继信息？ 若结点有左子树若结点有左子树, ,则其则其leftChildleftChild域指示其左孩子域指示其左孩子, ,否否则令则令leftChildleftChild域

26、指示其前驱；域指示其前驱； 若结点有右子树若结点有右子树, ,则其则其rightChildrightChild域指示其右孩子域指示其右孩子, ,否否则令则令rightChildrightChild域指示其后继。域指示其后继。 为了避免混淆为了避免混淆, ,增加两个标志域增加两个标志域: :leftThreadleftThread和和rightThreadrightThread。为保存在遍历中得到的为保存在遍历中得到的动态信息动态信息, ,试作如下现定试作如下现定: :leftChildrightChildleftThreadrightThreaddata其中其中: : 0 leftChildl

27、eftChild 域指示结点的左孩子域指示结点的左孩子 = 1 leftChildleftChild 域指示结点的前驱域指示结点的前驱 0 rightChildrightChild 域指示结点的右孩子域指示结点的右孩子 = 1 rightChildrightChild 域指示结点的后继域指示结点的后继leftThreadrightThread 以这种结点构成的二叉树链表作为二叉树的存储结以这种结点构成的二叉树链表作为二叉树的存储结构构, , 叫做叫做线索链表线索链表, ,其中指向结点其中指向结点前驱前驱和和后继的指针后继的指针, , 叫作叫作线索线索, , 加上线索的二叉树称之为加上线索的二叉

28、树称之为线索二叉树线索二叉树。中序线索二叉树中序线索二叉树BDAECBDAEC，如下图所示：，如下图所示： 对二叉树以某种次序遍历使其变成线索二对二叉树以某种次序遍历使其变成线索二叉树的过程叫做叉树的过程叫做线索化线索化. . 在线索树中进行遍历时在线索树中进行遍历时, ,只要先找到序列中只要先找到序列中的第一个结点的第一个结点, , 然后依次找结点后继直至其后然后依次找结点后继直至其后继空时为止。继空时为止。 后继：结点标志为后继：结点标志为1 1时，其右指针为其后继；时，其右指针为其后继；结点标志为结点标志为0 0时，其右子树最左下结点为其时，其右子树最左下结点为其后继。后继。abcde中

29、序线索二叉树中序线索二叉树 前驱：结点标志为前驱：结点标志为1 1时，其左指时，其左指针为其前驱；结点标志为针为其前驱；结点标志为0 0时，时，其左子树最右下结点为其前驱。其左子树最右下结点为其前驱。 由于线索化的实质是将二叉树链表中的空指针改由于线索化的实质是将二叉树链表中的空指针改为指向前驱或后继的线索为指向前驱或后继的线索, ,而前驱或后继的信息只有而前驱或后继的信息只有在遍历时才能得到。因此在遍历时才能得到。因此线索化的过程即为在遍历的线索化的过程即为在遍历的过程中修改空指针的过程。过程中修改空指针的过程。 为了记下遍历过程中访问结点的先后关系为了记下遍历过程中访问结点的先后关系, ,

30、附设一附设一个指针个指针prepre始终指向刚刚访问过的结点始终指向刚刚访问过的结点, ,若指针若指针p p指向当指向当前访问过的结点前访问过的结点, ,则则prepre指向它的前驱。指向它的前驱。 线索化的实质线索化的实质StatusStatus InOrderThreading(InOrderThreading(BiThrTree&Thrt,BiThrTree T) ) /中序遍历并线索化二叉树，Thrt为头结点 if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode) exit(OVERFLOW)；/建头结点 ThrtleftThread=lin

31、k； ThrtrightThread=Thread； ThrtrightChild=Thrt；/头结点右指针回指 If(!T) ThrtleftChild=Thrt；/若二叉树为空，则左指针也回指 Else ThrtleftChild=T; Pre=Thrt；/pre总是指向最后一个访问过的结点，即其后要访问结点的前驱 InThreading(T)； /线索化的主过程 prerightChild=Thrt； prerightThread=Thread； ThrtrightThread=pre； /将最后一个结点线索化 return OK； 算法算法 6.6 中序线索二叉树中序线索二叉树V27.

32、2 7.2 图的存储结构图的存储结构7.2.17.2.1 数组（邻接矩阵）表示法数组（邻接矩阵）表示法7.2.2 7.2.2 图的邻接表表示法图的邻接表表示法算法算法 2.2 顺序有序表的合并顺序有序表的合并6.4 6.4 树和森林树和森林1.1.树的双亲表示法树的双亲表示法2.2.孩子表示法孩子表示法( (多重链表多重链表) )3.3.孩子兄弟表示法孩子兄弟表示法6.4.16.4.1 树的存储结构树的存储结构typedef struct PTNode TElemType data ； int parent ；PTNode;1.1.树的双亲表示法树的双亲表示法#define MAX_TREE_

33、SIZE 100typedef struct PTNode nodes MAX_TREE_SIZE； int n；PTree；PARENT(T,X)PARENT(T,X)操作可以在常量时间内实现，反复调用，操作可以在常量时间内实现，反复调用，直到遇到无双亲的结点时，便找到了树的根。直到遇到无双亲的结点时，便找到了树的根。 BAGEIDHCFEDCBAHI440-1101654321078data parent树的双亲表示法示例树的双亲表示法示例typedef struct PTNode TElemType data ； int parent ；PTNode;树的双亲表

34、示法形式说明如下：树的双亲表示法形式说明如下：#define MAX_TREE_SIZE 100typedef struct PTNode nodes MAX_TREE_SIZE； int n；PTree；2.2.孩子表示法孩子表示法( (多重链表多重链表) )ABCDEFGBCDEFGAn(d-1)+1n(d-1)+1个空链域个空链域 第一种结点结构第一种结点结构 等数量的链域等数量的链域 (d为树的度为树的度) childd . child2 child1 data 第二种结点结构第二种结点结构 不同数量的链域不同数量的链域 childd . child2child1degree data

35、 若采用第二种结点格式，则多重链表中的结点是不若采用第二种结点格式，则多重链表中的结点是不同构的，其中同构的，其中dd为结点的度，为结点的度，degreedegree域的值同域的值同dd。 此时，虽能节约存储空间，但操作不方便。此时，虽能节约存储空间，但操作不方便。 孩子链表孩子链表G6F5E4D3C2B1A0123456ABCDEFG将每个结点将每个结点的孩子链在的孩子链在该结点之后该结点之后组成链表，组成链表，再将所有头结点组再将所有头结点组成一个线性表成一个线性表。结点结构结点结构nextSiblingdata firstChildABCDEFGn+1n+1个空链域个空链域ABECFDG

36、3.3.孩子兄弟表示法孩子兄弟表示法typedef char TreeData;typedef struct node TreeData data; struct node *firstChild, *nextSibling; TreeNode;typedef TreeNode * Tree;用左孩子用左孩子- -右兄弟表示实现的树定义右兄弟表示实现的树定义6.4.26.4.2 森林与二叉树的转换森林与二叉树的转换BACDEFJHGI森林的二叉树表示3 棵树的森林BADCEFHGIJT1T2T3BACDEFJHGI各棵树的二叉树表示T1T2T3树的先根树的先根遍历遍历n当树非空时当树非空时u

37、访问根结点访问根结点u 依次先根遍历根的各棵依次先根遍历根的各棵u 子树子树 n树先根遍历树先根遍历 A B E F C D GA B E F C D GABCEDGFABCDEFGn对应二叉树先根遍历对应二叉树先根遍历 A B E F C D GA B E F C D Gn树的先根遍历同其对应二叉树的先根遍树的先根遍历同其对应二叉树的先根遍历历n当树非空时当树非空时u 依次后根遍历根的各棵依次后根遍历根的各棵u 子树子树u访问根结点访问根结点 n树后根遍历树后根遍历 E F B C G D AE F B C G D AABCEDGF树的后根遍历树的后根遍历n对应二叉树中序遍历对应二叉树中序遍

38、历 E F B C G D AE F B C G D An树的后根遍历同其对应二叉树的中序遍树的后根遍历同其对应二叉树的中序遍历历ABCDEFG按照森林和树相互递归的定义，按照森林和树相互递归的定义，我们可以推出森林的两种遍历方法：我们可以推出森林的两种遍历方法：一、先序遍历森林一、先序遍历森林 若森林非空，则可按下述规则遍历之：若森林非空，则可按下述规则遍历之：(1) (1) 访问森林中第一棵树的根结点访问森林中第一棵树的根结点; ;(2) (2) 先序遍历第一棵树中根结点的子树森林；先序遍历第一棵树中根结点的子树森林；(3) (3) 先序遍历除去第一棵树之后剩余的树构成的森林。先序遍历除去

39、第一棵树之后剩余的树构成的森林。森林的遍历森林的遍历森林进行先序遍历的序列为：森林进行先序遍历的序列为：A B C D E F G H I J A B C D E F G H I J 森林的先序遍历即为其对应的二叉树的先序遍历。森林的先序遍历即为其对应的二叉树的先序遍历。BADCBACDHGIJJHGIEFEF二、中序遍历森林二、中序遍历森林 若森林非空，则可按下述规则遍历之：若森林非空，则可按下述规则遍历之： (1) (1) 中序遍历森林中第一棵树的根结点的子树森林；中序遍历森林中第一棵树的根结点的子树森林； (2) (2) 访问第一棵树的根结点；访问第一棵树的根结点； (3) (3) 中序

40、遍历除去第一棵树之后剩余的树构成的森林。中序遍历除去第一棵树之后剩余的树构成的森林。森林的遍历森林的遍历森林进行中序遍历的序列为森林进行中序遍历的序列为 B C D A F E H J I GB C D A F E H J I G森林的中序遍历即为其对应的二叉树的中序遍历。森林的中序遍历即为其对应的二叉树的中序遍历。BADCBACDHGIJJHGIEFEF带权路径长度带权路径长度 (Weighted Path Length, WPL)二叉树的带权二叉树的带权 (外部外部) 路径长度是树的各叶结点所带路径长度是树的各叶结点所带的权值的权值 wi 与该结点到根的路径长度与该结点到根的路径长度 li

41、 的乘积的和。的乘积的和。10niiilwWPL6.6.6 6 赫夫曼树及其应用赫夫曼树及其应用 (a) WPL=7 (a) WPL=72 + 52 + 52 + 22 + 22 + 42 + 42 =362 =36 (b) WPL=7(b) WPL=73 + 53 + 53 + 23 + 21 + 41 + 42 =462 =46 (c) WPL=7 (c) WPL=71 + 51 + 52 + 22 + 23 + 43 + 43 =353 =35 其中（其中（c c）树的带权路径长度最小，）树的带权路径长度最小， 可以验证，它恰为哈夫曼树。可以验证，它恰为哈夫曼树。abcd7ab524ca

42、b4d2ab75a7ab5bcd24 (a) (b) (c) 赫夫曼树赫夫曼树n带权路径长度达到最小的二叉树即为赫夫曼树。带权路径长度达到最小的二叉树即为赫夫曼树。n在哈夫曼树中，权值大的结点离根最近在哈夫曼树中，权值大的结点离根最近。(1) (1) 由给定的由给定的n n个权值个权值 ww0 0, w, w1 1, w, w2 2, , , w, wn-1n-1 ，构造构造具有具有n n棵二叉树的森林棵二叉树的森林 F= TF= T0 0, T, T1 1, T, T2 2, , , T, Tn-1 n-1 ，其中，其中每棵二叉树每棵二叉树 T Ti i 只有一只有一 个带权值个带权值 w

43、wi i 的根结点的根结点, , 其左、右其左、右子树均为空。子树均为空。 赫夫曼赫夫曼算法算法 在在 F F 中选取两棵根结点的权值最小的二叉树中选取两棵根结点的权值最小的二叉树, , 做为左、右子树构造一棵新的二叉树。置新的二叉树的根做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。结点的权值为其左、右子树上根结点的权值之和。(2) (2) 重复以下步骤重复以下步骤, , 直到直到 F F 中仅剩下一棵树为止。中仅剩下一棵树为止。赫夫曼算法的具体步骤赫夫曼算法的具体步骤 在在 F F 中删去这两棵二叉树。中删去这两棵二叉树。 把新的二叉树加入把新

44、的二叉树加入 F F。F : 7 5 2 47524初始F : 7 5 6合并2 475246F : 7 11 1175246合并5 6F : 18 合并7 11527461118赫夫曼树的构造过程举例赫夫曼树的构造过程举例可以利用二叉树来设计二进制的前缀编码，若约定左可以利用二叉树来设计二进制的前缀编码，若约定左分支表示字符分支表示字符00，若约定右分支表示字符，若约定右分支表示字符11：可得A、B、C、D的二进制前缀编码A1ab0BCD0101A（0）B（10）C（110）D（111） 6.6.6.26.2 赫夫曼编码赫夫曼编码const int n = 20;/叶结点数叶结点数const int m = 2*n - -1;/结点数结点数 typedef struct float weight; int parent, leftChild, rightChild; HTNode; typedef HTNode HuffmanTreem;赫夫曼