C++哈夫曼编码详解（从零开始掌握哈夫曼树算法与数据压缩实现）

实现步骤概览

1. 统计输入字符串中每个字符的出现频率
2. 根据频率构建最小堆（优先队列）
3. 不断合并频率最小的两个节点，构建哈夫曼树
4. 遍历哈夫曼树，生成每个字符对应的二进制编码
5. 使用编码表对原始数据进行压缩

C++ 实现哈夫曼编码

下面我们用 C++ 编写一个完整的哈夫曼编码程序。我们将使用标准库中的 priority_queue（优先队列）来高效地获取最小频率节点。

1. 定义哈夫曼树节点

#include <iostream>#include <queue>#include <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; // 小顶堆    }};

2. 构建哈夫曼树

// 构建哈夫曼树Node* buildHuffmanTree(const string& text) {    // 统计字符频率    map<char, int> freqMap;    for (char c : text) {        freqMap[c]++;    }    // 创建优先队列（最小堆）    priority_queue<Node*, vector<Node*>, Compare> pq;    // 将每个字符作为叶子节点加入堆    for (auto& pair : freqMap) {        pq.push(new Node(pair.first, pair.second));    }    // 合并节点直到只剩根节点    while (pq.size() != 1) {        Node* left = pq.top(); pq.pop();        Node* right = pq.top(); pq.pop();        // 创建新内部节点，频率为左右子节点之和        Node* newNode = new Node('\0', left->freq + right->freq);        newNode->left = left;        newNode->right = right;        pq.push(newNode);    }    return pq.top(); // 返回根节点}

3. 生成哈夫曼编码表

// 递归遍历哈夫曼树，生成编码void generateCodes(Node* root, string code, map<char, string>& codes) {    if (!root) return;    // 如果是叶子节点，保存编码    if (!root->left && !root->right) {        codes[root->ch] = code;    }    generateCodes(root->left, code + "0", codes);    generateCodes(root->right, code + "1", codes);}

4. 主函数：整合流程

int main() {    string text = "hello world";    cout << "原始文本: " << text << endl;    // 构建哈夫曼树    Node* root = buildHuffmanTree(text);    // 生成编码表    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;}

运行效果与说明

以字符串 "hello world" 为例，程序会输出每个字符对应的哈夫曼编码。例如：

' ': 00'd': 010'e': 011'h': 100'l': 11'o': 101'r': 0100'w': 0101

注意：实际编码可能因实现细节略有不同，但压缩原理一致。高频字符如 'l' 和 'o' 使用了较短的编码（2~3 位），而低频字符如 'r' 使用了更长的编码。

总结

通过本教程，你已经掌握了如何用 C++实现哈夫曼编码。这项技术是数据压缩领域的基石，理解它有助于深入学习文件压缩、网络传输优化等高级主题。记住，哈夫曼树算法的核心在于“频率决定编码长度”，这也是其高效的关键。

如果你正在学习C++哈夫曼编码或准备面试，建议动手敲一遍代码，加深理解。未来你还可以扩展此程序，支持文件读写、解码功能，甚至封装成压缩工具！

关键词回顾：C++哈夫曼编码、哈夫曼树算法、C++数据压缩、哈夫曼编码实现。