1. 哈夫曼树（Huffman Tree）：

定义：

哈夫曼树是一种带权路径长度最短的二叉树，通常用于数据压缩。

它的“最优”体现在权重大的节点离根节点更近，从而使加权路径长度最小。

构造过程：

哈夫曼树的构建基于贪心算法，步骤如下：

  1. 将给定的所有权值看作是森林中的单节点树。
  2. 每次选择两个权值最小的节点进行合并，构成一个新的父节点，其权值为两个子节点的权值之和。
  3. 重复上述过程，直到所有节点合并成一棵二叉树。

应用：

  • 数据压缩：哈夫曼树用于哈夫曼编码，它通过为高频率字符分配较短的编码，低频率字符分配较长的编码，达到压缩数据的目的。

例子：

假设我们有字符集和对应的权值（频率）如下：

字符 频率
A 5
B 9
C 12
D 13
E 16
F 45

构建哈夫曼树的过程如下：

  1. 选择频率最小的 A(5) 和 B(9)，合并为一个新节点，权值为 14。
  2. 再选择 C(12) 和 D(13) 合并，权值为 25。
  3. 合并 14 和 E(16)，权值为 30。
  4. 合并 25 和 F(45)，权值为 70。
  5. 最后合并 30 和 70，得到哈夫曼树的根节点。

这棵树是最优的，因为它最小化了每个字符的加权路径长度。

最终生成的最优二叉树如下：
        R(100)
       /     \
   N3(30)   N4(70)
    /   \      /   \
 A(5)  E(16) N2(25) F(45)
            /   \
         C(12) D(13)

2.赫夫曼编码

为了实现高效率，我们要采取不等长编码原则，以及前缀编码原则

赫夫曼编码过程：

向左用0表示，向右用1表示

根据树的结构：

1
2
3
4
5
6
7
         R(100)
        /     \
    N3(30)   N4(70)
   /   \      /   \
A(5)  E(16) N2(25) F(45)
           /   \
        C(12) D(13)

生成的赫夫曼编码应该是：

  • A: 00
  • E: 01
  • C: 100
  • D: 101
  • F: 11

对应的编码表：

字符 赫夫曼编码
A 00
E 01
C 100
D 101
F 11