资源描述：
《第6章-树和二叉树3.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、6.8哈夫曼树与 哈夫曼编码最优树的定义如何构造最优树前缀编码1有关术语路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。路径长度：路径上的分支数树的路径长度：从树根到每一个结点的路径长度之和树的带权路径长度：树中所有带权结点的路径（WeightedPathLength）长度之和。rdcab2475例如：第k个叶子结点到根的路径长度—个叶子结点的权值第—叶子结点的个数其中：记作：kWPL1kknklwnlkwk-=å=2例有4个结点a,b,c,d，其权值分别为7，5，2，4，构造有4个
2、叶子结点的二叉树abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35VS3哈夫曼树（Huffman树）——又称最优二叉树，它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。教材定义：设有n个权值{w1,w2,……wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则WPL最小的二叉树叫哈夫曼树或最优二叉树。4构造哈夫曼树Huffman给出构造最
3、优二叉树的算法，具体构造哈夫曼算法的步骤如下：⑴根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti(1≤i≤n)中只有一个带权为wi的根结点，其左右子树均空；⑵在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。⑶在F中删除这两棵树，同时将新得到的二叉树加入F中。重复(2)和(3)，直到F只含一棵树为止。这棵树便是所求的赫夫曼树。5例如，对5个权值{5,6,2,9
4、,7}构造最优二叉树的过程如动画所示69例如:已知权值W={5,6,2,9,7}562752769767139527767139527952716671329000011110001101101118例：编制一个将百分制转换成五级分制的程序0～59————————————————————bad60～69————————————————————pass70～79————————————————————general80～89————————————————————good90～100——————————
5、——————————excellentHuffman树的应用：寻求最佳判断过程if(a<60)b=“bad”;elseif(a<70)b=“pass”;elseif(a<80)b＝“general”;elseif(a<90)b=“good”;elseb=“excellent”;………………………5%………………………15%………………………40%………………………30%………………………10%a<60不及格YNa<70及格YNa<80中等YNa<90良好YN优秀根据出现的频率决定比较的次数判定树9出现
6、的频率：10153040515510153030604010070～7980～890～5960～6990～10070≤a<80YN中等80≤a<90YN良好60≤a<70NY及格a<60YN优秀不及格10改造成每个判定框只有一次比较的判定树：a<80YNa<90YN良好Y及格a<60YN优秀不及格a<70N中等实践证明：按照此棵判定树，输入10000个输入数据，原判定树需进行31500次比较，此判定树需进行22000次比较116.6.2赫夫曼编码在电报通讯中，电文是以二进制的0，1序列传送的。编码：在
7、发送端，发送的电文二进制序列译码：在接收端，接到的二进制序列电文12赫夫曼编码提出的背景：（1）如何使电报编码变短，非前缀编码会出现二义性；（2）用二叉树可以构造前缀编码；（3）由哈夫曼树得到最优编码赫夫曼(Huffman)编码是一种常用的压缩编码方法，是Huffman于1952年为压缩文本文件建立的。它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。13编码方式：1）等长编码例：假设传送的电文为英文序列‘A
8、BACCDA’ABCD00011011则电文编码为“00010010101100”，总长14，译码时：两位一分142）不等长编码一般，在英文字母a—z中，e的使用频率比q,z要大得多使用频率高的用短码使用频率低的用长码使用频率：3121ABCD000110电文编码“000011010”，总长9译码：AAAA或BB或ABA原因：A(0)为B(00)的前缀编码不等长，但大部分情况下电文长度会减少15如何得到使电文长度最短的二进制前缀编码？假设电文中每种字符出
