C++哈夫曼树实现（手把手教你用C++构建哈夫曼编码树）

实现步骤概览

1. 统计字符频率
2. 构建最小堆（优先队列）
3. 不断合并频率最小的两个节点，直到只剩一棵树
4. 生成哈夫曼编码

C++代码实现

下面我们使用C++标准库中的 priority_queue 和 map 来高效实现哈夫曼树。

1. 定义哈夫曼树节点

struct Node {    char ch;    int freq;    Node* left;    Node* right;    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}};

2. 自定义比较函数（用于最小堆）

struct Compare {    bool operator()(const Node* l, const Node* r) const {        return l->freq > r->freq; // 小顶堆：频率小的优先级高    }};

3. 构建哈夫曼树

#include <iostream>#include <queue>#include <unordered_map>#include <string>using namespace std;Node* buildHuffmanTree(const string& text) {    // 统计字符频率    unordered_map<char, int> freqMap;    for (char c : text) {        freqMap[c]++;    }    // 创建最小堆    priority_queue<Node*, vector<Node*>, Compare> minHeap;    // 将每个字符作为叶子节点加入堆    for (auto& pair : freqMap) {        minHeap.push(new Node(pair.first, pair.second));    }    // 合并节点直到只剩一棵树    while (minHeap.size() != 1) {        Node* left = minHeap.top(); minHeap.pop();        Node* right = minHeap.top(); minHeap.pop();        int sum = left->freq + right->freq;        Node* newNode = new Node('\0', sum); // 内部节点无字符        newNode->left = left;        newNode->right = right;        minHeap.push(newNode);    }    return minHeap.top();}

4. 生成哈夫曼编码

void generateCodes(Node* root, string code, unordered_map<char, string>& huffmanCode) {    if (!root) return;    // 如果是叶子节点，保存编码    if (!root->left && !root->right) {        huffmanCode[root->ch] = code;    }    generateCodes(root->left, code + "0", huffmanCode);    generateCodes(root->right, code + "1", huffmanCode);}

5. 主函数测试

int main() {    string text = "hello world";    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;    }    // 注意：实际项目中应释放动态分配的内存    return 0;}

总结

通过以上步骤，我们成功用C++实现了哈夫曼树的构建与编码。这项技术是数据结构哈夫曼树的经典应用，也是理解哈夫曼编码C++教程的核心内容。掌握它不仅能提升你的算法能力，还能为后续学习压缩算法打下坚实基础。

记住：哈夫曼编码的关键在于“频率决定编码长度”。高频字符用短码，低频字符用长码，从而实现最优压缩效果。

希望这篇关于C++哈夫曼树实现的教程对你有帮助！动手敲一遍代码，你会理解得更深刻。