哈夫曼树与哈夫曼编码

哈夫曼树(,Huffman-tree,)

设有一棵二叉树，其只有叶子节点有值，对于每个叶子节点设节点上的值为该叶子节点的权重，设该节点到根节点所经过的边的条数为该节点到根节点的路径长度，树的所有节点的权重与到根节点的路径长度的和为树的带权路径长度。

哈夫曼树是一种针对于二叉树的改良，它将二叉树中较大的值放在离根节点较近的叶子节点，使得树的带权路径长度最小。

构造哈夫曼树

设一组数 {2, 4, 5, 3}，将其每个数转化为一个二叉树节点，组成数组 [2, 4, 5, 3]；

构造新二叉树，取出数组中值最小和次小的两个树节点，作为新二叉树树的左右子树，新节点的值即为左右子树的值之和，再将新二叉树插回数组，重复此步骤直到数组中只剩下一棵二叉树。

1. 取出节点 2 和 3，作为新二叉树的左右子树，将新二叉树插回数组，此时数组为 [4, 5, 5]
2. 取出节点 4 和 5，作为新二叉树的左右子树，将新二叉树插回数组，此时数组为 [5, 9]
3. 取出节点 5 和 9，作为新二叉树的左右子树，将新二叉树插回数组，此时数组为 [ 14 ]。

最终可能的二叉树如下，这两棵树的带权路径长度相同，均为28：

 [14]      |     [14]
  |        |      ||
|---|      |   |------|
5  [9]     |  [5]    [9]
    |      |   |      |
  |---|    | |---|  |---|
  4  [5]   | 2   3  4   5
      |    |
    |---|  |
    2   3  |

哈夫曼编码

哈夫曼编码是对哈夫曼树的典型应用。

前缀编码

对一串字符进行编码有两种编码方式，等长编码和不等长编码。其中对于不等长编码，为了避免编码的歧义性，使用前缀编码（即确保任一编码都不是其它编码的前缀）的方式进行编码，例如：

哈夫曼编码实现逻辑

由于不等长编码的特性，为使编码结果最短，要将较短的编码分配给较频繁使用的字符。

以每个字符出现的频率作为权重，构造一棵哈夫曼树，树中越上层的字符分配越短的编码。

可以通过从节点向下，左子树为0，右子树为1的方式分配编码，例如：

    [  ]
     ||
   0 || 1
  |------|
 [ ]    [ ]
  |      |
0 | 1  0 | 1
|---|  |---|
a   b  c   d

则 a, b, c, d 的编码分别为：

点此查看原文