C/C++ — 哈夫曼树与哈夫曼编码的实现

哈夫曼树是一种用于数据压缩的树形结构，可以通过构建哈夫曼树来得到哈夫曼编码。下面是用C++实现哈夫曼树和哈夫曼编码的示例代码：

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

// 哈夫曼树节点
struct HuffmanNode {
    char ch;                // 字符
    int freq;               // 出现频率
    HuffmanNode *left, *right;  // 左右子节点

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

// 用于比较哈夫曼树节点的函数对象
class HuffmanNodeCompare {
public:
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;   // 以出现频率为优先级
    }
};

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(string str) {
    unordered_map<char, int> freqMap;   // 统计各字符出现频率
    for (char c : str) {
        freqMap[c]++;
    }

    priority_queue<HuffmanNode*, vector<HuffmanNode*>, HuffmanNodeCompare> pq;
    // 将字符及其出现频率构建成哈夫曼树节点，并加入优先队列
    for (auto it = freqMap.begin(); it != freqMap.end(); it++) {
        HuffmanNode* node = new HuffmanNode(it->first, it->second);
        pq.push(node);
    }

    // 逐步合并哈夫曼树节点，直到只剩下一个节点，即根节点
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top();
        pq.pop();
        HuffmanNode* right = pq.top();
        pq.pop();
        HuffmanNode* parent = new HuffmanNode('$', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }

    return pq.top();
}

// 递归遍历哈夫曼树，得到字符的哈夫曼编码
void getHuffmanCode(HuffmanNode* node, string code, unordered_map<char, string>& codeMap) {
    if (!node) {
        return;
    }
    if (node->ch != '$') {
        codeMap[node->ch] = code;
    }
    getHuffmanCode(node->left, code + "0", codeMap);
    getHuffmanCode(node->right, code + "1", codeMap);
}

int main() {
    string str = "hello world";
    HuffmanNode* root = buildHuffmanTree(str);
    unordered_map<char, string> codeMap;
    getHuffmanCode(root, "", codeMap);
    cout << "Huffman codes:" << endl;
    for (auto it : codeMap) {
        cout << it.first << ": " << it.second << endl;
    }

    return 0;
}

代码中，先统计字符串中各字符的出现频率，然后将它们构建成哈夫曼树节点，并加入优先队列。接着，逐步合并哈夫曼树节点，直到只剩下一个节点，即根节点。最后，递归遍历哈夫曼树，得到各字符的哈夫曼编码。