带权路径长度（WPL）#

WPL 定义为所有叶子结点的权值与路径长度（从根到该叶子的边数）的乘积之和：

1
WPL = Σ wᵢ × lᵢ

其中 wᵢ 是第 i 个叶子结点的权值，lᵢ 是从根到该叶子的路径长度（边数）。

示例：对三个权值 {2, 3, 5}，不同的二叉树形态对应的 WPL 不同：

1
  形态1:       5            形态2:     2          形态3:     3
2
            /   \                    /   \               /   \
3
           2     3                  5     3             5     2
4

5
  WPL1 = 2×2 + 3×2 + 5×1 = 15
6
  WPL2 = 5×2 + 3×2 + 2×1 = 18
7
  WPL3 = 5×2 + 2×2 + 3×1 = 17

形态 1 即为哈夫曼树，因为它的 WPL 最小。

哈夫曼树的性质#

证明 2n-1 个结点：n 个叶子结点合并 n-1 次产生 n-1 个新结点，总数为 n + (n-1) = 2n-1。

算法步骤（贪心策略）#

1. 将 n 个权值看作 n 棵只有根结点的二叉树，构成森林 F
2. 每次从 F 中选取权值最小的两棵树作为左右子树，合并为一棵新树，新树的根权值为左右子树权值之和
3. 从 F 中删除这两棵树，加入新树
4. 重复步骤 2-3，直到 F 中只剩一棵树

示例：权值 {7, 5, 2, 4}

1
Step 1: 选出 2 和 4 → 合并为 6
2
  F: {7, 5, 6}
3

4
Step 2: 选出 5 和 6 → 合并为 11
5
  F: {7, 11}
6

7
Step 3: 选出 7 和 11 → 合并为 18
8
  F: {18}  → 完成

1
最终树形：
2
            18
3
          /    \
4
         7     11
5
              /  \
6
             5    6
7
                 / \
8
                2   4
9

10
WPL = 7×1 + 5×2 + 2×3 + 4×3 = 7 + 10 + 6 + 12 = 35

WPL 的等价计算#

哈夫曼树的 WPL 等于所有非叶结点的权值之和。在上例中：

1
WPL = 11 + 6 + 18 = 35

这是因为每个非叶结点的权值恰好是其子树所有叶子权值之和，在合并过程中被重复累加，最终等价于 Σ 叶子权值 × 路径长度。

时间复杂度#

• 使用最小堆（优先队列）实现时，每次取最小元素 O(log n)，共 n-1 次合并
• 总时间复杂度：O(n log n)

1
// 哈夫曼树结点结构
2
typedef struct {
3
    int weight;
4
    int parent, lchild, rchild;
5
} HTNode, *HuffmanTree;

基本概念#

哈夫曼编码（Huffman Coding）是一种基于哈夫曼树的变长编码方案，广泛用于数据压缩。

构建方法#

1. 统计每个字符的出现频率作为权值
2. 用这些权值构建哈夫曼树
3. 从根到每个叶子的路径上，左分支标记 0，右分支标记 1（或相反）
4. 从根到叶子的路径上的 0/1 序列即为该字符的哈夫曼编码

哈夫曼编码的重要性质#

示例：字符 {a, b, c, d} 频率 {4, 2, 1, 1}

1
哈夫曼树：
2
           8
3
         /   \
4
        4     4 (权值和)
5
             / \
6
            2   2
7
               / \
8
              1   1
9

10
编码：
11
  a: 0      (频率 4，1 位)
12
  b: 10     (频率 2，2 位)
13
  c: 110    (频率 1，3 位)
14
  d: 111    (频率 1，3 位)
15

16
平均编码长度 = (4×1 + 2×2 + 1×3 + 1×3) / 8 = 1.75 位/字符

前缀编码的重要性#

若编码集为 {0, 10, 110, 111}，对序列 0110111 可以唯一解码（0 | 110 | 111），不会出现歧义。这是因为哈夫曼树中每个叶子对应一个编码，路径不会相互包含。

相比之下，若采用 {0, 01, 10}，则 010 可以解码为 0|10 或 01|0，存在歧义。

静态哈夫曼 vs 动态哈夫曼#