bitworld 的博客
【CSP-J初赛】哈夫曼树
bitworld 最强壮的男人 SU @ 2025-7-28 16:11:31

哈夫曼编码

1. 编码、压缩与前缀码

1.1 信息的表示与编码

在计算机内部，所有信息，无论是文字、图片还是声音，最终都以二进制的 $0$ 和 $1$ 序列存储和传输。将我们熟悉的字符（如 'a', 'b', 'c'）转换为二进制序列的过程，就是 编码 (Encoding)。

最简单的编码方式是定长编码 (Fixed-Length Code)。例如，标准的 ASCII 码使用 7 个二进制位来表示 128 个不同的字符。在现代计算机系统中，为了方便处理，这些 7 位码通常存储在一个 8 位的字节中，多出的一位可用于扩展 ASCII 字符集或作他用。假设我们只需要编码四个字符 A, B, C, D，我们可以用两位定长二进制数来表示它们：

A -> 00
B -> 01
C -> 10
D -> 11

这种方式的优点是解码非常简单：每读取两位，就能唯一确定一个字符。例如，二进制串 01001110 可以毫不费力地被解码为 BADC。

1.2 变长编码与压缩

然而，定长编码并未考虑字符出现的频率。在一篇英文文章中，字母 'e' 和 't' 的出现频率远高于 'z' 和 'q'。如果我们能用更短的编码表示高频字符，用更长的编码表示低频字符，那么总的编码长度就有可能被大大缩短。这就是变长编码 (Variable-Length Code) 的核心思想，也是数据压缩的基石。

假设我们有一段文本 "AAAAABBC"。其中字符频率为：A: 5, B: 2, C: 1。

定长编码：若使用两位定长编码（A:00, B:01, C:10），编码 "AAAAABBC" 的结果是 0000000000010110，总长度为 $5 \times 2 + 2 \times 2 + 1 \times 2 = 16$ 位。
变长编码：考虑下面这套变长编码：A: 0, B: 10, C: 11。编码 "AAAAABBC" 的结果是 00000101011，总长度为 $5 \times 1 + 2 \times 2 + 1 \times 2 = 11$ 位。

可见，变长编码显著缩短了总长度，实现了数据压缩。

1.3 前缀码：解决解码歧义

变长编码带来了一个新问题：解码的歧义性。考虑这样一套编码：{ A: 0, B: 01, C: 1 }。当接收到二进制串 01 时，解码就出现了问题：它可以被直接完整地匹配为字符 B 的编码；但同时，它的前缀 0 又是字符 A 的编码，而剩下的 1 恰好是字符 C 的编码，因此它也可以被解码为 AC。这种歧义使得我们无法唯一地恢复原文。

为了解决这个问题，我们需要引入前缀码 (Prefix Code)。

前缀码的定义是：任意一个字符的编码都不是另一个字符编码的前缀。

我们上面那套有问题的编码 {A: 0, B: 01, C: 1} 就不是前缀码，因为 A 的编码 0 是 B 的编码 01 的前缀。
而我们在前面例子中成功使用的变长编码 {A: 0, B: 10, C: 11} 是一套有效的前缀码。0 不是 10 或 11 的前缀；10 不是 0 或 11 的前缀；11 也不是 0 或 10 的前缀。

使用前缀码，解码过程是无歧义的。解码器从左到右扫描二进制串，一旦当前扫描到的序列匹配了一个字符的编码，就立即将其译出，然后从下一个比特位开始重复该过程。例如，对于二进制串 0101011 和编码表 {A: 0, B: 10, C: 11}（假设原文为 "ABBC"）：

读取 0。这与字符 'A' 的编码匹配。译出 A。
从下一位开始，读取 1。没有字符的编码是 1。继续读取下一位，得到 10。这与字符 'B' 的编码匹配。译出 B。
从下一位开始，再次读取 1，然后是 0，得到 10。这与字符 'B' 的编码匹配。译出 B。
从下一位开始，读取 1，然后是 1，得到 11。这与字符 'C' 的编码匹配。译出 C。

最终解码为 "ABBC"，与原文一致。由于前缀码的特性，解码器在任何时候匹配到一个编码时，都不需要担心它会是另一个更长编码的一部分，从而保证了解码的唯一性和即时性。

2. 哈夫曼树：最优前缀码的构造

哈夫曼编码的目标是，找到一种最优的前缀码方案，使得编码后的总长度（即带权路径长度）最小。

