一、简介

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
在计算机数据处理中，哈夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节，即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1L1+W2L2+W3L3+...+WnLn），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明哈夫曼树的WPL是最小的。

二、理解

当然，看了简介发现一脸懵逼，接下来我用个具体的例子举例，讲解一下哈夫曼树的应用。

例如：acabeaahf

我们在计算机通信过程中要发送这些数据，我们可以用各种编码手段，比如：

假设要把字符串【ABBB】转成二进制编码进行传输
可以使用ASCII编码（65~66，1000001~100101），如下：
        编码：1000001 100101 100101 100101（这里空格是为了阅读方便）
        解码：   A       B      B      B  （每次取7个位即可）

使用ASCII编码有点冗长，怎么样才能使编码更短呢？怎么用最小的bit位把这些数据传递出去呢？这就要用到哈夫曼编码了。
哈夫曼编码和字符出现的频率有紧密的关系，“acabbdaa”这串字符中，a出现4次，b出现2次，c出现1次，d出现一次，即{a:4,b:2,c:1,d:1}。
我们选择最小的频率的字符即{c:1,d:1}，构建一颗树，得到新节点2，即1+1和和。即如下图1所示：