c++代码实现构建哈夫曼树

在C++中，我们可以使用`std::pair`和自定义的`Node`结构来实现哈夫曼树的构建。以下是一个基本的代码实现，使用了优先队列（`std::priority_queue`）：

#include <queue>
#include <vector>

using namespace std;

struct Node {
    char data;
    int frequency;
    Node* left = nullptr, *right = nullptr;
    
    bool operator<(const Node& other) const { return frequency < other.frequency; }
};

class HuffmanTree {
public:
    vector<Node*> buildHuffmanTree(vector<pair<char, int>>& freqChars) {
        priority_queue<Node*, vector<Node*>, greater<Node*>> pq(freqChars.begin(), freqChars.end());

        while (pq.size() > 1) {
            // 从堆中取出两个频率最低的节点
            Node* node1 = pq.top(); pq.pop();
            Node* node2 = pq.top(); pq.pop();

            // 合并两个节点
            Node* newNode = new Node();
            newNode->frequency = node1->frequency + node2->frequency;
            newNode->left = node1;
            newNode->right = node2;

            // 将新的节点放回堆中
            pq.push(newNode);
        }

        // 堆顶剩下的就是哈夫曼树的根节点
        return {pq.top()};
    }
};

int main() {
    vector<pair<char, int>> freqChars = {{'a', 5}, {'b', 7}, {'c', 3}};
    HuffmanTree huffman;
    auto root = huffman.buildHuffmanTree(freqChars);

    return 0;
}

在这个例子中，我们首先创建了一个节点结构`Node`，它包含了字符和其频率。然后通过`buildHuffmanTree`函数，我们按照频率递增的原则不断合并两个频率最低的节点，直到只剩下一个节点，这就是哈夫曼树的根节点。