数据结构：第6章树C

1、1具体内容：先生成一棵二叉树，再用中序遍历方式打印每个具体内容：先生成一棵二叉树，再用中序遍历方式打印每个结点值，并统计其叶子结点的个数结点值，并统计其叶子结点的个数。具体内容：先生成一棵哈夫曼树，再打印各字符对应的哈夫具体内容：先生成一棵哈夫曼树，再打印各字符对应的哈夫曼编码。曼编码。具体内容：参见严题集具体内容：参见严题集P149 实习实习5.2要求，或参见自测卷要求，或参见自测卷（三个方案由易到难，可自选，参见自测题集（三个方案由易到难，可自选，参见自测题集实验二实验二资料）资料）实验报告要求实验报告要求实验报告格式要求：见实验报告格式要求：见数据结构数据结构题集（题集（C语言版）语言版

2、）P75实习报告规范实习报告规范:除除题目、班级、姓名、学号、完成日期题目、班级、姓名、学号、完成日期外，还要有外，还要有7项内容：项内容：1、 需求分析需求分析2、 概要设计概要设计3、 详细设计详细设计4、 调试分析调试分析5、 用户使用说明用户使用说明6、 测试结果测试结果7、 附录（带注释的源程序）附录（带注释的源程序）实验报告按实验报告按百百分制打分：分制打分： 程序正常跑通：程序正常跑通： 4040分分 界面友好及健壮性：界面友好及健壮性：2020分分 源码有源码有30%30%注释：注释： 2020分分 有实验报告格式：有实验报告格式： 2020分分 23第第6章章 树和二叉树树和

3、二叉树（Tree & Binary Tree）6.1 树的基本概念树的基本概念6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.5 二叉树的典型应用二叉树的典型应用6.6 赫夫曼树及其应用赫夫曼树及其应用利用利用n+1个空链域个空链域6.4 树和森林6.4.1 树和森林与二叉树的转换树和森林与二叉树的转换6.4.2 树和森林的存储方式树和森林的存储方式6.4.3 树和森林的遍历树和森林的遍历4方法：方法：加线加线抹线抹线旋转旋转 abeidfhgcabeidfhgc兄弟相连兄弟相连长兄为父长兄为父孩子靠左孩子靠左6.4.1 树和森林与二

4、叉树的转换树和森林与二叉树的转换回顾回顾1 1：树如何转为二叉树？树如何转为二叉树？左孩子左孩子右右兄弟表示法兄弟表示法5回顾回顾2 2：二叉树怎样还原为树？二叉树怎样还原为树？abeidfhgc要点：要点：逆操作，把逆操作，把所有右孩子变为兄弟所有右孩子变为兄弟！ abdefhgic6法一：法一： 各森林先各自转为二叉树；各森林先各自转为二叉树； 依次连到前一个二叉树的右子树上。依次连到前一个二叉树的右子树上。讨论讨论1 1：森林如何转为二叉树？森林如何转为二叉树？即即F=TF=T1 1, T, T2 2, , ,T,Tm m B=root, LB, RB B=root, LB, RB法二：

5、法二：森林直接变兄弟，再转为二叉树森林直接变兄弟，再转为二叉树（参见教材（参见教材P138P138图图6.176.17，两种方法都有转换示意图），两种方法都有转换示意图）法一和法二得到的二叉树是完法一和法二得到的二叉树是完全相同的、惟一的。全相同的、惟一的。7ABCDEFGHJIABCDEFGHJIBCDEFGHJI森林转二叉树举例：森林转二叉树举例：（用法二，森林直接变兄弟，再转为二叉树）（用法二，森林直接变兄弟，再转为二叉树）兄弟相连兄弟相连 长兄为父长兄为父头树为根头树为根 孩子靠左孩子靠左8BCDEFGHJI讨论讨论2 2：二叉树如何还原为森林？二叉树如何还原为森林？要点：要点：把最右

