c++用树实现哈夫曼编码的代码

C++中使用树实现哈夫曼编码的代码如下所示：

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

// 定义哈夫曼树节点
struct HuffmanNode {
    char data; // 字符
    int freq; // 频率
    HuffmanNode* left;
    HuffmanNode* right;
    HuffmanNode(char d, int f) : data(d), freq(f), left(nullptr), right(nullptr) {}
};

// 定义比较函数，用于优先队列的排序
struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(map<char, int>& freqMap) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> 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* newNode = new HuffmanNode('$', left->freq + right->freq);
        newNode->left = left;
        newNode->right = right;
        
        pq.push(newNode);
    }
    
    return pq.top();
}

// 生成哈夫曼编码表
void generateHuffmanCodes(HuffmanNode* root, string code, map<char, string>& huffmanCodes) {
    if (root == nullptr) {
        return;
    }
    
    // 叶子节点表示一个字符，将字符和对应的哈夫曼编码加入编码表
    if (root->left == nullptr && root->right == nullptr) {
        huffmanCodes[root->data] = code;
    }
    
    // 递归生成左子树和右子树的哈夫曼编码
    generateHuffmanCodes(root->left, code + "0", huffmanCodes);
    generateHuffmanCodes(root->right, code + "1", huffmanCodes);
}

// 哈夫曼编码
string encode(string text, map<char, string>& huffmanCodes) {
    string encodedText = "";
    
    // 将原始文本中的每个字符替换为对应的哈夫曼编码
    for (char c : text) {
        encodedText += huffmanCodes[c];
    }
    
    return encodedText;
}

// 哈夫曼解码
string decode(string encodedText, HuffmanNode* root) {
    string decodedText = "";
    HuffmanNode* curr = root;
    
    // 遍历编码后的文本，根据0和1进行解码
    for (char bit : encodedText) {
        if (bit == '0') {
            curr = curr->left;
        } else {
            curr = curr->right;
        }
        
        // 到达叶子节点，表示找到了一个字符，将其加入解码后的文本
        if (curr->left == nullptr && curr->right == nullptr) {
            decodedText += curr->data;
            curr = root;
        }
    }
    
    return decodedText;
}

int main() {
    string text = "Hello, World!";
    
    // 统计字符频率
    map<char, int> freqMap;
    for (char c : text) {
        freqMap[c]++;
    }
    
    // 构建哈夫曼树
    HuffmanNode* root = buildHuffmanTree(freqMap);
    
    // 生成哈夫曼编码表
    map<char, string> huffmanCodes;
    generateHuffmanCodes(root, "", huffmanCodes);
    
    // 打印字符和对应的哈夫曼编码
    cout << "Huffman Codes:" << endl;
    for (auto it = huffmanCodes.begin(); it != huffmanCodes.end(); ++it) {
        cout << it->first << ": " << it->second << endl;
    }
    
    // 哈夫曼编码
    string encodedText = encode(text, huffmanCodes);
    cout << "Encoded Text: " << encodedText << endl;
    
    // 哈夫曼解码
    string decodedText = decode(encodedText, root);
    cout << "Decoded Text: " << decodedText << endl;
    
    return 0;
}