C++语言哈夫曼编码实现（从零开始掌握哈夫曼树与数据压缩）

一、什么是哈夫曼编码？

哈夫曼编码由David A. Huffman于1952年提出，是一种无损压缩方法。其核心思想是：根据字符在文本中出现的频率，构建一棵二叉树（即哈夫曼树），频率越高的字符离根节点越近，编码长度越短。

例如，在字符串 "aabbc" 中：

• 'a' 出现 2 次
• 'b' 出现 2 次
• 'c' 出现 1 次

通过哈夫曼编码，我们可以为 'a' 和 'b' 分配较短的编码（如 0 和 10），而为 'c' 分配较长的编码（如 11），从而减少整体编码长度。

二、实现步骤概述

使用 C++ 实现哈夫曼编码主要分为以下几个步骤：

1. 统计输入字符串中每个字符的频率
2. 构建最小堆（优先队列），用于每次取出频率最小的两个节点
3. 不断合并频率最小的两个节点，直到只剩一个根节点（即哈夫曼树）
4. 遍历哈夫曼树，生成每个字符对应的编码
5. 使用生成的编码对原始字符串进行编码

三、C++代码实现

下面是一个完整的 C++ 哈夫曼编码实现示例：

#include <iostream>#include <queue>#include <unordered_map>#include <vector>#include <string>using namespace std;// 哈夫曼树节点结构struct Node {    char ch;    int freq;    Node *left, *right;    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}};// 自定义比较函数，用于优先队列（最小堆）struct Compare {    bool operator()(Node* l, Node* r) {        return l->freq > r->freq;    }};// 递归生成哈夫曼编码void generateCodes(Node* root, string str, unordered_map<char, string>& codes) {    if (!root) return;    if (!root->left && !root->right) {        codes[root->ch] = str;    }    generateCodes(root->left, str + "0", codes);    generateCodes(root->right, str + "1", codes);}// 构建哈夫曼树并返回根节点Node* buildHuffmanTree(const string& text) {    // 统计字符频率    unordered_map<char, int> freq;    for (char c : text) {        freq[c]++;    }    // 创建最小堆    priority_queue<Node*, vector<Node*>, Compare> minHeap;    for (auto& pair : freq) {        minHeap.push(new Node(pair.first, pair.second));    }    // 构建哈夫曼树    while (minHeap.size() != 1) {        Node* left = minHeap.top(); minHeap.pop();        Node* right = minHeap.top(); minHeap.pop();        Node* newNode = new Node('\0', left->freq + right->freq);        newNode->left = left;        newNode->right = right;        minHeap.push(newNode);    }    return minHeap.top();}// 主函数int main() {    string text = "aabbc";    cout << "原始字符串: " << text << endl;    Node* root = buildHuffmanTree(text);    unordered_map<char, string> huffmanCode;    generateCodes(root, "", huffmanCode);    cout << "\n哈夫曼编码:\n";    for (auto& pair : huffmanCode) {        cout << pair.first << ": " << pair.second << endl;    }    // 编码原始字符串    string encoded = "";    for (char c : text) {        encoded += huffmanCode[c];    }    cout << "\n编码结果: " << encoded << endl;    return 0;}

四、代码解析

1. Node 结构体：表示哈夫曼树的节点，包含字符、频率和左右子节点指针。

2. Compare 结构体：用于定义优先队列的排序规则，确保频率小的节点优先出队。

3. generateCodes 函数：通过深度优先搜索（DFS）遍历哈夫曼树，为每个叶子节点（字符）生成唯一的二进制编码。

4. buildHuffmanTree 函数：先统计字符频率，然后利用优先队列反复合并最小频率节点，最终构建完整的哈夫曼树。

五、运行结果示例

以输入字符串 "aabbc" 为例，程序输出可能如下：

原始字符串: aabbc哈夫曼编码:a: 0b: 10c: 11编码结果: 00101011

可以看到，原本需要 5 字节（假设每个字符占 1 字节）存储的字符串，现在仅用 8 位（1 字节）即可表示，实现了有效的数据压缩。

六、总结

通过本教程，你已经学会了如何使用 C++语言实现哈夫曼编码。这项技术不仅在文件压缩（如ZIP、GZIP）中有广泛应用，也是理解哈夫曼树实现和C++数据压缩算法的重要基础。希望这篇哈夫曼编码教程能帮助你打下坚实的算法基础！

继续练习，尝试对不同字符串进行编码，观察压缩效果吧！