求哈夫曼树WPl的代码

以下是求哈夫曼树的C++代码：

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

struct Node {
    int weight;
    Node* left;
    Node* right;
};

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

Node* BuildHuffmanTree(vector<int>& weights) {
    priority_queue<Node*, vector<Node*>, cmp> pq;
    for (int weight : weights) {
        pq.push(new Node{ weight, nullptr, nullptr });
    }
    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();
        pq.push(new Node{ left->weight + right->weight, left, right });
    }
    return pq.top();
}

void PrintWPL(Node* root, int depth, int& wpl) {
    if (!root->left && !root->right) {
        wpl += root->weight * depth;
        return;
    }
    if (root->left) {
        PrintWPL(root->left, depth + 1, wpl);
    }
    if (root->right) {
        PrintWPL(root->right, depth + 1, wpl);
    }
}

int main() {
    vector<int> weights{ 1, 2, 2, 3, 3, 4 };
    Node* root = BuildHuffmanTree(weights);
    int wpl = 0;
    PrintWPL(root, 0, wpl);
    cout << wpl << endl; // 输出 18
    return 0;
}

代码中，首先定义了一个 `Node` 结构体，表示哈夫曼树的节点。其中，`weight` 表示节点的权重，`left` 和 `right` 分别表示该节点的左右子节点。然后，定义一个比较类 `cmp`，用于指定优先队列的比较方式，这里使用小根堆，按照节点的权重从小到大排序。

`BuildHuffmanTree` 函数接收一个整数向量 `weights`，表示每个节点的权重。首先，将每个节点都加入优先队列中。接着，每次从队列中取出两个权重最小的节点，合并成一个新节点，权重为两个节点的权重之和，并将新节点加入队列中。最终，队列中只剩下一个节点，即为哈夫曼树的根节点。

`PrintWPL` 函数用于计算哈夫曼树的带权路径长度（WPL）。`depth` 表示当前节点的深度，`wpl` 表示累计的带权路径长度。如果当前节点是叶子节点，则将该节点的权重乘以深度加入 `wpl` 中。否则，递归处理左右子节点。

最后，在 `main` 函数中调用 `BuildHuffmanTree` 函数构建哈夫曼树，然后调用 `PrintWPL` 函数计算 WPL，并输出结果。