Huffman树的编码与构建的c++代码实现以及思路

Huffman树，也称为最优二叉树或霍夫曼树，是一种用于数据压缩的自适应哈夫曼编码构造方法。它的构建过程主要是基于贪心策略，通过合并频率最低的两个字符形成新的节点，并将其加入到树中，直至所有字符都被包含。

**构建思路**：
1. 计算每个字符的频率。
2. 创建一个优先队列，初始时将所有的字符及其频率作为键值对插入。
3. 取出队列中频率最低的两个节点，创建一个新的节点，新节点的频率是这两个节点频率之和，然后将新节点放回队列。
4. 重复步骤3，直到队列只剩下一个节点，这个节点就是Huffman树的根。

**C++代码实现**：

#include <queue>
#include <unordered_map>

struct Node {
    char data;
    int freq;
    Node* left, *right;
};

Node* buildHuffmanTree(std::unordered_map<char, int>& freqMap) {
    std::priority_queue<std::pair<int, Node*>, std::vector<std::pair<int, Node*>>, std::greater<std::pair<int, Node*>>> pq(freqMap.begin(), freqMap.end());

    while (pq.size() > 1) {
        int freq1 = pq.top().first;
        int freq2 = pq.top().second->freq;
        pq.pop();

        int freqSum = freq1 + freq2;
        pq.push({freqSum, new Node{'.', freqSum, nullptr, nullptr}});

        pq.push({freq1, freqMap.begin()->second});
        pq.pop();
        
        pq.push({freq2, pq.top().second});
        pq.pop();

        freqMap.erase(freqMap.begin());
    }
    
    return pq.top().second;
}

// 示例使用
std::unordered_map<char, int> freq = {{'a', 5}, {'b', 9}, {'c', 3}};
Node* root = buildHuffmanTree(freq);

--