6、边的子树变为森林，其余右子树变为兄弟把最右边的子树变为森林，其余右子树变为兄弟 即即B=root, LB, RB F=TB=root, LB, RB F=T1 1, T, T2 2, , ,T,Tm m ABCDEFGHJIEFABCDGHJI96.4.2 6.4.2 树和森林的存储方式树和森林的存储方式树有三种常用存储方式：树有三种常用存储方式：双亲表示法双亲表示法 孩子表示法孩子表示法 孩子孩子兄弟表示法兄弟表示法 nextsiblingdatafirstchild指向左孩子指向左孩子指向右兄弟指向右兄弟问：问：树树二叉树的二叉树的“连线连线抹线抹线旋转旋转” 如何由计算机自动实现如何由计

7、算机自动实现？答：答：用用“左孩子右兄弟左孩子右兄弟”表示法来存储即可。表示法来存储即可。 10abecdfhgbacedfgh例如例如：1112因课时有限，因课时有限， “6.4.3树和森树和森林的遍历林的遍历”请自学请自学（见本次（见本次PPT 13-16页）页）6.5 二叉树的典型应用二叉树的典型应用（见本次见本次PPT 17页）页）6.4.3 6.4.3 树和森林的遍历树和森林的遍历例如：例如：abdec先根序列：先根序列：后根序列：后根序列：a b c d eb d c e a深度优先遍历深度优先遍历（先根、后根）（先根、后根）广度优先遍历广度优先遍历（层次）（层次）先根遍历先根遍历

8、访问根结点；访问根结点；依次先根遍历根结点依次先根遍历根结点的每棵子树。的每棵子树。后根遍历后根遍历 依次后根遍历根结点的每依次后根遍历根结点的每棵子树；棵子树； 访问根结点。访问根结点。树没有中序遍历（因树没有中序遍历（因子树不分左右）子树不分左右）13讨论：树若采用讨论：树若采用“先转换，后遍历先转换，后遍历”方式，结果是否一样？方式，结果是否一样？abdec先序遍历：先序遍历：后序遍历：后序遍历：中序遍历：中序遍历：d e c b aabdeca b c d eb d c e a1. 树的先根遍历与二叉树的树的先根遍历与二叉树的先序先序遍历相同；遍历相同； 2. 树的树的后根后根遍历相当

9、于二叉树的遍历相当于二叉树的中序中序遍历；遍历；3. 树没有中序遍历，因为子树无左右之分。树没有中序遍历，因为子树无左右之分。结论：结论：树的先根序列：树的先根序列：a b c d e树的后根序列：树的后根序列：b d c e a14先序遍历先序遍历若森林为空，返回；若森林为空，返回；访问森林中第一棵树的根结点；访问森林中第一棵树的根结点；先根遍历第一棵树的根结点的子树森林；先根遍历第一棵树的根结点的子树森林；先根遍历除去第一棵树之后剩余的树构成的森林。先根遍历除去第一棵树之后剩余的树构成的森林。森林的遍历森林的遍历ABCDEFGHJI为何有中序？为何有中序？深度优先遍历深度优先遍历（先序、中

10、序）（先序、中序）广度优先遍历广度优先遍历（层次）（层次）中序遍历中序遍历若森林为空，返回；若森林为空，返回；中根遍历森林中第一棵树的根结点的子树森林；中根遍历森林中第一棵树的根结点的子树森林；访问第一棵树的根结点；访问第一棵树的根结点；中根遍历除去第一棵树之后剩余的树构成的森林。中根遍历除去第一棵树之后剩余的树构成的森林。15讨论：讨论：若采用若采用“先转换，后遍历先转换，后遍历”方式，结果是否相同？方式，结果是否相同？例如：例如：先序序列：先序序列：中序序列：中序序列：A B C D E F G H I JB C D A F E H J I G先序序列：先序序列：中序序列：中序序列：A B

