第六章 树和二叉树演示

第六章树和二叉树演示第一页，共二十页，编辑于2023年，星期四第六章树和二叉树6.7哈夫曼树及应用6.7.1哈夫曼树及构造6.7.1哈夫曼编码

第二页，共二十页，编辑于2023年，星期四6.7哈夫曼树及应用6.7.1哈夫曼树及构造1哈夫曼树的概念路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；路径长度：路径上的分支数目称为路径长度；结点的权：根据应用的需要可以给树的结点赋权值；结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；树的带权路径长度=树中所有叶子结点的带权路径之和；

通常记作WPL=wiLi哈夫曼树：假设有n个权值(w1,

w2,…,wn)，构造有n个叶子结点的二叉树，每个叶子结点有一个wi作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。第三页，共二十页，编辑于2023年，星期四6.7哈夫曼树及应用2应用举例在求得某些判定问题时，利用哈夫曼树获得最佳判定算法。例编制一个将百分制转换成五分制的程序。最直观的方法是利用if语句来的实现。可用二叉树描述判定过程。参见课本P145图6.23(a)。如果这个程序很不经常使用，或要转换的分数不多，不必考虑该程序效率，我们可以按照这个流程编程。可是如果该程序经常要使用或数据量很大。比如对北京市几十万小学生的分数进行转换，在这种情况下，要考虑转换程序的效率。

设有10000个百分制分数要转换，设学生成绩在5个等级以上的分布如下：

分数0-5960-6970-7980-8990-100比例数0.050.150.400.300.10第四页，共二十页，编辑于2023年，星期四6.7哈夫曼树及应用按图的判定过程，转换一个分数所需的比较次数=从根到对应结点的路径长度。转换10000个分数所需的总比较次数=10000（0.051+0.152+0.43+0.34+0.14）若将学生成绩在5个等级以上的分布比例看作描述判定过程二叉树叶子结颠点权值，（0.051+0.152+0.43+0.34+0.14）正是该二叉树的带权路径长度。可见要想获得效率较高的转换程序，可构造以分数的分布比例为权值的哈夫曼树。403060155101530100第五页，共二十页，编辑于2023年，星期四6.7哈夫曼树及应用3哈夫曼树的构造构造哈夫曼树的步骤：1．根据给定的n个权值，构造n棵只有一个根结点的二叉树，n个权值分别是这些二叉树根结点的权。设F是由这n棵二叉树构成的集合2．在F中选取两棵根结点树值最小的树作为左、右子树，构造一颗新的二叉树，置新二叉树根的权值=左、右子树根结点权值之和；3．从F中删除这两颗树，并将新树加入F；4．重复2、3，直到F中只含一颗树为止；第六页，共二十页，编辑于2023年，星期四6.7哈夫曼树及应用403060155101530403060155101530100例：构造以W=（5，15，40，30，10）为权的哈夫曼树。305101540403015510154030301551015第七页，共二十页，编辑于2023年，星期四6.7哈夫曼树及应用6.7.2哈夫曼编码

哈夫曼树除了能求解最优判定问题解，还用于其他一些最优问题的求解。这里介绍用哈夫曼树求解数据的二进制编码。

在进行数据通讯时，涉及数据编码问题。所谓数据编码就是数据与二进制字符串的转换。例如：邮局发电报，发送方将原文转换成二进制字符串，接收方将二进制字符串还原成原文。原文电文（二进制字符串）原文例要传输的原文为ABACCDA

设ABCD的编码为

A；00

B；01

C：10

D：11发送方：将ABACCDA转换成00010010101100接收方：将00010010101100还原为ABACCDA第八页，共二十页，编辑于2023年，星期四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）从根到叶子结点路径上标记作为叶子结点所对应字符的编码；acbdgfeha:0000b:0001c:0010d:0011e:010f:011g:10h:11第九页，共二十页，编辑于2023年，星期四6.7哈夫曼树及应用应用中每个字符的使用频率是不一样的。显然，为使传输的二进制串尽可能的短，使用频率高的字符用较短编码，使用频率低的字符用较长编码电文总长=原文中字符总数（字符x使用频率字符x编码长度）

为设计电文总长最短编码，可通过构造以字符使用频率作为权值的哈夫曼树实现。如何得到使二进制串总长最短编码？第十页，共二十页，编辑于2023年，星期四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:01029195842100158

735811231429第十一页，共二十页，编辑于2023年，星期四6.7哈夫曼树及应用2．构造哈夫曼树的算法

输入：n个权值

结果：哈夫曼树设用一维数组W存储n个权值，用静态三叉链表HT存储哈夫曼树存储哈夫曼树的静态三叉链表类型定义typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树weightparentlchildrchildHTNode类型的结构变量第十二页，共二十页，编辑于2023年，星期四6.7哈夫曼树及应用wplchrch01234567891011121314155000290007000800014000230003000110008111715123419138929145104215611581521210001314哈夫曼树哈夫曼树对应的静态三叉链表w,p,lch,rch是weight,parent,lchild,rchild的缩写29195842100158

735811231429第十三页，共二十页，编辑于2023年，星期四6.7哈夫曼树及应用哈夫曼算法voidHuffmanTree(HuffmanTree&HT,int*w,intn){//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(;i<m;++i;++p){//按构造哈夫曼树的步骤2、3、4，建哈夫曼树//在HT[1..i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2。Select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;//HT[i]存放新子树的根结点，HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;第十四页，共二十页，编辑于2023年，星期四6.7哈夫曼树及应用例：用哈夫曼算法构造以w=(5,29,7,8,14,23,3,11)为权值的哈夫曼树529781423311012345678Wwplchrch01234567891011121314155000290007000800014000230003000110008111715123419138929145104215611581521210001314哈夫曼树对应的静态三叉链表HTHT算法原始数据算法结果数据权值数组W第十五页，共二十页，编辑于2023年，星期四6.7哈夫曼树及应用0123456789101112131415wplchrchHT为哈夫曼树分配存储空间哈夫曼算法主要步骤图示第十六页，共二十页，编辑于2023年，星期四6.7哈夫曼树及应用0123456789101112131415wplchrch5000290007000800014000230003000000HT算法的第一个FOR循环的执行结果8棵只有一个结点的二叉树5378

11

2314

29第十七页，共二十页，编辑于2023年，星期四6.7哈夫曼树及应用HT算法的第二个FOR循环的执行结果完整的哈夫曼树29195842100158

735811231429静态三叉链表HT对应的哈夫曼树构造哈夫曼树的过程中，新生成的结点wplchrch012345678910111213141550002900070008000140002300