用c++语言构造一个哈夫曼树

以下是用C++语言实现构造哈夫曼树的示例代码：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
    Node(int v, Node* l, Node* r) : val(v), left(l), right(r) {}
};

struct Compare {
    bool operator() (Node* a, Node* b) {
        return a->val > b->val;
    }
};

Node* constructHuffmanTree(vector<int>& weights) {
    priority_queue<Node*, vector<Node*>, Compare> pq;
    for (int w : weights) {
        pq.push(new Node(w));
    }
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();
        int sum = left->val + right->val;
        pq.push(new Node(sum, left, right));
    }
    return pq.top();
}

void printHuffmanTree(Node* root, string prefix = "") {
    if (root == nullptr) {
        return;
    }
    if (root->left == nullptr && root->right == nullptr) {
        cout << prefix << " " << root->val << endl;
    }
    printHuffmanTree(root->left, prefix + "0");
    printHuffmanTree(root->right, prefix + "1");
}

int main() {
    vector<int> weights = {5, 9, 12, 13, 16, 45};
    Node* root = constructHuffmanTree(weights);
    printHuffmanTree(root);

    return 0;
}

在这个示例程序中，我们使用了一个优先队列来保存每个权值对应的节点，每次从队列中取出权值最小的两个节点，构造新的父节点，并将其加入队列中。最后队列中只剩下一个节点，即为哈夫曼树的根节点。我们还实现了一个函数 `printHuffmanTree`，用于打印哈夫曼树的编码。