11、 C D E F G H I JB C D A F E H J I G结论：结论：森林的先序和中序遍历在森林的先序和中序遍历在两种方式下的结果相同。两种方式下的结果相同。166.5 二叉树的典型应用二叉树的典型应用平衡树平衡树排序树排序树字典树字典树判定树判定树带权树带权树最优树最优树由字符串构成的二叉排序树由字符串构成的二叉排序树特点特点：分支查找树（例如：分支查找树（例如1212个球如何只称个球如何只称3 3次次便分出轻重）便分出轻重）特点特点：路径带权值（例如长度）：路径带权值（例如长度）是带权路径长度最短的树，又称是带权路径长度最短的树，又称 HuffmanHuffman树，树，用途之

12、一是通信中的压缩编码。用途之一是通信中的压缩编码。特点特点：所有结点左右子树深度差：所有结点左右子树深度差1 1特点特点：所有结点：所有结点“左小右大左小右大”17什么是平衡二叉树什么是平衡二叉树（ 又称又称AVL 树）树）？性质：性质： 所有所有结点左、右子树深度之差的绝对值结点左、右子树深度之差的绝对值 1若定义结点的若定义结点的“平衡因子平衡因子” BF = 左子树深度左子树深度 右子树深度右子树深度则：平衡二叉树中所有结点的则：平衡二叉树中所有结点的BF -1, 0, 1 (a) (a) 平衡树平衡树 (b) (b) 不平衡树不平衡树例：判断下列二叉树是否例：判断下列二叉树是否AVL树

13、？树？0001 11 1-1-10001-118什么是二叉排序树？什么是二叉排序树？（a）（b）例：例：下列下列2种图形中，哪个不是二叉排序树种图形中，哪个不是二叉排序树 ？-或是一棵空树；或者是具有如下性质的非空二叉树：或是一棵空树；或者是具有如下性质的非空二叉树： （1 1）左子树的所有结点均小于根的值；）左子树的所有结点均小于根的值； （2 2）右子树的所有结点均大于根的值；）右子树的所有结点均大于根的值； （3 3）它的左右子树也分别为二叉排序树。）它的左右子树也分别为二叉排序树。想一想：对它中序遍历之后是什么效果？想一想：对它中序遍历之后是什么效果？74110102 26539810

14、2164739819什么是判定树？什么是判定树？ 举例举例： 1212个球如何用天平只称个球如何用天平只称3 3次便分出轻重？次便分出轻重？分析：分析：1212个球中必有一个非轻即重，即共有个球中必有一个非轻即重，即共有2424种种“次品次品”的可能性。的可能性。每次天平称重的结果有每次天平称重的结果有3 3种，连称种，连称3 3次次应该得到的结果有应该得到的结果有3 33 3=27=27种。种。说明仅用说明仅用3 3次就能找出次品的可能性是存在的。次就能找出次品的可能性是存在的。思路：思路：首先，将首先，将1212个球分三组，每组个球分三组，每组4 4个，任意取两组称。会有个，任意取两组称。

15、会有3 3种结果：种结果：平衡平衡、或、或左左 右右、或、或左左 右右。 其次，一定要利用已经称过的那些结论；即充分利用其次，一定要利用已经称过的那些结论；即充分利用“旧球旧球”的的标准性作为参考。标准性作为参考。20第第1 1次次: :等分等分3 3组组 第第2 2次次: :3 3旧旧3 3新新第第3 3次次: :1 1旧旧1 1新新 相等相等= =小于小于 (11)(11) 大于大于 相等相等= =小于小于 小于小于 小于小于 相等相等= =(12)(12)小于小于 (12)(12)轻轻大于大于 小于小于 小于小于 小于小于 相等相等= =重重重重重重21什么是带权树？什么是带权树？abd

