c++构造哈夫曼树并实现哈夫曼编码

好的，我可以帮你解答这个问题。

首先，哈夫曼树是一种用于编码的树形结构，它可以根据字符出现的频率构建一种最优的编码方式，使得编码后的数据长度最短。

构建哈夫曼树的基本步骤如下：

1. 统计每个字符出现的频率，并将它们按照频率从小到大排序。
2. 取出当前频率最小的两个字符，将它们组成一个新的节点，且该节点的权值为两个字符的频率之和。
3. 将新节点插入到频率表中，并删除原来的两个字符，然后重新排序。
4. 重复步骤2和3，直到只剩下一个节点，这个节点就是哈夫曼树的根节点。

构建好哈夫曼树后，就可以对每个字符进行编码了。编码的规则是，对于哈夫曼树中的每个叶子节点，从根节点到该节点的路径上的左右分支分别用0和1表示，这就是该字符的哈夫曼编码。

这里是一个 C++ 实现的示例代码：

#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>

using namespace std;

// 定义哈夫曼树的节点结构体
struct HuffmanNode {
    char ch; // 字符
    int freq; // 频率
    HuffmanNode* left; // 左子节点
    HuffmanNode* right; // 右子节点
    HuffmanNode(char c, int f): ch(c), freq(f), left(nullptr), right(nullptr) {}
};

// 定义比较哈夫曼节点的函数对象
struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq; // 按照频率从小到大排序
    }
};

// 统计字符频率
unordered_map<char, int> countFreq(string str) {
    unordered_map<char, int> freq;
    for(char c: str) {
        freq[c]++;
    }
    return freq;
}

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(unordered_map<char, int> freq) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    // 将每个字符作为一个单独的节点加入优先队列
    for(auto p: freq) {
        pq.push(new HuffmanNode(p.first, p.second));
    }
    // 不断取出频率最小的两个节点，合并成一个新节点，并加入队列中
    while(pq.size() > 1) {
        HuffmanNode* left = pq.top(); pq.pop();
        HuffmanNode* right = pq.top(); pq.pop();
        HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    // 最后队列中只剩下一个节点，它就是哈夫曼树的根节点
    return pq.top();
}

// 递归遍历哈夫曼树，生成每个字符的编码
void generateHuffmanCode(HuffmanNode* root, string code, unordered_map<char, string>& huffmanCode) {
    if(!root) return;
    // 如果是叶子节点，就记录下该字符的哈夫曼编码
    if(!root->left && !root->right) {
        huffmanCode[root->ch] = code;
        return;
    }
    // 分别遍历左右子树，并在编码后面加上0或1
    generateHuffmanCode(root->left, code + "0", huffmanCode);
    generateHuffmanCode(root->right, code + "1", huffmanCode);
}

// 对给定字符串进行哈夫曼编码
string huffmanEncode(string str) {
    unordered_map<char, int> freq = countFreq(str);
    HuffmanNode* root = buildHuffmanTree(freq);
    unordered_map<char, string> huffmanCode;
    generateHuffmanCode(root, "", huffmanCode);
    string encodedStr;
    for(char c: str) {
        encodedStr += huffmanCode[c];
    }
    return encodedStr;
}

// 解码给定的哈夫曼编码
string huffmanDecode(string encodedStr, HuffmanNode* root) {
    string decodedStr;
    HuffmanNode* cur = root;
    for(char c: encodedStr) {
        if(c == '0') {
            cur = cur->left;
        } else {
            cur = cur->right;
        }
        if(!cur->left && !cur->right) {
            decodedStr += cur->ch;
            cur = root;
        }
    }
    return decodedStr;
}

int main() {
    string str = "hello world";
    string encodedStr = huffmanEncode(str);
    cout << "Encoded string: " << encodedStr << endl;
    HuffmanNode* root = buildHuffmanTree(countFreq(str));
    string decodedStr = huffmanDecode(encodedStr, root);
    cout << "Decoded string: " << decodedStr << endl;
    return 0;
}

上述代码中，我们首先定义了一个哈夫曼树节点的结构体 `HuffmanNode`，其中包含字符、频率、左右子节点等信息。然后，我们通过 `countFreq` 函数统计每个字符出现的频率，并通过 `buildHuffmanTree` 函数构建哈夫曼树。在构建哈夫曼树的过程中，我们使用了一个优先队列来存储每个字符的节点，并按照频率从小到大排序。

构建好哈夫曼树后，我们通过递归遍历树的方式生成每个字符的哈夫曼编码，并记录在一个哈希表中。最后，我们使用 `huffmanEncode` 函数对给定字符串进行编码，使用 `huffmanDecode` 函数对编码后的字符串进行解码，恢复原来的字符串。