2.1 编码树

前缀码可以很自然地用一棵二叉树来表示，这棵树我们称为编码树 (Coding Tree) 或前缀树 (Prefix Tree)。

所有待编码的字符都作为叶子节点。
从根节点到任意一个叶子节点的路径代表了该叶子节点的编码。
路径的每一条左分支代表 0，右分支代表 1。

由于所有字符都在叶子节点上，从根到一个叶子的路径不可能成为到另一个叶子路径的前缀，因此这样构造出的编码天然满足前缀码的性质。

2.2 带权路径长度 (WPL)

我们的优化目标是最小化编码后的总长度。假设一个字符 $c_i$ 的频率（或称为权值）为 $w_i$ ，其在编码树中的深度为 $d_i$ （根节点深度为0），那么其编码长度就是 $d_i$ 。

编码一段文本后的总长度可以表示为：

WPL = \sum_{i=1}^{n} w_i d_i

这个值被称为树的带权路径长度 (Weighted Path Length, WPL)。哈夫曼算法的目标就是构造一棵具有最小 WPL 的二叉树，这棵树就被称为哈夫曼树 (Huffman Tree)，也叫最优二叉树。

2.3 哈夫曼算法核心思想

哈夫曼算法采用的是一种贪心策略 (Greedy Strategy)。其核心思想是：权值越大的叶子，应该离根节点越近；权值越小的叶子，应该离根节点越远。

为了实现这一点，算法总是将当前所有节点中权值最小的两个节点合并，形成一个新的父节点。这个新父节点的权值是它两个子节点权值之和。这个过程不断重复，直到最后只剩下一个节点，即根节点。

3. 哈夫曼树的构建步骤

我们通过一个具体的例子来完整演示哈夫曼树的构建和编码的生成过程。问题：为字符串 "SUCCESS IS SUCCESS" 生成哈夫曼编码。

步骤 1：统计字符频率 (计算权值)

首先，统计每个字符出现的次数（忽略空格）。字符串 "SUCCESSISSUCCESS" 共16个字符。

S: 7次
U: 2次
C: 4次
E: 2次
I: 1次

我们得到五个带权值的字符：{ (I, 1), (U, 2), (E, 2), (C, 4), (S, 7) }。

步骤 2：初始化节点

将每个字符看作一个独立的叶子节点。我们有一个节点集合，按权值从小到大排序： [ (I, 1), (U, 2), (E, 2), (C, 4), (S, 7) ]

步骤 3：迭代合并

重复以下过程：从集合中选出权值最小的两个节点，将它们合并成一棵新树。新树的根节点的权值为两个子节点权值之和。然后用这个新节点替换掉原来的两个节点。

第 1 次合并：

最小的两个节点是 (I, 1) 和 (U, 2)。
合并它们，创建一个新的内部节点，权值为 $1 + 2 = 3$ 。
节点集合变为：[ (E, 2), (New, 3), (C, 4), (S, 7) ]
```
  (3)
 /   \
(I,1) (U,2)
```

第 2 次合并：

当前最小的两个节点是 (E, 2) 和权值为 3 的新节点。
合并它们，新父节点的权值为 $2 + 3 = 5$ 。

节点集合变为：[ (C, 4), (New, 5), (S, 7) ]

     (5)
    /   \
  (E,2) (3)
       /   \
      (I,1) (U,2)

第 3 次合并：

最小的两个节点是 (C, 4) 和权值为 5 的新节点。
合并它们，新父节点的权值为 $4 + 5 = 9$ 。

节点集合变为：[ (S, 7), (New, 9) ]

        (9)
       /   \
     (C,4) (5)
          /   \
        (E,2) (3)
             /   \
            (I,1) (U,2)

注意：在选择合并节点时，如果存在多个权值相同的节点，任选两个即可。例如第一次合并时，如果还有另一个权值为1的节点，选择哪个都会得到相同的WPL，但具体编码可能不同。

第 4 次合并：

只剩下最后两个节点：(S, 7) 和权值为 9 的新节点。
合并它们，得到根节点，权值为 $7 + 9 = 16$ 。
集合中只剩下一个节点，构建完成。

最终的哈夫曼树如下：

           (16)
          /    \
        (S,7)  (9)
             /   \
           (C,4) (5)
                /   \
              (E,2) (3)
                   /   \
                  (I,1) (U,2)