16、c7524即叶子带有权值。例如：即叶子带有权值。例如：最优二叉树最优二叉树( (哈夫曼树哈夫曼树) )如果是带权路径长如果是带权路径长度最短的树度最短的树226.6 Huffman6.6 Huffman树及其应用树及其应用一、一、HuffmanHuffman树树二、二、HuffmanHuffman编码编码最优二叉树最优二叉树HuffmanHuffman树树HuffmanHuffman编码编码带权路径带权路径长度最短长度最短的树的树不等长编码不等长编码是通信中是通信中最经典的最经典的压缩编码压缩编码23树的带权路径长树的带权路径长度如何计算？度如何计算？WPLWPL = = w wk kl lk

17、 k k=1k=1n nabdc7524(a)cdab2457(b)bdac7524(c)经典之例：经典之例：WPL=WPL=WPL=Huffman树是树是WPL WPL 最小的树最小的树树中所有叶子结树中所有叶子结点的带权路径长点的带权路径长度之和度之和36463524一、一、 HuffmanHuffman树树（最优二叉树）（最优二叉树）路路 径径：路径长度路径长度：树的路径长度树的路径长度：带权路径长度带权路径长度：树的带权路径长度树的带权路径长度：HuffmanHuffman树树：由一结点到另一结点间的分支所构成。由一结点到另一结点间的分支所构成。路径上的分支数目。路径上的分支数目。从树

18、根到从树根到每一结点每一结点的路径长度之和。的路径长度之和。结点到根的路径长度与结点上权的乘积（结点到根的路径长度与结点上权的乘积（WPLWPL）若干术语：若干术语：debacf g即树中所有即树中所有叶子结点叶子结点的带权路径长度之和的带权路径长度之和带权路径长度最小的树。带权路径长度最小的树。例如：例如：aeae的路径长度的路径长度树长度树长度2 21010HuffmanHuffman常译为常译为赫夫曼、霍夫曼、哈夫曼、胡夫曼等赫夫曼、霍夫曼、哈夫曼、胡夫曼等Weighted Path LengthWeighted Path Length251. 1. 构造构造Huffman树的基本思想：

