《数据结构教程(简答易懂)赫夫曼树及其应用》由会员分享，可在线阅读，更多相关《数据结构教程(简答易懂)赫夫曼树及其应用（15页珍藏版）》请在金锄头文库上搜索。
1、赫夫曼树及其应用赫夫曼(Huffman)树，又称最优树，是一类 带权路径长度最短的树。树的带权路径长度：为树中所有叶子结点的带权路径长度之和， 通常记作 nWPL= wklkk=1假设有n个权值w1,w2,wn，试构造一棵 有n个叶子结点的二叉树，每个叶子结点带权为 wi，则其中带权路径长度WPL最小的二叉树称做 最优二叉树或赫夫曼树。 例如，图中的三棵二叉树，都有4个叶子结点a、b 、c、d，分别带权7、5、2、4，它们的带权路径长度 分别为 (a)WPL=7*2+5*2+2*2+4*2=36(b)WPL=7*3+5*3+2*1+4*2=46(c)WPL=7*1+5*2+2*3+4* 3=3
2、5其中以(c)树的为最小。可以验证，它恰为赫夫曼树，即其带 权路径长度在所有带权为7、 5、2、4的四个叶子结点的二叉树中 居最小。cbda(c)abdc(b )dcba(a)The application of HuffmanFor getting the best decision algorithm For communication of coding 利用赫夫曼树可以得到最佳判定算法。例如，要编制一个将百分制转换成五级分 制的程序。显然，此程序很简单，只要利用条件 语句便可完成。如：if(a60)b=“bad”；else if(a70) b=“pass”；else if(a80) b
3、=“general”；else if(a90) b=“good”；else b=“excellent”；这个判定过程可以图 (a)的判定树来表示。如果上 述程序需反复使用，而且每次的输入量很大，则应考 虑上述程序的质量问题，即其操作所需时间。因为在 实际生活中，学生的成绩在五个等级上的分布是不均 匀的。假设其分布规律如下表所示： 分数 0-5960-69 70-79 80-8990-100比例数 0.05 0.15 0.40 0.30 0.10则80以上的数据需进行三次或三次以上的比较才 能得出结果。假定以5，15，40，30和 10为权构造一棵 有五个叶子结点的赫夫曼树，则可得到如图 (b)
4、所示的判 定过程，它可使大部分的数据经过较少的比较次数得出结 果。图 (a) (b)A60A70A80A90良好优秀中等及格不及格YY YYNNNNa6060=a7080=a9070=a80良好中等及格优秀不及格YYNYNNNY但由于每个判定框都有两次比较，将这两次比较 分开，我们得到如图 (c)所示的判定树，按此判定树可 写出相应的程序。假设现有10000个输入数据，若按 图 (a)的判定过程进行操作，则总共需进行31500次比 较；而若按图 (c)的判定过程进行操作，则总共仅需进 行22000次比较。(c)A60A70A80A90中等及格不及格良好优秀如何构造赫夫曼树呢?7 5 2 4(a
5、)7 5 6 7 11 18 (b) (c) (d) 赫夫曼树的构造过程abcdddcbacbadcba赫夫曼最早给出了一个带有一般规律的算法，俗称 赫夫曼算法。如下： (1)根据给定的n个权值W1，W2，Wn构成n 棵二叉树的集合F=T1，T2，Tn，其中每棵二叉树 Ti中只有一个带权为Wi的根结点，其左右子树均空。(2)在F中选取两棵根结点的权值最小的树作为左右 子树构造一棵新的二叉树，且置新的二叉树的根结点的 权值为其左、右子树上根结点的权值之和。(3)在F中删除这两棵树，同时将新得到的二叉树加 入到F中。(4)重复(2)和(3)，直到F只含一棵树为止。这棵树 便是赫夫曼树。赫夫曼编码目
6、前，进行快速远距离通信的主要手段是将需传 送的文字转换成由二进制的字符组成的字符串。例如 ，假设需传送的电文为ABACCDA，它只有四种字符 ，只需两个字符的串便可分辨。假设A、B、C、D的 编码分别为00、01、10和11，则上述七个字符的电文 便为00010010101100，总长14位，对方接收时，可 按二位一分进行译码。当然，在传送电文时，希望总长尽可能地短。如 果对每个字符设计长度不等的编码，且让电文中出现次 数较多的字符采用尽可能短的编码，则传送电文的总长 便可减少。如果设计A、 B、C、D的编码分别为0、00 、1和01，则上述七个字符的电文可转换成总长为9的 字符串000011
7、010。但是，这样的电文无法翻译，例 如传送过去的字符串中前四个字符的子串，0000就可 有多种译法，或是AAAA，或是ABA，也可以是BB ，等。因此，若要设计长短不等的编码，则必须是任一 个字符的编码都不是另一个字符的编码的前缀，这种编 码称做前缀编码。可以利用二叉树来设计 二进制的前缀编码。假设有 一棵如图所示的二叉树，其 四个叶子结点分别表示A、B 、C、D四个字符，且约定左 分支表示字符0，右分支表 示字符1，可以证明，如此得到的 必为二进制前缀编码。如由 图所得A、B、C、D的二进 制前缀编码分别为0、10、 110和111。DCBA前缀编码示例又如何得到使电文总长最短的二进制前缀
8、编码呢? 假设每种字符在电文中出现的次数为wi；，其编码长 度为li，电文中只有n种字符，则电文总长为wili。对 应到二叉树上，若置wi为叶子结点的权，li恰为从根到 叶子的路径长度。则wili恰为二叉树上带权路径长度 。由此可见，设计电文总长最短的二进制前缀编码即 为以n种字符出现的频率作权，设计一棵赫夫曼树的问 题，由此得到的二进制前缀编码便称为赫夫曼编码。 已知某系统在通信联络 中只可能出现八种字符，其 概率分别为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)，n=8， 按上述算法可构造一棵赫夫 曼树如图所示。所得赫夫曼 编码如图 (a) 所示。2329111487531 2 3 4 5 6 7 8(a)赫夫曼编码0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 0
