前言

哈夫曼树（Huffman tree）是一棵带权二叉树，目标只有一个：让带权路径长度（weighted path length, WPL）最小。WPL 是每个叶子的权重乘上它到根的路径长度之和。把权重大的叶子放得浅、权重小的放得深，WPL 就小。这个性质直接对应压缩：高频字符用短码，低频字符用长码。

常见的误解有三个。第一，以为哈夫曼树唯一——当有权值相同的结点时，不同的合并顺序会得到不同的树，但 WPL 相同。第二，以为它是"平衡树"，其实它刻意不平衡，越常用的字符越靠近根。第三，把编码过程与建树过程混在一起：建树只依赖频率，编码只是对树做一次遍历。

本文按"概念 → 构造 → 编码解码 → 完整实现"讲，重点说清为什么每次合并最小的两个权重能得到最优解，以及实现时堆的比较器方向、单字符树、比特流校验这些边界。代码以 C++17 为基准。

一、带权路径长度

给定n个叶子，每个带权重w_i，深度为d_i（根为 0，或按边数计为 1，只要全树统一即可），则：

WPL = Σ w_i × d_i

在所有以这些叶子为叶子的二叉树中，WPL 最小的那棵就是哈夫曼树，也叫最优二叉树。

举例：权重为 1、2、3、4 的四个叶子。若做成一条链，深度分别是 0、1、2、3（假设），WPL 会很大；若尽量让大权重靠近根，WPL 会明显下降。哈夫曼算法给出的结构是：先合并 1 与 2 得到 3，再合并 3 与 3 得到 6，最后合并 6 与 4 得到 10。四个叶子的深度分别是 3、3、2、1，WPL = 1×3 + 2×3 + 3×2 + 4×1 = 19。

二、构造：贪心合并最小的两个

算法非常短：

1. 
   
2. 把每个叶子作为一个单结点树，放入一个按权重排序的集合；
3. 
   
4. 取出权重最小的两棵，合并成一棵新树，新树的权重是两者之和；
5. 
   
6. 把新树放回集合；
7. 
   
8. 重复直到只剩一棵树。
9. 
   

n 个叶子 → 需要 n-1 次合并 → 总共 2n-1 个结点

为什么这样能得到最优解？核心是一个交换论证：在任意一棵最优树中，权重最小的两个叶子一定可以放在最深的一层，并且互为兄弟。如果它们不在最深处，把最深处的叶子与它们交换，WPL 不会增大（因为小权重下沉、大权重上浮只会让总和更小）；如果它们不是兄弟，把它们调整为兄弟也不会增大 WPL。于是"合并最小的两个"这一步是安全的，剩下的问题规模减一，归纳即得最优。

这个论证也解释了贪心成立的条件：每一步都必须合并当前最小的两个，而不是原始权重最小的两个。合并产生的新权重会参与后续比较。

三、编码与解码：前缀码

把树的左分支记为 0、右分支记为 1，从根到叶子的路径就是一个二进制串。由于每个字符都在叶子上，任何一个编码都不是另一个编码的前缀——这就是前缀码（prefix code），解码时不需要分隔符，从左到右走树即可。

构造过程是：合并 9 与 12 得 21，合并 13 与 16 得 29，合并 21 与 29 得 50，最后合并 45 与 50 得 95。左右分支可以互换，所以具体编码不是唯一的，但每个编码都满足前缀性质：没有任何一个编码是另一个编码的前缀，解码时不需要分隔符。

四、完整实现

用std::priority_queue维护最小堆。默认的priority_queue是最大堆，所以要自定义比较器，让"权重小"的排在堆顶。

// 适用于 C++17
#include <map>
#include <memory>
#include <queue>
#include <string>
#include <utility>
#include <vector>

struct Node {
int weight = 0;
char ch = '\0'; // 内部结点没有字符
Node* left = nullptr;
Node* right = nullptr;
Node(int w, char c) : weight(w), ch(c) {}
};

struct MinCompare {
bool operator()(const Node* a, const Node* b) const {
return a->weight > b->weight; // 注意方向：大于号构成最小堆
}
};

