哈夫曼树的构造代码

以下是基于C++的哈夫曼树构造代码：

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

// 定义哈夫曼树结点
struct HuffmanNode {
    int weight; // 权重
    HuffmanNode* left; // 左子树
    HuffmanNode* right; // 右子树
    HuffmanNode(int w = 0) : weight(w), left(NULL), right(NULL) {}
};

// 定义比较器
struct cmp {
    bool operator() (HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight;
    }
};

// 构造哈夫曼树
HuffmanNode* HuffmanTree(vector<int>& weights) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, cmp> pq;
    for (int i = 0; i < weights.size(); i++) {
        pq.push(new HuffmanNode(weights[i]));
    }
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top();
        pq.pop();
        HuffmanNode* right = pq.top();
        pq.pop();
        HuffmanNode* node = new HuffmanNode(left->weight + right->weight);
        node->left = left;
        node->right = right;
        pq.push(node);
    }
    return pq.top();
}

其中，优先队列 `pq` 存储哈夫曼树结点，比较器 `cmp` 按照权重从小到大排序，函数 `HuffmanTree` 输入权重数组 `weights`，返回构造好的哈夫曼树的根结点。