哈夫曼树的数据压缩c++代码

哈夫曼树是一种常用的数据压缩算法，它通过构建字符集的哈夫曼树来实现数据的压缩。下面是一个简单的C++代码实现：

#include <iostream>
#include <queue>
#include <map>
using namespace std;

// 定义哈夫曼树节点
struct TreeNode {
    char data; // 字符
    int freq; // 频率
    TreeNode* left;
    TreeNode* right;

    TreeNode(char data, int freq) {
        this->data = data;
        this->freq = freq;
        left = nullptr;
        right = nullptr;
    }

    // 比较函数，用于优先队列
    bool operator<(const TreeNode& other) const {
        return freq > other.freq;
    }
};

// 构建哈夫曼树
TreeNode* buildHuffmanTree(map<char, int>& freqMap) {
    // 构建优先队列，按频率从小到大排序
    priority_queue<TreeNode> pq;
    for (auto& p : freqMap) {
        pq.push(TreeNode(p.first, p.second));
    }

    // 不断取出两个频率最小的节点，合并为一个节点，直到只剩下一个节点
    while (pq.size() > 1) {
        TreeNode* left = new TreeNode(pq.top().data, pq.top().freq);
        pq.pop();
        TreeNode* right = new TreeNode(pq.top().data, pq.top().freq);
        pq.pop();
        int freq = left->freq + right->freq;
        TreeNode* parent = new TreeNode('\0', freq);
        parent->left = left;
        parent->right = right;
        pq.push(*parent);
    }
    return new TreeNode(pq.top().data, pq.top().freq); // 返回根节点
}

// 生成哈夫曼编码表
void generateHuffmanCode(TreeNode* root, string code, map<char, string>& codeMap) {
    if (root == nullptr) {
        return;
    }
    if (root->data != '\0') {
        codeMap[root->data] = code;
    }
    generateHuffmanCode(root->left, code + "0", codeMap);
    generateHuffmanCode(root->right, code + "1", codeMap);
}

// 将字符串压缩为哈夫曼编码后的字符串
string compress(string s, map<char, string>& codeMap) {
    string compressed = "";
    for (char c : s) {
        compressed += codeMap[c];
    }
    return compressed;
}

// 将哈夫曼编码后的字符串解压缩为原字符串
string decompress(string compressed, TreeNode* root) {
    string original = "";
    TreeNode* cur = root;
    for (char c : compressed) {
        if (c == '0') {
            cur = cur->left;
        } else if (c == '1') {
            cur = cur->right;
        }
        if (cur->left == nullptr && cur->right == nullptr) {
            original += cur->data;
            cur = root;
        }
    }
    return original;
}

int main() {
    string s = "hello world";
    
    // 统计字符频率
    map<char, int> freqMap;
    for (char c : s) {
        freqMap[c]++;
    }

    // 构建哈夫曼树
    TreeNode* root = buildHuffmanTree(freqMap);

    // 生成哈夫曼编码表
    map<char, string> codeMap;
    generateHuffmanCode(root, "", codeMap);

    // 压缩字符串
    string compressed = compress(s, codeMap);
    cout << "compressed: " << compressed << endl;

    // 解压缩字符串
    string original = decompress(compressed, root);
    cout << "original: " << original << endl;

    return 0;
}