class Huffman {
public:
explicit Huffman(const std::vector<std::pair<char, int>>& freqs) {
std::priority_queue<Node*, std::vector<Node*>, MinCompare> pq;
for (const auto& item : freqs) {
if (item.second <= 0) continue; // 忽略非正频率
nodes_.push_back(std::make_unique<Node>(item.second, item.first));
pq.push(nodes_.back().get());
}
if (pq.empty()) return;

while (pq.size() > 1) {
Node* a = pq.top(); pq.pop();
Node* b = pq.top(); pq.pop();
nodes_.push_back(std::make_unique<Node>(a->weight + b->weight, '\0'));
Node* parent = nodes_.back().get();
parent->left = a;
parent->right = b;
pq.push(parent);
}
root_ = pq.top();
}

void build_codes() {
codes_.clear();
build_codes(root_, std::string());
if (root_ != nullptr && root_->left == nullptr && root_->right == nullptr) {
codes_[root_->ch] = "0"; // 单字符树：给一个占位编码
}
}

const std::map<char, std::string>& codes() const { return codes_; }

std::string encode(const std::string& text) const {
std::string bits;
for (char c : text) {
auto it = codes_.find(c);
if (it == codes_.end()) return std::string(); // 未知字符
bits += it->second;
}
return bits;
}

std::string decode(const std::string& bits) const {
if (root_ == nullptr) return std::string();
if (root_->left == nullptr && root_->right == nullptr) {
return std::string(bits.size(), root_->ch); // 单字符树
}
std::string text;
const Node* cur = root_;
for (char b : bits) {
if (b == '0') cur = cur->left;
else if (b == '1') cur = cur->right;
else return std::string();
if (cur == nullptr) return std::string();
if (cur->left == nullptr && cur->right == nullptr) {
text.push_back(cur->ch);
cur = root_; // 回到根，解下一个字符
}
}
if (cur != root_) return std::string(); // 比特流不完整
return text;
}

int wpl() const { return wpl(root_, 0); }

private:
static void build_codes(const Node* n, const std::string& prefix,
std::map<char, std::string>& out);
static int wpl(const Node* n, int depth);

std::vector<std::unique_ptr<Node>> nodes_; // 统一持有所有结点
Node* root_ = nullptr;
std::map<char, std::string> codes_;
};

两个静态辅助函数的实现：

// 适用于 C++17
void Huffman::build_codes(const Node* n, const std::string& prefix,
std::map<char, std::string>& out) {
if (n == nullptr) return;
if (n->left == nullptr && n->right == nullptr) {
out[n->ch] = prefix;
return;
}
build_codes(n->left, prefix + '0', out);
build_codes(n->right, prefix + '1', out);
}

int Huffman::wpl(const Node* n, int depth) {
if (n == nullptr) return 0;
if (n->left == nullptr && n->right == nullptr) {
return n->weight * depth;
}
return wpl(n->left, depth + 1) + wpl(n->right, depth + 1);
}

用std::vector<std::unique_ptr<Node>>统一持有所有结点，结点之间的left/right用裸指针表示非拥有关系。这样既不会泄漏，也不需要在树结构里处理所有权转移。

五、复杂度与边界

建树时每个叶子入堆一次、每次合并产生一个新结点入堆，共2n-1个结点，每次堆操作 O(log n)，总时间 O(n log n)。编码遍历 O(n)，解码 O(比特数)。

边界情况：

• 
  
• 只有一个不同字符：树只有一个结点，没有左/右分支，常规遍历会给它一个空编码。上面用"0"占位，解码时按位数还原。这是压缩实现里必须特判的情况。
• 
  
• 频率为 0 或负数：没有意义，应当过滤或拒绝。全部被过滤时root_为空，编码解码返回空串。
• 
  
• 比特流不完整：最后一个字符的编码被截断，cur不会回到根，解码应当报错而不是返回半截结果。
• 
  
• 树的形状不唯一：权重相同的结点谁左谁右都可以，只要双方约定一致即可；编码表必须与树一起传递，不能只传比特流。
• 
  

常见坑点

1. 比较器方向写反，得到最大堆

// ❌ 每次取出最大的两个，WPL 不是最优
return a->weight < b->weight;
// ✅ 最小堆：堆顶是最小值
return a->weight > b->weight;

2. 合并后忘记把新结点入堆

// ❌ 集合元素越来越少，结果错误
Node* parent = make(a, b);
// ✅ 新结点也要参与后续比较
pq.push(parent);

3. 单字符树没有编码

// ❌ 编码为空串，无法还原
if (leaf) out[ch] = prefix; // prefix 为空
// ✅ 特判并给一个占位码
codes_[root_->ch] = "0";

4. 解码不校验比特流完整性

// ❌ 截断的输入被当成合法数据
for (char b : bits) { ... }
return text;
// ✅ 结束后确认已回到根
if (cur != root_) return std::string();

5. 用裸new建结点却没有统一释放

// ❌ 异常路径上泄漏
Node* n = new Node(w, c);
// ✅ 用 unique_ptr 容器统一持有
nodes_.push_back(std::make_unique<Node>(w, c));

6. 把原始频率当成合并后的权重

// ❌ 新结点权重算错，贪心失效
parent->weight = a->weight; // 漏了 b
// ✅ 权重是两者之和
parent->weight = a->weight + b->weight;

7. 假设哈夫曼树唯一

// ❌ 用树的形状做校验
// ✅ 只校验 WPL 与编解码的可逆性

8. 编码表与比特流分开传输却未同步

// ❌ 解码方用旧表解新流
// ✅ 编码表随数据一起传输，或固定版本

总结

哈夫曼树的核心只有一句：让权重大的叶子离根近。构造算法用最小堆把这个直觉变成可执行步骤，编码只是对结果做一次遍历。实现时真正要小心的是堆的比较方向、单字符树、比特流完整性这三处边界；把这三个处理掉，剩下的就是标准的二叉树遍历。