第六章 树和二叉树演示优秀课件.ppt
第六章第六章 树和二叉树演示树和二叉树演示第1页，本讲稿共20页第六章第六章 树和二叉树树和二叉树 6.7 6.7 哈夫曼树及应用哈夫曼树及应用 6.7.1 哈夫曼树及构造 6.7.1 哈夫曼编码 第2页，本讲稿共20页6.7 6.7 哈夫曼树及应用哈夫曼树及应用6.7.1 6.7.1 哈夫曼树及构造哈夫曼树及构造1 哈夫曼树哈夫曼树的概念的概念路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；路径长度：路径上的分支数目称为路径长度；结点的权：根据应用的需要可以给树的结点赋权值；结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作 WPL=wi Li 哈夫曼树：假设有n个权值(w1,w2 ,wn )，构造有n个叶子结点的二叉树，每个叶子结点有一个 wi 作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。哈夫曼树。第3页，本讲稿共20页6.7 6.7 哈夫曼树及应用哈夫曼树及应用2 应用举例应用举例在求得某些判定问题时，利用哈夫曼树获得最佳判定算法。例 编制一个将百分制转换成五分制的程序。最直观的方法是利用if语句来的实现。可用二叉树描述判定过程。参见课本P145 图6.23(a)。如果这个程序很不经常使用，或要转换的分数不多，不必考虑该程序效率，我们可以按照这个流程编程。可是如果该程序经常要使用或数据量很大。比如对北京市几十万小学生的分数进行转换，在这种情况下，要考虑转换程序的效率。设有10000个百分制分数要转换，设学生成绩在5个等级以上的分布如下：分数 0-59 60-69 70-79 80-89 90-100比例数 0.05 0.15 0.40 0.30 0.10第4页，本讲稿共20页6.7 6.7 哈夫曼树及应用哈夫曼树及应用按图的判定过程，转换一个分数所需的比较次数=从根到对应结点的路径长度。转换10000个分数所需的总比较次数=10000（0.05 1+0.15 2+0.4 3+0.3 4+0.1 4）若将学生成绩在5个等级以上的分布比例看作描述判定过程二叉树叶子结颠点权值，（0.05 1+0.15 2+0.4 3+0.3 4+0.1 4）正是该二叉树的带权路径长度。可见要想获得效率较高的转换程序，可构造以分数的分布比例为权值的哈夫曼树。403060155101530100第5页，本讲稿共20页6.7 6.7 哈夫曼树及应用哈夫曼树及应用3 哈夫曼树的构造哈夫曼树的构造构造哈夫曼树的步骤：1根据给定的n个权值，构造n棵只有一个根结点的二叉树，n个权值分别是这些二叉树根结点的权。设F是由这n棵二叉树构成的集合2在F中选取两棵根结点树值最小的树作为左、右子树，构造一颗新的二叉树，置新二叉树根的权值=左、右子树根结点权值之和；3从F中删除这两颗树，并将新树加入F；4重复 2、3，直到F中只含一颗树为止；第6页，本讲稿共20页6.7 6.7 哈夫曼树及应用哈夫曼树及应用403060155101530403060155101530100例：构造以W=（5，15，40，30，10）为权的哈夫曼树。305101540403015510154030301551015第7页，本讲稿共20页6.7 6.7 哈夫曼树及应用哈夫曼树及应用6.7.26.7.2 哈夫曼编码哈夫曼编码 哈夫曼树除了能求解最优判定问题解，还用于其他一些最优问题的求解。这里介绍用哈夫曼树求解数据的二进制编码。在进行数据通讯时，涉及数据编码问题。所谓数据编码就是数据与二进制字符串的转换。例如：邮局发电报，发送方将原文转换成二进制字符串，接收方将二进制字符串还原成原文。原文 电文（二进制字符串）原文例 要传输的原文为ABACCDA设ABCD的编码为A；00B；01C：10D：11发送方：将ABACCDA 转换成 00010010101100接收方：将 00010010101100 还原为 ABACCDA第8页，本讲稿共20页6.7 6.7 哈夫曼树及应用哈夫曼树及应用 在数据输传时，为省节费用总希望传输的二进制串尽可能短。可利用二叉树设计不等长编码：例 某通讯系统只使用8种字符a、b、c、d、e、f、g、h，其使用频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，利用二叉树设计一种不等长编码：1）构造以 a、b、c、d、e、f、g、h为叶子结点的二叉树；2）将该二叉树所有左分枝标记1，所有右分枝标记0；3）从根到叶子结点路径上标记作为叶子结点所对应字符的编码；a ac cb bd dg gf fe eh ha:0000b:0001c:0010d:0011e:010f:011g:10h:11第9页，本讲稿共20页6.7 6.7 哈夫曼树及应用哈夫曼树及应用 应用中每个字符的使用频率是不一样的。显然，为使传输的二进制串尽可能的短，使用频率高的字符用较短编码，使用频率低的字符用较长编码电文总长=原文中字符总数（字符x使用频率 字符x编码长度）为设计电文总长最短 编码，可通过构造以字符使用频率作为权值的哈夫曼树实现。如何得到使二进制串总长最短编码第10页，本讲稿共20页6.7 6.7 哈夫曼树及应用哈夫曼树及应用例 某通讯系统只使用8种字符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)，按哈夫曼算法构造的一棵哈夫曼树如下：对应字符的编码a:0110b:10c:1110d:1111e:110f:00g:0111h:010292919195858424210010015158 8 7 7 3 3 5 5 8 8 1111232314142929第11页，本讲稿共20页6.7 6.7 哈夫曼树及应用哈夫曼树及应用2构造哈夫曼树的算法输入：n个权值结果：哈夫曼树设用一维数组W存储n个权值，用静态三叉链表HT存储哈夫曼树存储哈夫曼树的静态三叉链表类型定义typedef struct unsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/动态分配数组存储赫夫曼树weight parent lchild rchildHTNode类型的结构变量第12页，本讲稿共20页6.7 6.7 哈夫曼树及应用哈夫曼树及应用w p lch rch0123456789101112131415 5 0 0 029 0 0 0 7 0 0 0 8 0 0 014 0 0 023 0 0 0 3 0 0 011 0 0 0 8 11 1 715 12 3 419 13 8 929 14 5 10 42 15 6 1158 15 2 12100 0 13 14哈夫曼树哈夫曼树对应的静态三叉链表w,p,lch,rch 是weight,parent,lchild,rchild的缩写292919195858424210010015158 8 7 7 3 3 5 5 8 8 1111232314142929第13页，本讲稿共20页6.7 6.7 哈夫曼树及应用哈夫曼树及应用哈夫曼算法void HuffmanTree(HuffmanTree&HT,int*w,int n)/w 存放n 个字符的权值（均0），构造赫夫曼树HTif(n=1)return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/为哈夫曼树分配存储/空间for (p=HT,i=1;i=n;+i,+p,+w)*p=*w,0,0,0;/用给定的n个权/值，构造n棵只有一个根结点的二叉树for(;im;+i;+p)/按构造哈夫曼树的步骤2、3、4，建哈夫曼树/在HT1.i-1 选择parent为0且weight最小的两个结点，其序号分别为s1和s2。Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;/HTi存放新子树的根结点，HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;第14页，本讲稿共20页6.7 6.7 哈夫曼树及应用哈夫曼树及应用例：用哈夫曼算法构造以w=(5,29,7,8,14,23,3,11)为权值的哈夫曼树529781423311012345678W Ww p lch rch0123456789101112131415 5 0 0 029 0 0 0 7 0 0 0 8 0 0 014 0 0 023 0 0 0 3 0 0 011 0 0 0 8 11 1 715 12 3 419 13 8 929 14 5 10 42 15 6 1158 15 2 12100 0 13 14哈夫曼树对应的静态三叉链表HTHTHT算法原始数据算法结果数据权值数组W第15页，本讲稿共20页6.7 6.7 哈夫曼树及应用哈夫曼树及应用0123456789101112131415w p lch rchHTHT为哈夫曼树分配存储空间哈夫曼算法主要步骤图示第16页，本讲稿共20页6.7 6.7 哈夫曼树及应用哈夫曼树及应用0123456789101112131415w p lch rch 5 0 0 029 0 0 0 7 0 0 0 8 0 0 014 0 0 023 0 0 0 3 0 0 011 0 0 0 HTHT算法的第一个FOR循环的执行结果8 棵只有一个结点的二叉树5378 11 2314 29第17页，本讲稿共20页6.7 6.7 哈夫曼树及应用哈夫曼树及应用HTHT算法的第二个FOR循环的执行结果完整的哈夫曼树292919195858424210010015158 8 7 7 3 3 5 5 8 8 1111232314142929静态三叉链表HT对应的哈夫曼树构造哈夫曼树的过程中，新生成的结点w p lch rch0123456789101112131415 5 0 0 029 0 0 0 7 0 0 0 8 0 0 014 0 0 023 0 0 0 3 0 0 011 0 0 0 8 11 1 715 12 3 419 13 8 929 14 5 10 42 15 6 1158 15 2 12100 0 13 14第18页，本讲稿共20页习题 十二1 P41 6.26习题取自习题取自数据结构题集数据结构题集 C C语言版语言版 严尉敏等编严尉敏等编 清华大学出版社清华大学出版社第六章 习 题第19页，本讲稿共20页第20页，本讲稿共20页
