哈夫曼树和哈夫曼编码

1、哈夫曼树（Huffman Tree）

哈夫曼树又称最优二叉树。是一种带权路径长度最短的二叉树。它的定义如下：

假设有n个权值{w1,w2,w3,w4…,wn}，构造一棵有n个节点的二叉树，若树的带权路径最小，则这颗树称作哈夫曼树。

这里面涉及到几个概念，我们由一棵哈夫曼树来解释。

• 路径与路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1；
• 树的路径长度：从根节点到每一节点的路径长度之和；
• 节点的权：将树中的节点赋予一个某种含义的数值作为该节点的权值，该值称为节点的权；
• 带权路径长度：从根节点到某个节点之间的路径长度与该节点的权的乘积。
• 树的带权路径长度：树的带权路径长度为所有叶子节点的带权路径长度之和，称为WPL。而哈夫曼树就是树的带权路径最小的二叉树。

如何构造一棵哈夫曼树：

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

① 将w1、w2、…，wn看成是有n棵树的森林(每棵树仅有一个结点)；

②在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

③从森林中删除选取的两棵树，并将新树加入二叉树中；

④重复②、③步，直到森林中只剩一棵二叉树为止，该树即为所求得的哈夫曼树。

构建的底层可以借助于最小堆算法，可以将原始的数据构造出一个最小堆，然后每次从堆中选取值最小的两个节点，计算他们的权重之和，作为一个新的节点的值，然后插入到最小堆中，直到所有的数据节点都构造完毕，成为一个最大堆，如图所示：

2、哈夫曼编码（Huffman编码）

赫夫曼树的应用十分广泛，比如众所周知的在通信电文中的应用。在等传送电文时，我们希望电文的总长尽可能短，因此可以对每个字符设计长度不等的编码，让电文中出现较多的字符采用尽可能短的编码。为了保证在译码时不出现歧义，我们可以采取如下图所示的编码方式：

上述是为了设计长短不等的编码，以便减少电文的总长，还必须考虑编码的唯一性，即在建立不等长编码时必须使任何一个字符的编码都不是另一个字符的前缀，这宗编码称为前缀编码（prefix code）。

利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树，从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码。