赫夫曼树

过去我们小学、中学一般考试都是用百分制来表示学科成绩的。这带来了一个弊端，就是很容易让学生、家长，甚至老师自己都以分取人，让分数代表了一切。有时想想也对，90分和95分也许就只是一道题目对错的差距，但却让两个孩子可能受到完全不同的待遇，这并不公平。于是在如今提倡素质教育的背景下，我们很多的学科，特别是小学的学科成绩都改作了优秀、良好、中等、及格和不及格这样模糊的词语，不再通报具体的分数。

不过对于老师来讲，他在对试卷评分的时候，显然不能凭感觉给优良或及格不及格等成绩，因此一般都还是按照百分制算出每个学生的成绩后，再根据统一的标准换算得出五级分制的成绩。比如下面的代码就实现了这样的转换。

if (a < 60)
    b = "不及格";
else if (a < 70)
    b = "及格";
else if (a < 80)
    b = "中等";
else if (a < 90)
    b = "良好";
else
    b = "优秀";

上面的代码粗略看没什么问题，可是通常都认为，一张好的考卷应该是让学生成绩大部分处于中等或良好的范围，优秀和不及格都应该较少才对。而上面这样的程序，就使得所有的成绩都需要先判断是否及格，再逐级而上得到结果。输入量很大的时候，其实算法是有效率问题的。

如果在实际的学习生活中，学生的成绩在5个等级上的分布规律如下图所示

image-20200505214324174

那么70分以上大约占总数80%的成绩都需要经过3次以上的判断才可以得到结果，这显然不合理。

有没有好一些的办法，仔细观察发现，中等成绩（70～79分之间）比例最高，其次是良好成绩，不及格的所占比例最少。我们把图6-12-2这棵二叉树重新进行分配。改成如下图的做法试试看。

image-20200505214400687

赫夫曼树定义与原理

我们先把这两棵二叉树简化成叶子结点带权的二叉树（注：树结点间的边相关的数叫做权Weight），如图下所示。其中A表示不及格、B表示及格、C表示中等、D表示良好、E表示优秀。每个叶子的分支线上的数字就是刚才我们提到的五级分制的成绩所占百分比。

image-20200505214754902

赫夫曼大叔说，从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度。上图的二叉树a中，根结点到结点D的路径长度就为4，二叉树b中根结点到结点D的路径长度为2。树的路径长度就是从树根到每一结点的路径长度之和。二叉树a的树路径长度就为1+1+2+2+3+3+4+4=20。二叉树b的树路径长度就为1+2+3+3+2+1+2+2=16。

带权结点路劲的计算

“如果考虑到带权的结点，结点的带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。假设有n个权值{w1,w2,...,wn}，构造一棵有n个叶子结点的二叉树，每个叶子结点带权wk，每个叶子的路径长度为lk，我们通常记作，则其中带权路径长度WPL最小的二叉树称做赫夫曼树。也有不少书中也称为最优二叉树，我个人觉得为了纪念做出巨大贡献的科学家，既然用他们的名字命名，就应该要坚持用他们的名字称呼，哪怕“最优”更能体现这棵树的品质也应该只作为别名。

有了赫夫曼对带权路径长度的定义，我们来计算一下上图这两棵树的WPL值。

二叉树a的WPL=5×1+15×2+40×3+30×4+10×4=315

注意：这里5是A结点的权，1是A结点的路径长度，其他同理。

二叉树b的WPL=5×3+15×3+40×2+30×2+10×2=220

这样的结果意味着什么呢？如果我们现在有10000个学生的百分制成绩需要计算五级分制成绩，用二叉树a的判断方法，需要做31500次比较，而二叉树b的判断方法，只需要22000次比较，差不多少了三分之一量，在性能上提高不是一点点。

赫夫曼树的构建

1．先把有权值的叶子结点按照从小到大的顺序排列成一个有序序列，即：A5，E10，B15，D30，C40。

2．取头两个最小权值的结点作为一个新节点N1的两个子结点，注意相对较小的是左孩子，这里就是A为N1的左孩子，E为N1的右孩子，如下图所示。新结点的权值为两个叶子权值的和5+10=15。

image-20200505215904388

3．将N1替换A与E，插入有序序列中，保持从小到大排列。即：N115，B15，D30，C40。

4．重复步骤2。将N1与B作为一个新节点N2的两个子结点。如下图所示。N2的权值=15+15=30。

image-20200505220014279

5．将N2替换N1与B，插入有序序列中，保持从小到大排列。即：N230，D30，C40。

6．重复步骤2。将N2与D作为一个新节点N3的两个子结点。如下图所示。N3的权值=30+30=60。

image-20200505220119727

7．将N3替换N2与D，插入有序序列中，保持从小到大排列。即：C40，N360。

8．重复步骤2。将C与N3作为一个新节点T的两个子结点，如图6-12-8所示。由于T即是根结点，完成赫夫曼树的构造。

image-20200505220205273

此时的二叉树的带权路径长度WPL=40×1+30×2+15×3+10×4+5×4=205。与上面的二叉树b的WPL值220相比，还少了15。显然此时构造出来的二叉树才是最优的赫夫曼树。

通过刚才的步骤，我们可以得出构造赫夫曼树的赫夫曼算法描述。

1. 根据给定的n个权值{w1,w2,...,wn}构成n棵二叉树的集合F={T1,T2,...,Tn}，其中每棵二叉树Ti中只有一个带权为wi根结点，其左右子树均为空。
2. 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3. 在F中删除这两棵树，同时将新得到的二叉树加入F中。
4. 重复2和3步骤，直到F只含一棵树为止。这棵树便是赫夫曼树。”

赫夫曼编码

比如我们有一段文字内容为“BADCADFEED”要网络传输给别人，显然用二进制的数字（0和1）来表示是很自然的想法。我们现在这段文字只有六个字母ABCDEF，那么我们可以用相应的二进制数据表示，如下图所示。

image-20200505220649854

这样真正传输的数据就是编码后的“001000011010000011101100100011”，对方接收时可以按照3位一分来译码。如果一篇文章很长，这样的二进制串也将非常的可怕。而且事实上，不管是英文、中文或是其他语言，字母或汉字的出现频率是不相同的，比如英语中的几个元音字母“ae i o u”，中文中的“的 了 有 在”等汉字都是频率极高。

假设六个字母的频率为A 27，B 8，C 15，D15，E 30，F 5，合起来正好是100%。那就意味着，我们完全可以重新按照赫夫曼树来规划它们。

下图左图为构造赫夫曼树的过程的权值显示。右图为将权值左分支改为0，右分支改为1后的赫夫曼树。

image-20200505220908436

此时，我们对这六个字母用其从树根到叶子所经过路径的0或1来编码，可以得到如下图所示这样的定义。

image-20200505220942005

我们将文字内容为“BADCADFEED”再次编码，对比可以看到结果串变小了。

• 原编码二进制串：001000011010000011101100100011（共30个字符）
• 新编码二进制串：1001010010101001000111100（共25个字符）

因此在解码时，还是要用到赫夫曼树，即发送方和接收方必须要约定好同样的赫夫曼编码规则。

当我们接收到1001010010101001000111100时，由约定好的赫夫曼树可知，1001得到第一个字母是B，接下来01意味着第二个字符是A，

一般地，设需要编码的字符集为{d1,d2,...,dn}，各个字符在电文中出现的次数或频率集合为{w1,w2,...,wn}，以d1,d2,...,dn作为叶子结点，以w1,w2,...,wn作为相应叶子结点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表0，右分支代表1，则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，这就是赫夫曼编码。