哈夫曼编码是一种变长前缀编码方法，常用于无损数据压缩，例如ZIP、JPEG等格式中都能看到它的身影。实现一个哈夫曼编码生成器并不复杂，核心步骤分为三部分：统计字符频率、构建哈夫曼树、从树中提取每个字符的编码。本文将以C++为例，完整展示从二叉树构建到编码映射表生成的源码，并讨论实现中容易踩坑的细节。
一、统计字符频率与设计节点结构
任何哈夫曼编码实现的第一步都是获取字符频率。对于输入文本，遍历每个字符并用哈希表记录出现次数，复杂度为O(n)。在C++中可以使用unordered_map<char,int>来存储字符到频率的映射。之所以选择char作为键，是因为ASCII字符集最多256种，若需要支持宽字符可以改为wchar_t或自定义类型。
定义哈夫曼树的节点。节点需要保存字符、频率、左右子树指针，并提供两个构造函数：一个用于叶子节点，一个用于内部合并节点。内部节点不含具体字符，常用空字符\0标识。为了让节点能被优先队列管理，还需要自定义比较器，因为priority_queue默认是大顶堆，而建树需要每次取出频率最小的两个节点，必须将比较逻辑反过来。
struct Node {
char ch;
int freq;
Node* left;
Node* right;
Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
Node(int f, Node* l, Node* r) : ch('\0'), freq(f), left(l), right(r) {}
};
struct Compare {
bool operator()(Node* a, Node* b) {
return a->freq > b->freq;
}
};
二、最小堆构建哈夫曼树
建树过程可以被理解为反复合并两个权值最小的子树。先把所有叶子节点压入最小堆，每次弹出两个频率最小的节点，创建一个新的内部节点，其频率等于两个子节点频率之和，左右指针分别指向这两个节点，再把新节点压回堆中。重复此操作直到堆中只剩一个节点，这唯一的节点就是哈夫曼树的根。整个过程需要执行n-1次合并，每次弹出和压入堆的复杂度为O(log n)，总体复杂度为O(n log n)。
边界条件需要单独处理。如果输入为空，直接返回空指针；如果只有一种字符，无法进行两次弹出，可以创建一个虚拟根节点，将唯一节点作为左子树，这样该字符的编码就是单个0。另外，当多个字符频率相同时，最小堆的弹出顺序可能受容器实现影响，但最终生成的编码仍是最优前缀码，只是个别字符的编码可能不同。
Node* buildHuffmanTree(const unordered_map<char,int>& freqMap) {
priority_queue<Node*, vector<Node*>, Compare> pq;
for (auto& pair : freqMap) {
pq.push(new Node(pair.first, pair.second));
}
if (pq.empty()) return nullptr;
if (pq.size() == 1) {
Node* single = new Node('\0', 0);
single->left = pq.top();
pq.pop();
return single;
}
while (pq.size() > 1) {
Node* left = pq.top(); pq.pop();
Node* right = pq.top(); pq.pop();
Node* parent = new Node(left->freq + right->freq, left, right);
pq.push(parent);
}
return pq.top();
}
三、深度优先遍历生成编码映射表
得到哈夫曼树后，从根节点开始做深度优先遍历，维护当前路径的二进制串。向左走追加0，向右走追加1，当到达叶子节点时，把该字符和对应的路径字符串存入映射表。由于哈夫曼树是二叉前缀树，这样生成的编码天然满足前缀码性质：任何一个字符的编码都不是另一个字符编码的前缀，解码时不会产生歧义。
实现上可以选择递归或显式栈。递归写法更简洁，但若树深度过大可能导致栈溢出，实际应用中字符集有限，树深度最多为字符种类数减1，通常很安全。编码映射表使用unordered_map<char,string>存储，键为字符，值为编码字符串。对于非叶子内部节点，它们没有属于自身的字符编码，只作为路径中转。
void generateCodes(Node* root, const string& prefix, unordered_map<char,string>& codeMap) {
if (!root) return;
if (!root->left && !root->right) {
if (root->ch != '\0') {
codeMap[root->ch] = prefix;
}
return;
}
generateCodes(root->left, prefix + "0", codeMap);
generateCodes(root->right, prefix + "1", codeMap);
}
四、编码与解码的完整实现
有了映射表，编码就是将原字符串每个字符替换为对应编码串。解码则需要从根节点开始按位读取编码串，遇到0向左走，遇到1向右走，走到叶子节点时输出该字符并回到根节点继续处理。解码不依赖映射表，只需要树结构，因此编码表和树可以分别存储或传输。若编码串损坏或有非法位，解码会偏离路径，实际应用中通常会加入校验机制。
下面给出完整的C++源代码，将上述步骤整合到main函数中进行测试。测试字符串选择abracadabra，该字符串中a出现5次、b出现2次、r出现2次、c出现1次、d出现1次，频率分布非均匀，能体现哈夫曼编码的压缩效果。运行后会输出字符编码映射表、原始字符串、编码结果和解码结果，便于验证正确性。
#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;
struct Node {
char ch;
int freq;
Node* left;
Node* right;
Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
Node(int f, Node* l, Node* r) : ch('\0'), freq(f), left(l), right(r) {}
};
struct Compare {
bool operator()(Node* a, Node* b) {
return a->freq > b->freq;
}
};
Node* buildHuffmanTree(const unordered_map<char,int>& freqMap) {
priority_queue<Node*, vector<Node*>, Compare> pq;
for (auto& pair : freqMap) {
pq.push(new Node(pair.first, pair.second));
}
if (pq.empty()) return nullptr;
if (pq.size() == 1) {
Node* single = new Node('\0', 0);
single->left = pq.top();
pq.pop();
return single;
}
while (pq.size() > 1) {
Node* left = pq.top(); pq.pop();
Node* right = pq.top(); pq.pop();
Node* parent = new Node(left->freq + right->freq, left, right);
pq.push(parent);
}
return pq.top();
}
void generateCodes(Node* root, const string& prefix, unordered_map<char,string>& codeMap) {
if (!root) return;
if (!root->left && !root->right) {
if (root->ch != '\0') {
codeMap[root->ch] = prefix;
}
return;
}
generateCodes(root->left, prefix + "0", codeMap);
generateCodes(root->right, prefix + "1", codeMap);
}
string encode(const string& text, const unordered_map<char,string>& codeMap) {
string encoded;
for (char c : text) {
encoded += codeMap.at(c);
}
return encoded;
}
string decode(const string& encoded, Node* root) {
string decoded;
Node* current = root;
for (char bit : encoded) {
if (bit == '0') current = current->left;
else current = current->right;
if (!current->left && !current->right) {
decoded += current->ch;
current = root;
}
}
return decoded;
}
int main() {
string text = "abracadabra";
unordered_map<char,int> freqMap;
for (char c : text) freqMap[c]++;
Node* root = buildHuffmanTree(freqMap);
unordered_map<char,string> codeMap;
generateCodes(root, "", codeMap);
cout << "字符编码映射表：" << endl;
for (auto& kv : codeMap) {
cout << kv.first << " : " << kv.second << endl;
}
string encoded = encode(text, codeMap);
cout << "原始字符串：" << text << endl;
cout << "编码结果：" << encoded << endl;
string decoded = decode(encoded, root);
cout << "解码结果：" << decoded << endl;
return 0;
}
整体时间复杂度主要来自建堆和维护最小堆，为O(n log n)，空间复杂度为O(n)，用于存储节点和映射表。如果字符集很小且固定，可以使用数组代替unordered_map获得更快的查找速度。另外，在解码时若树结构较大，可以考虑将树转为状态表来降低指针跳转开销，但通常没有必要性。代码已处理单字符、空输入等边界情况，可直接用于学习或小规模压缩工具。