步骤 4：生成哈夫曼编码

从根节点开始遍历树，约定左分支为 0，右分支为 1。到达每个叶子节点的路径就构成了该字符的哈夫曼编码。

S: 从根向左，路径是 0。编码为 0。
C: 从根向右再向左，路径是 10。编码为 10。
E: 从根向右、右、左，路径是 110。编码为 110。
I: 从根向右、右、右、左，路径是 1110。编码为 1110。
U: 从根向右、右、右、右，路径是 1111。编码为 1111。

最终得到的哈夫曼编码表：

S: 0
C: 10
E: 110
I: 1110
U: 1111

可以看到，频率最高的 'S' 编码最短，频率最低的 'I' 编码最长，这符合哈夫曼编码的优化目标。

该哈夫曼树的 WPL 计算： $WPL = 7 \times 1(\text{S}) + 4 \times 2(\text{C}) + 2 \times 3(\text{E}) + 1 \times 4(\text{I}) + 2 \times 4(\text{U})$ $WPL = 7 + 8 + 6 + 4 + 8 = 33$

4. C++ 代码实现

在 C++ 中，实现哈夫曼树的关键是使用优先队列 (priority_queue) 来高效地找到并提取权值最小的两个节点。优先队列本质上是一个堆 (Heap)，默认是最大堆，我们需要将其改造为最小堆。

题意概括

给定 N 个字符的权值，构造哈夫曼树，并计算其带权路径长度 WPL。

核心代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 树节点结构体
struct Node {
    ll w; // 节点的权值
    Node *l, *r; // 左右子节点指针

    // 构造函数
    Node(ll w, Node* l = nullptr, Node* r = nullptr) : w(w), l(l), r(r) {}
};

// 自定义优先队列的比较器
// 使其成为一个基于节点权值的最小堆
struct Cmp {
    bool operator()(const Node* a, const Node* b) const {
        return a->w > b->w; // 权值小的优先级高
    }
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;
    cin >> n; // 输入字符数量

    priority_queue<Node*, vector<Node*>, Cmp> pq;

    for (int i = 0; i < n; ++i) {
        ll w;
        cin >> w; // 输入每个字符的权值
        pq.push(new Node(w)); // 创建叶子节点并加入优先队列
    }

    if (n == 1) {
        // 边界情况：只有一个字符。
        // WPL的定义是 sum(w_i * d_i)。若只有一个节点，它既是根也是叶，深度d=0，WPL=0。
        // 但在一些题目中，可能规定单字符编码长度为1，此时WPL=w。
        // 此处遵循WPL是所有合并代价之和的计算方式，n=1时没有合并，代价为0。
        cout << 0 << endl; 
        return 0;
    }

    ll wpl = 0; // 初始化WPL
    
    while (pq.size() > 1) {
        // 1. 取出权值最小的两个节点
        Node* a = pq.top(); pq.pop();
        Node* b = pq.top(); pq.pop();

        // 2. 合并，新节点的权值是合并代价
        ll sum = a->w + b->w;
        wpl += sum; // 关键：WPL等于所有非叶子节点的权值之和

        // 3. 创建新的父节点，并放回队列
        pq.push(new Node(sum, a, b));
    }

    cout << wpl << endl; // 输出最终的WPL

    // 注意：实际应用中需要释放动态分配的内存
    // 但在算法竞赛中，通常省略以保持代码简洁
    return 0;
}

代码解释

Node 结构体：定义了树的节点，包含权值 w 和指向左右孩子的指针 l 和 r。
Cmp 结构体：我们为优先队列 priority_queue 提供了一个自定义比较器 Cmp。pq 默认是最大堆，a->w > b->w 返回 true 会将 a 排在 b 的后面，从而实现了最小堆的效果。
主逻辑：
- 读取所有叶子节点的权值，创建 Node 对象并放入最小优先队列 pq。
- 循环执行直到队列里只剩一个节点（根节点）。在每次循环中：
  - 从 pq 中弹出两个权值最小的节点 a 和 b。
  - 创建一个新的父节点，其权值为 a->w + b->w，左右孩子分别为 a 和 b。
  - 将这个新的父节点压入 pq。