19、树的基本思想：设有设有4 4个字符个字符d,i,a,nd,i,a,n，出现的频度分别为，出现的频度分别为7,5,2,47,5,2,4， 怎样编码才能使它们组成的报文在网络中传得最快？怎样编码才能使它们组成的报文在网络中传得最快？法法1 1：等长编码：等长编码（如二进制编码）（如二进制编码）令令d=d=0000，i=i=0101，a=a=1010，n=n=1111，则：，则：WPLWPL1 12bit2bit(7(75 52 24 4）3636法法2 2：不等长编码：不等长编码（如（如HuffmanHuffman编码）编码）令令d=d=0 0;i=;i=1010,a=,a=110110,n=,n

20、=111111，则：，则：讨论：讨论：HuffmanHuffman树有什么用？树有什么用？权值大的结点用短路径，权值小的结点用长路径。权值大的结点用短路径，权值小的结点用长路径。WPLWPL最小的树最小的树频度高的信息频度高的信息用短码，低的用短码，低的用长码，传输用长码，传输效率肯定高！效率肯定高！WPLWPL2 2= =1 1bitbit7 72 2bitbit5+35+3bitbit(2+4)=(2+4)=3535平均码长平均码长= =3535/ /( (7524)=35/18=1.944)=35/18=1.944最小冗余编码、信息高效传输最小冗余编码、信息高效传输26step1step

21、1：在权值集合在权值集合7,5,2,47,5,2,4中，总是合并中，总是合并当前值最小当前值最小的两个权的两个权先介绍先介绍HuffmanHuffman树的具体构造步骤：树的具体构造步骤：a. 初始初始方框表示外结点（叶子，字符）方框表示外结点（叶子，字符）圆框表示内结点圆框表示内结点（合并后的权值）（合并后的权值）b. 合并合并2 4c. 合并合并5 6d. 合并合并7 11谁左谁右？若不谁左谁右？若不规定就会不惟一规定就会不惟一27step2step2：d da ai in n1 11 11 10 00 00 0HuffmanHuffman编码结果：编码结果：d=d=0 0, i=, i=

22、1010, a=, a=110110, n=, n=111111WPL=1WPL=1bitbit7 72 2bitbit5+35+3bitbit(2+4)=(2+4)=3535（小于等长码的（小于等长码的WPL=36WPL=36）HuffmanHuffman编码也称为编码也称为HuffmanHuffman树树 与与 HuffmanHuffman编码编码 挂钩挂钩28最长码元最长码元= =n-1(bit)n-1(bit)2. 2. 构造构造HuffmanHuffman树的步骤树的步骤（即（即HuffmanHuffman算法）：算法）：怎样证明它就是怎样证明它就是WPL最小的最优二叉树？最小的最优

23、二叉树？参考参考信源编码信源编码总之，每次合并当前值最小的两个权。总之，每次合并当前值最小的两个权。( (此树特征：没有度为此树特征：没有度为1 1的结点的结点) )29思考：若权值相同，先合并哪个？思考：若权值相同，先合并哪个？思考：思考：HuffmanHuffman编码举例编码举例解：解：先将概率先将概率放大放大100100倍倍，以方便构造哈夫曼树。，以方便构造哈夫曼树。放大后的权值集合放大后的权值集合 w= 7, 19, 2, 6, 32, 3, 21, 10 w= 7, 19, 2, 6, 32, 3, 21, 10 ，按哈夫曼树构造规则按哈夫曼树构造规则（合并、删除、替换），（合并、

24、删除、替换），可得到哈夫曼树。可得到哈夫曼树。例例1【严题集严题集6.26】：假设用于通信的电文仅由假设用于通信的电文仅由8个字母个字母 a, b, c, d, e, f, g, h 构成，它们在电文中出现的概率分别为构成，它们在电文中出现的概率分别为 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 ，试为这，试为这8个字母设计哈夫曼个字母设计哈夫曼编编码。如果用码。如果用07的二进制编码方案又如何？的二进制编码方案又如何？ 【类同类同P148例例2】30typedef structunsigned int weight；/权值分量（可放大取整）权

25、值分量（可放大取整）unsigned int parent，lchild，rchild； /双亲和孩子分量双亲和孩子分量HTNode，*HuffmanTree；/用动态数组存储用动态数组存储Huffman树树Huffman树的存储表示：树的存储表示：000r0920019007lpw321双亲双亲* *HuffmanTreeHuffmanTree或或 HTHT向量向量样式：样式：HT3.parent=9HT3.parent=931注： 常先用一个int型数组来采集权值W，并用*w指针拷贝给HT10107 71717000000000000000-00000000r001000210030032

26、0060020019007lpw13121011987654321w= 7, 19, 2, 6, 32, 3, 21, 10 w= 7, 19, 2, 6, 32, 3, 21, 10 在机内存储形式为在机内存储形式为: :2 23 35 52828212119194040100100b bc ca a11116 6d d60603232e eg gf fh h5991110104917284060100双亲双亲左右孩子左右孩子363218111110111212选择选择parent为为0且且weight最最小小的两的两个结点个结点另另一一种种表表示示：33Huffman树树HT的机内实现：的

27、机内实现：先构造先构造Huffman树树HT， 才能求出才能求出N个字符的个字符的Huffman编码编码HC。Void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)if (n=1)return;m=2*n-1; /n 个叶子的个叶子的HuffmanTree共有共有2n-1个结点；个结点；HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /0单元未用单元未用for(p=HT+1,i=1; i=n; +i,+p,+w)*p=*w,0,0,0; /给前给前n个单个单元

28、初始化元初始化(教材教材p=HT有误有误)for(；i=m; +i,+p)*p =0,0,0,0; /从叶子之后从叶子之后的存储单元清零的存储单元清零for(i=n+1;i=m; +i) /建建Huffman树树(从从n个叶子后开始存内结点个叶子后开始存内结点) Select(HT, i-1, s1, s2); /在在HT1i-1选择选择parent为为0且且weight最小最小的的两个结点，其序号分别为两个结点，其序号分别为s1和和s2（教材未列此函数源码）教材未列此函数源码）HTs1.parent=i; HTs2.parent=i; /给双亲分量赋值给双亲分量赋值HTi.lchild=s1

29、; HTi.rchild=s2; /给合并后的内结点赋孩子值给合并后的内结点赋孩子值HTi.weight=HTs1.weight+ HTs2.weight;*w存放存放n个字符的权值个字符的权值INT*W是表明是表明W是一个指向是一个指向INT数组的数组的指针指针,*W即取一个即取一个INT,W+后后*W取下一取下一个元素个元素W这里和数组名这里和数组名(即指向该即指向该INT数组的指针数组的指针)等价。等价。s200rs1090i20i7lpwis2s13410107 71717000000000000000-00000000r0010002100300320060020019007lpw1

30、3121011987654321w= 7, 19, 2, 6, 32, 3, 21, 10 w= 7, 19, 2, 6, 32, 3, 21, 10 在机内存储形式为在机内存储形式为: :2 23 35 52828212119194040100100b bc ca a11116 6d d60603232e eg gf fh h5991110104917284060100双亲双亲左右孩子左右孩子363518111110111212选择选择parent为为0且且weight最最小小的两的两个结点个结点根据哈夫曼树可得对应编码：根据哈夫曼树可得对应编码：符符编码编码频率频率a0.07b0.19c0

31、.02d0.06e0.32f0.03g0.21h0.10符符编码编码频率频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10000001010011100101110111Huffman码的码的WPL2(0.19+0.32+0.21) + 4(0.07+0.06+0.10) +5(0.02+0.03) =1.44+0.92+0.25=2.61 平均码长平均码长=2.61/(概率总和概率总和)=2.61/1=2.613(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 二进制等长码的二进制等长码的WPL按左按左0右右1标注标注0

32、 00 00 00 00 00 01 11 11 11 11 11 11 10 010107 717172 23 35 52828212119194040100100b bc ca a11116 6d d60603232e eg gf fh h36typedef structunsigned int weight；/权值分量（可放大取整）权值分量（可放大取整）unsigned int parent，lchild，rchild； /双亲和孩子分量双亲和孩子分量HTNode，*HuffmanTree；/用动态数组存储用动态数组存储Huffman树树Huffman树编码的机内实现：树编码的机内实现：

33、HCHC向量向量样式：样式：HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi, &cdstart);指针型指针指针型指针37HCi0 1 1 1 - - - - -cd =(char*) malloc(n*sizeof(char)start=n-1-start最长码元最长码元= =n-1(bit)n-1(bit)逐个字符求逐个字符求HuffmanHuffman编码编码: :for(i=1; i=n; +i) start=n-1; /编码结束符位置编码结束符位置 for(c=i, f=HTi.parent; f!=0; c=f, f=H

34、Tf.parent) if(HTf.lchild=c) cd-start=“0”; else cd-start=“1”; /从叶子到根逆向求编码从叶子到根逆向求编码10107 717172 23 35 52828212119194040100100b bc ca a11116 6d d60603232e eg gf fh h0 00 00 00 00 00 01 11 11 11 11 11 11 10 0- - - - -cd-startstart=n-1c(=i=1)f(=11)双亲双亲=0则到根则到根,停止编码停止编码-startSIZEOF()可以对变量或变量类型运算可以对变量或变量类型运算,SIZEOF(CHAR*)是是一个一个CHAR型指针的空间大小型指针的空间大小,如定义如定义CHAR*P,那么那么SIZEOF(P)就是结果就是结果,和和SIZEOF(CHAR*)等价。等价。(续前续前) 求出求出n个字符的个字符的Huffman编码编码HCHC=(HuffmanCode)malloc(n+1)*sizeof(char*);