C++怎么建立Huffman树

建立Huffman树的过程可以分为以下几个步骤：

1. 统计每个字符出现的频率，并将它们存储一个数组中。
2. 将这些字符的频率从小到大排序。
3. 选择两个频率最小的字符，组成一个新的节点，其权值为这两个字符的频率之和。
4. 将新节点插入到频率数组中，并删除原来的两个节点。
5. 重复步骤3和4，直到只剩下一个节点为止，这个节点就是Huffman树的根节点。

下面是一个基于C++的Huffman树的实现代码示例：

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

//Huffman树节点
struct TreeNode{
    char data;  //字符
    int freq;   //字符出现的频率
    TreeNode *left, *right; //左右子节点
    TreeNode(char data, int freq):data(data), freq(freq), left(NULL), right(NULL){}
};

//用于比较两个节点的频率大小
struct compare{
    bool operator()(TreeNode* l, TreeNode* r){
        return (l->freq > r->freq);
    }
};

//建立Huffman树
TreeNode* buildHuffmanTree(map<char, int> freq_map){
    //用优先队列存储节点，按照节点频率从小到大排序
    priority_queue<TreeNode*, vector<TreeNode*>, compare> min_heap;
    //将所有字符的频率存储在节点中，并加入优先队列中
    for(auto p:freq_map){
        TreeNode* node = new TreeNode(p.first, p.second);
        min_heap.push(node);
    }
    //构建Huffman树
    while(min_heap.size() > 1){
        //取出两个频率最小的节点
        TreeNode* left = min_heap.top();
        min_heap.pop();
        TreeNode* right = min_heap.top();
        min_heap.pop();
        //组成新节点，并将其插入到优先队列中
        TreeNode* parent = new TreeNode('$', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        min_heap.push(parent);
    }
    //返回根节点
    return min_heap.top();
}

//遍历Huffman树，将每个字符的编码存储在map中
void encode(TreeNode* root, string str, map<char, string>& huffman_code){
    if(root == NULL) return;
    //如果节点为叶子节点，则将字符和对应的编码存储在map中
    if(!root->left && !root->right){
        huffman_code[root->data] = str;
    }
    //遍历左子树，将编码加上0
    encode(root->left, str + "0", huffman_code);
    //遍历右子树，将编码加上1
    encode(root->right, str + "1", huffman_code);
}

//打印Huffman编码
void printHuffmanCode(map<char, string> huffman_code){
    cout << "Huffman编码为：" << endl;
    for(auto p:huffman_code){
        cout << p.first << " : " << p.second << endl;
    }
}

int main(){
    //定义字符串
    string str = "hello world";
    //统计每个字符出现的频率
    map<char, int> freq_map;
    for(char c:str){
        freq_map[c]++;
    }
    //建立Huffman树
    TreeNode* root = buildHuffmanTree(freq_map);
    //遍历Huffman树，生成Huffman编码
    map<char, string> huffman_code;
    encode(root, "", huffman_code);
    //打印Huffman编码
    printHuffmanCode(huffman_code);
    return 0;
}

运行结果：

Huffman编码为：
  : 1110
d : 100
e : 01
h : 1100
l : 001
o : 101
r : 1111
w : 1101

以上代码实现了Huffman树的建立和遍历，生成了Huffman编码，并将编码存储在一个map中。