CC++ & Algorithm

哈夫曼树：最省力的编码树

极难14
语言版本：C++Python
概述：哈夫曼树是一种带权路径长度最短的二叉树，常用于数据压缩，比如把经常用的字母用短编码表示。

哈夫曼树：像整理书包一样给信息编码

你有没有想过，为什么电脑能把一张图片或一段文字压缩得特别小？秘密就藏在一种叫做“哈夫曼树”的神奇结构中。哈夫曼树是一种 带权路径长度最短 的二叉树，它最擅长做一件事：数据压缩 —— 把常见的符号用尽量短的编码表示，不常见的符号用长一点的编码，这样整体长度就大大缩短了。

就好像你整理书包：每天必用的课本放在最外面（短编码），偶尔才用的彩笔塞在最里面（长编码），这样你拿书的速度最快。哈夫曼树也是这么想的。

1. 为什么需要哈夫曼树？—— 生活中的“最省力”原则

假设老师要求你统计班里同学最喜欢的零食，并给每种零食编一个“数字暗号”，方便写在卡片上。如果每样零食都用两个数字表示（比如01代表薯片，02代表巧克力，03代表糖果），那么写100次“薯片”就需要200个数字。但薯片是大家最喜欢的，出现了60次！如果给薯片单独一个短编码“0”，那60次薯片只需要60个数字，比原来省了60个数字。这就是哈夫曼的聪明之处：频率高的给短码，频率低的给长码。

再举一个例子：在中文里，“的”字几乎每句话都有，而“饕餮”可能一篇文章才出现一次。如果所有字都用相同的比特数（比如每个字16位），那文章会很长。哈夫曼编码就能让“的”用“0”表示，“饕餮”用“1011”表示，从而压缩全文。

2. 核心概念：什么是“带权路径长度”？

在树中，路径长度就是从根节点走到某个节点需要经过的边数。如果这个节点“有重量”（比如字符出现的次数），那么从根到该节点的路径长度 × 该节点的重量，就是该节点的带权路径长度。整棵树的**带权路径长度（WPL）**就是所有叶子节点带权路径长度之和。

哈夫曼树的目标就是让这个 WPL 最小。想象一下：你把最重的书放在离书包口最近的位置，这样每次拿它都最省力。哈夫曼树就是把“重量”（频率）大的节点放在离根最近的位置（路径短），让整体“搬运”最省力。

3. 怎么构造哈夫曼树？—— 像玩“合并纸团”游戏

构造过程超级简单，你只需要第1步和第2步不断重复：

  1. 准备材料：把每个字符当作一个纸团，纸团上的数字就是它出现的次数（频率）。
  2. 每次挑出两个最轻的纸团，把它们揉成一个新纸团，新纸团上的数字是两数之和，然后把新纸团放回堆里。
  3. 重复第二步，直到只剩一个纸团。这个纸团就是哈夫曼树的根。

举个例子：假设有字符 a(5次), b(9次), c(12次), d(13次), e(16次), f(45次)。我们来玩一下：

  • 第一次：最小的两个是 a(5) 和 b(9)，合并成新节点 14，放回。现在集合有：14, c(12), d(13), e(16), f(45)。
  • 第二次：最小的两个是 c(12) 和 d(13)，合并成 25，放回。集合：14, e(16), 25, f(45)。
  • 第三次：最小的两个是 14 和 e(16)，合并成 30，放回。集合：25, 30, f(45)。
  • 第四次：最小的两个是 25 和 30，合并成 55，放回。集合：55, f(45)。
  • 第五次：最后两个是 55 和 f(45)，合并成 100。结束。

这样我们就得到了一棵二叉树，其中叶节点就是原来的 a~f，内部节点是合并过程中产生的新节点。

4. 编码规则：左0右1，没有歧义

构造好树之后，从根节点出发，往左子树走一步写“0”，往右子树走一步写“1”。这样每个叶子节点（原来的字符）都会得到一个独一无二的二进制串。而且因为这些编码都是叶子节点，没有任何一个编码是另一个编码的前缀（叫做“前缀编码”），所以解码时不会搞混。

比如上面例子中，f 的频率最高（45），它的路径最短——可能只有“0”或“1”这样一位编码。而 a 和 b 频率最低，路径最长，编码可能有4位。

5. 用C++实现哈夫曼树：代码一步步讲解

我们用**优先队列（最小堆）**来每次快速找出两个最小权重的节点。下面这段代码包含了完整的构造、编码输出功能。

#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;

// 定义树节点结构体
struct HuffmanNode {
    char ch;             // 如果是叶子节点，存字符；内部节点设为'#'
    int freq;            // 频率（权重）
    HuffmanNode *left;   // 左孩子指针
    HuffmanNode *right;  // 右孩子指针
    // 构造函数：初始化字符、频率、左右孩子为空
    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

// 比较器：用于优先队列，让频率小的节点优先级高（最小堆）
struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;  // 注意：大于号实现最小堆
    }
};

// 递归遍历树，生成每个字符的哈夫曼编码
void buildCodes(HuffmanNode* root, string prefix, vector<string>& codes) {
    if (!root) return;                    // 空节点直接返回
    if (root->ch != '#') {                // 遇到叶子节点（字符不是'#'）
        codes[root->ch] = prefix;         // 将当前路径作为该字符的编码
        return;
    }
    // 非叶子：向左走加"0"，向右走加"1"，继续递归
    buildCodes(root->left, prefix + "0", codes);
    buildCodes(root->right, prefix + "1", codes);
}

