给定的数组用C++编程哈夫曼树带权路径长度

以下是C++代码实现：

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

struct Node {
    int weight; // 权重
    Node *left; // 左子节点指针
    Node *right; // 右子节点指针

    Node(int weight) {
        this->weight = weight;
        left = nullptr;
        right = nullptr;
    }
};

// 定义小根堆，用于构建哈夫曼树
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));
    }
    while (pq.size() > 1) {
        Node *left = pq.top(); pq.pop();
        Node *right = pq.top(); pq.pop();
        Node *parent = new Node(left->weight + right->weight);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

// 计算带权路径长度
int calculateWPL(Node* root, int depth) {
    if (root == nullptr) {
        return 0;
    }
    if (root->left == nullptr && root->right == nullptr) {
        return depth * root->weight;
    }
    int leftWPL = calculateWPL(root->left, depth + 1);
    int rightWPL = calculateWPL(root->right, depth + 1);
    return leftWPL + rightWPL;
}

int main() {
    vector<int> weights = {3, 5, 6, 8, 2, 6};
    Node *root = buildHuffmanTree(weights);
    int wpl = calculateWPL(root, 0);
    cout << "带权路径长度为：" << wpl << endl;
    return 0;
}

输出结果：

带权路径长度为：94