构造一个哈夫曼树C++

哈夫曼树是一种带权路径长度最短的二叉树，通常用于数据压缩。构造哈夫曼树的过程可以分为以下几步：

1. 创建一个权值数组，用于存储每个字符在文本中出现的频率或权重。
2. 创建一个森林，森林中的每个树节点都是一个单独的字符，并以该字符出现的频率作为节点的权重。
3. 每次从森林中选出两个权值最小的节点作为左右子节点，将它们合并成一个新节点，并以这两个节点的权重之和作为新节点的权重。
4. 将新节点插入到森林中，并从森林中删除原来的两个节点。
5. 重复第3步和第4步，直到森林中只剩下一个根节点，即为哈夫曼树的根节点。

下面是一个基本的C++实现：

struct Node {
    char ch;          // 节点存储的字符
    int weight;       // 节点的权重
    Node *left, *right;  // 左右子节点
    Node(char c, int w): ch(c), weight(w), left(NULL), right(NULL) {}
};

// 构造哈夫曼树
Node* buildHuffmanTree(int weights[], int n) {
    // 定义一个优先队列用于存储所有节点
    priority_queue<Node*, vector<Node*>, [](const Node* a, const Node* b) { return a->weight > b->weight; }> pq;
    // 将每个字符作为单独的节点插入到队列中
    for (int i = 0; i < n; i++) {
        if (weights[i] > 0) {
            pq.push(new Node((char)i, weights[i]));
        }
    }
    // 逐步合并节点，构造哈夫曼树
    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();
        Node* parent = new Node('\0', left->weight + right->weight);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}