大话数据结构十六：哈夫曼树（最优二叉树）

大话数据结构十六：哈夫曼树（最优二叉树）2014-12-301. 引子

当前素质教育的背景下，小学的学科成绩都改为了优秀、良好、及格、不及格这样的模糊词语，而不再通报具体的分数。

用代码可以表示如下：

if（ a < 60 ）System.out.print（"不及格"）;else if（ a < 70 ）System.out.print（"及格"）;else if（ a < 90 ）System.out.print（"良好"）;elseSystem.out.print（"优秀"）;

粗略看这样做是没问题的，但是一张好的试卷大部分学生成绩集中在"良好"，而上面的程序需要判断两次才能到"良好"，输入量很大的时候，在算法效率上其实是有问题的。所以应该做如下改进（① -> ②）：

2. 哈夫曼树定义和原理

我们先把上图简化成叶子结点带权的二叉树（注：树结点间的连线相关的数叫做权，Weight）。

① 结点的路径长度：从根结点到该结点的路径上的连接数。

② 树的路径长度：树中每个叶子结点的路径长度之和。

③ 结点带权路径长度：结点的路径长度与结点权值的乘积。

④ 树的带权路径长度：WPL（Weighted Path Length）是树中所有叶子结点的带权路径长度之和。

※WPL的值越小，说明构造出来的二叉树性能越优，这种最优二叉树又称为哈夫曼树。