WPL 计算：有一个重要的性质：当哈夫曼树的节点数大于1时，其 WPL 等于所有非叶子节点（内部节点）的权值之和。在我们的代码中，wpl += sum; 正是利用了这个性质。每次合并产生的 sum 就是一个新内部节点的权值。累加所有这些权值，就得到了最终的 WPL。
复杂度分析：
- 时间复杂度：假设有 $N$ $N$ 个初始叶子节点。将 $N$ $N$ 个节点 push 进优先队列，每次 push 是 $O(\log k)$ $O (lo g k)$ （ $k$ $k$ 是当前队列大小），总共是 $O(N \log N)$ $O (N lo g N)$ 。之后循环执行 $N-1$ $N - 1$ 次合并。每次合并涉及两次 pop ( $O(\log N)$ $O (lo g N)$ ) 和一次 push ( $O(\log N)$ $O (lo g N)$ )。所以总时间复杂度是 $O(N \log N)$ $O (N lo g N)$ 。
  - 注：若所有权值一次性给出，可用 std::make_heap 在 $O(N)$ 时间内建堆，但后续合并操作仍需 $O(N \log N)$ ，故总复杂度不变。
- 空间复杂度：优先队列中最多存储 $N$ 个节点指针，并且我们创建了 $N-1$ 个内部节点。总空间复杂度是 $O(N)$ 。

5. 考点与练习

哈夫曼树编码是笔试和面试中的高频考点。

5.1 判断与选择题

1. (判断题) 哈夫曼编码是一种无损压缩算法。

答案： 正确。哈夫曼编码是完全可逆的，解码后可以精确地恢复原始数据，没有信息损失。

2. (判断题) 在一棵哈夫曼树中，权值最大的叶子节点一定离根节点最近。

答案： 正确。这是哈夫曼算法贪心策略的直接结果，也是其最优性的保证。

3. (判断题) 对于同一组权值，构造出的哈夫曼树是唯一的。

答案： 错误。当合并过程中出现两个或以上权值最小且相等的节点时，选择哪两个进行合并具有任意性。这会导致最终树的形态不同，从而编码也不同。但是，它们的带权路径长度 WPL 必定是相同的，都是最优的。

4. (选择题) 对 {a:5, b:30, c:12, d:18, e:25, f:10} 这 6 个字符进行哈夫曼编码，则该哈夫曼树的带权路径长度 (WPL) 是多少？

A. 250 B. 242 C. 305 D. 320

解题思路： 按照算法步骤合并，并累加所有中间节点的权值。

初始权值: [5, 10, 12, 18, 25, 30]

合并 5 和 10，得新节点 15。WPL += 15。队列: [12, 15, 18, 25, 30]

合并 12 和 15，得新节点 27。WPL += 27。队列: [18, 25, 27, 30]

合并 18 和 25，得新节点 43。WPL += 43。队列: [27, 30, 43]

合并 27 和 30，得新节点 57。WPL += 57。队列: [43, 57]

合并 43 和 57，得新节点 100。WPL += 100。队列: [100]

总 WPL = $15 + 27 + 43 + 57 + 100 = 242$ 。

答案： B

5.2 程序阅读与补全

1. (程序补全) 下面的代码段用于从已构建好的哈夫曼树 root 生成各个字符的编码，并存入 map<char, string>& codes 中。请补全 dfs 函数。

#include<bits/stdc++.h>
using namespace std;

// 假设Node结构体已定义，包含 char c, Node *l, Node *r;
// 叶子节点的 l 和 r 为 nullptr, c 为对应字符
// 非叶子节点的 c 为特殊空字符

void dfs(Node* u, string cur, map<char, string>& codes) {
    if (u == nullptr) return;

    // 如果是叶子节点
    if (u->l == nullptr && u->r == nullptr) {
        codes[u->c] = cur;
        return;
    }

    // _______________ (1) _______________
    
    // _______________ (2) _______________
}

int main() {
    // ... 假设已构建哈夫曼树，得到 root ...
    map<char, string> codes;
    dfs(root, "", codes); // 从根节点开始，初始编码为空串
    // ... 打印 codes ...
}

答案： (1) dfs(u->l, cur + '0', codes); (2) dfs(u->r, cur + '1', codes);

解析： 这是一个标准的深度优先搜索 (DFS) 遍历。cur 变量保存从根到当前节点 u 的路径编码。当向左子树递归时，当前编码追加 0；向右子树递归时，追加 1。当到达一个叶子节点时，cur 就是该叶子节点对应字符的完整哈夫曼编码，将其存入 map 中。

【CSP-J初赛】哈夫曼树