本节初赛复赛都会考。
如何构造一棵哈夫曼树？（哈夫曼树也是一棵二叉树）
给n个点，每个点都有权值，构造一棵哈夫曼树。每次选剩下的两棵根权值最小的树合并成一棵新树，新树的根权值等于两棵合并前树的根权值和。（一开始一个点也看成一棵树，只不过这棵树没有孩子节点）
例1：4个点，a、b、c、d，权值分别为7、5、2、4。
构树过程：因为4个点，所以合并3次（n个点，合并n-1次）
第一步：选根权值最小的两棵树2（c）和4（d）合并，新树的根节点为6，如图(b)；
第二步：选根权值最小的两棵树5（b）和6合并，新树的根节点为11，如图(c)；
第三步：选根权值最小的两棵树7（a）和11合并，新树的根节点为18，如图(c)；
例2：6个点，a、b、c、d、e、f，权值分别为0.4、0.3、0.1、0.1、0.02、0.08。
构图过程同例1。（如下图）
哈夫曼树的基本概念
树的路径长度PL：从树根到树的每个节点的路径长度（每条边长度为1）之和（完全二叉树为这种路径长度最短的二叉树）。
树的带权路径长度WPL：树的所有叶子节点的带权路径长度（该节点到根节点路径长度与节点上权的乘积）之和。
哈夫曼树：带权路径长度WPL最短的二叉树（最优二叉树）构造这种树的算法最早是由哈夫曼(Huffman)1952年提出，这种树在信息检索中很有用。
例如例1，构造哈夫曼树的WPL为35是最小的。具体比较如下图：
哈夫曼编码
一篇电文，原文为：AMCADEDDMCCAD。现在要把原文转换成01串发送给对方。为了节省资源，我们当然希望翻译好的01串长度尽量的短。怎么办？
研究发现：1、只有5个字母E,M,C,A,D；2、这5个字母的使用频度分别为｛E,M,C,A,D｝=｛1,2,3,3,4｝。
用频度为权值生成哈夫曼树，并在叶子上标注对应的字母，在树枝上标注分配码“0”或“1”（注：分配码不是边的长度，而是区分左右孩子代表方向）:
哈夫曼编码原则： n个节点的哈夫曼树含有2n-1个节点，没有度为1的节点 编码从叶子节点到根节点，译码从根节点到叶子节点。
从哈夫曼树根节点开始，对左子树分配码“0”，右子树分配码“1”，一直到达叶子节点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。
各字母的编码即为哈夫曼编码： EMCAD 所有编码长度和为12位，即PL=12，此时的PL并不是最小的，但此时的WPL一定是最小的。WPL最小才能使得密报翻译的01串长度最短。
例3：对原电文进行哈夫曼编码，如上图，则哈夫曼编码的WPL= 1*3 + 2*3 + 3*2 + 3*2 + 4 *2 = 29 。
例4：对原电文进行等长编码，则：
等长编码的WPL = 1*3 + 2*3 + 3*3 + 3*3 + 4*3 = 39
所以哈夫曼编码可以节省空间。
原电文AMCADEDDMCCAD翻译成01串后为：10001011011000111100101011011。
对方根据事先构造好的哈夫曼树编码表可以还原原电文。
每日练习
1、6个点a、b、c、d、e、f，权值分别为0.5、0.6、0.15、0.1、0.05、0.09，求PL= ( )，WPL=( )。
2、文章中只出现五个字母ABCDE，出现频率=｛6,2,1,2,5｝，求PL= ( )，WPL=( )，其中各个字母的哈夫曼编码为A( )，B( )，C( )，D( )，E( )。
3、最优前缀编码，也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码（ ）
A. (00，01，10，11) B. (0，1，00，11) C. (0，10，110，111) D. (1，01，000，001)
长沙信息学竞赛
联系客服