int main() {
    // 字符数组，共6个字符
    char chars[] = {'a', 'b', 'c', 'd', 'e', 'f'};
    // 各字符对应的频率（出现次数）
    int freq[] = {5, 9, 12, 13, 16, 45};
    int n = 6;  // 字符个数

    // 创建优先队列（最小堆），存储HuffmanNode指针
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;

    // 将所有叶子节点放入优先队列
    for (int i = 0; i < n; ++i) {
        pq.push(new HuffmanNode(chars[i], freq[i]));
    }

    // 合并过程：每次从队列取出两个最小的，合并后放回
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top(); pq.pop();   // 取出最小的节点
        HuffmanNode* right = pq.top(); pq.pop();  // 取出第二小的节点
        // 创建内部节点，字符设为'#'，频率为左右孩子之和
        HuffmanNode* internal = new HuffmanNode('#', left->freq + right->freq);
        internal->left = left;   // 左孩子指向最小的节点
        internal->right = right; // 右孩子指向第二小的节点
        pq.push(internal);       // 将新节点放回队列
    }

    // 队列中剩下的唯一节点就是哈夫曼树的根
    HuffmanNode* root = pq.top();

    // 准备一个数组存放所有字符的编码，大小为256（ASCII范围）
    vector<string> codes(256);
    // 从根开始生成编码
    buildCodes(root, "", codes);

    // 输出每个字符的哈夫曼编码
    cout << "字符编码：" << endl;
    for (int i = 0; i < n; ++i) {
        cout << chars[i] << ": " << codes[chars[i]] << endl;
    }

    return 0;
}

6. 常见错误（新手最容易踩的坑）

  • 错误1：忘记处理叶子节点以外的内部节点
    在递归生成编码时，只对叶子节点（ch != '#'）保存编码。如果忘记判断，内部节点的ch是随便的字符，会导致错误。

  • 错误2：优先队列的比较符号写反
    如果想实现最小堆，Compare里的operator()应该返回a->freq > b->freq。如果写成<，就会变成最大堆，每次取出频率最大的两个节点，得到的就不是哈夫曼树了。

  • 错误3：忘记释放动态分配的内存
    代码中用new创建了大量节点，但没有delete。虽然程序结束会自动回收，但在大型项目中可能导致内存泄漏。可以写一个递归函数来释放整棵树。

  • 错误4：编码数组不够大
    示例中用vector<string> codes(256)假设字符是ASCII。如果字符集更大（比如中文），需要改用map或更大的数组。

7. 完整示例运行结果

用上面代码运行，会输出类似下面的编码表（具体取决于你提供的频率值）：

字符编码：
a: 1100
b: 1101
c: 100
d: 101
e: 111
f: 0

可以看到，频率最高的f（45次）只用了1位编码“0”；频率次高的c、d、e（12、13、16次）用了3位；而频率最低的a和b（5、9次）用了4位。这就是哈夫曼树的威力：整体总长度最短。

8. 动手试试

你完全可以修改例子中的freq数组，比如改成你班里考试分数的分布：90分以上频率高，60分以下频率低。看看编码会怎么变化。也可以增加字符数量，比如改成7个、8个，感受一下树变大的过程。

9. 学完之后，还能探索什么？

哈夫曼树是贪心算法的一个经典应用——每次选最优，最终得到全局最优。掌握它之后，你还可以去了解：

  • 优先队列：如何自己实现一个最小堆？它的插入和删除复杂度是O(log n)。
  • 二叉树遍历：前序、中序、后序遍历，以及如何不用递归生成编码。
  • 其他压缩算法：LZW、算术编码、Run-Length Encoding。
  • 文件压缩实践：尝试把哈夫曼编码用到真实文件上（比如文本文件），编写完整的压缩和解压程序。

现在，你已经学会了用一棵树来给信息“减肥”，是不是很有成就感？快打开电脑，亲手试一试吧！

例题精讲

1单选题

下面关于哈夫曼树的说法，正确的是？

A哈夫曼树一定是完全二叉树
B哈夫曼树中权值越大的叶子节点离根节点越近
C哈夫曼树中所有节点的度数要么为0，要么为2
D给定一组权值构造的哈夫曼树是唯一的
2单选题

假设有四个字符a、b、c、d，它们在文本中出现的频率分别为5、9、12、13。下列关于哈夫曼编码的说法，正确的是？

Aa的编码长度一定是3
B编码后的总长度为95
C每个字符的编码都是前缀码
Dd的编码一定比a的编码短
3判断题

在哈夫曼树中，若叶子节点的权值均不相等，则权值最大的叶子节点深度一定最小。

4判断题

给定一组权值，构造的哈夫曼树是唯一的。

5填空题
下面C++代码是哈夫曼树构建的部分实现，其中使用优先队列（最小堆）来维护节点权值。请补全代码，完成计算带权路径长度（WPL）的功能。假设节点结构体如下：

struct HuffNode {
    int weight;
    int parent, left, right;
};

以下函数接收权值数组 w 和节点个数 n，返回哈夫曼树的WPL。请补全代码中空白部分。

int huffmanWPL(int w[], int n) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < n; i++) {
        pq.push(w[i]);
    }
    int total = 0;
    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        int sum = a + b;
        total += ___;
        pq.push(sum);
    }
    return total;
}