Huffman Tree，中文名是哈夫曼树或霍夫曼树，它是最优二叉树。

如果有一篇文章，由若干个字符构成。每个ABC…Z都由7位编码，文章有1w个字符，那么有7w位进行编码。一个字节8位，首位是0。需要占用1W个字节。

实际中每个单词的出现频率是不同的，比如e在文章中出现频率较高，我用5位给它编码，出现频率较低的使用7位、8位或者9位。这样效率会得到提高。

看一个具体的例子：

判定树：

倘若绝大数人的成绩到90分以上，很少人不及格。而每次查询90分以上需要进行4次判断，这样效率较低

如果学生的成绩分布概率： 查找效率为：0.051 + 0.151 + 0.42 + 0.33 + 0.1*4 = 3.15

修改判定树：

查找效率：0.053 + 0.153 + 0.42 + 0.32 + 0.1*2 = 2.2

如何根据节点不同的查找频率构造更有效的搜索树？这就是哈夫曼树要解决的问题

先了解几个定义： 1．树的路径长度 树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。

2．树的带权路径长度(Weighted Path Length of Tree，简记为WPL) 结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。 结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。

树的带权路径长度 (Weighted Path Length of Tree)：定义为树中所有叶结点的带权路径长度之和，通常记为： WPL=(W1L1+W2L2+W3L3+…+WnLn)

其中：Wi 和 Li 分别表示叶结点的权值和根到结点之间的路径长度。 树的带权路径长度亦称为树的代价。

假设有 n 个权值[W1,W2,…WN]，构造有 n 个叶子的二叉树，每个叶子的权值是 n 个权值之一，这样的二叉树可以构造很多个，其中必有一个是带权路径长度最小的，这棵二叉树就称为最优二叉树或哈夫曼树。

每次把权值最小的两棵二叉树合并 例子：

给定一段字符串，如何对字符进行编码，可以使得该字符串的编码存储空间最少？

第一种方式效率低，第二种方式是一种方式的改进。只要3位，2的三次方为8，可以包含7个字符。那我们试试哈夫曼编码？

问题出现：二义性，一个编码可能有多种解码方式。 所以要解决二义性问题，采用前缀码：任何字符的编码都不是另一字符编码的前缀。在用哈夫曼编码解决这个问题之前，先看一下普通二叉树编码和哈夫曼编码的区别

用二叉树进行编码：

要使代价小，要使得编码效率的提升，这就转换成哈夫曼树的问题。

这个例子采用改用哈夫曼编码：

哈夫曼编码的优点：

最后解决一下前面遗留的问题： 本文内容参考自：浙江大学陈越、何钦铭的公开课