c++类实现哈夫曼树最小权值和

以下是使用C++类实现哈夫曼树最小权值和的示例代码：

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

class Node {
public:
    int weight;
    Node* left;
    Node* right;

    Node(int w) {
        weight = w;
        left = nullptr;
        right = nullptr;
    }

    ~Node() {
        delete left;
        delete right;
    }
};

class Compare {
public:
    bool operator()(Node* a, Node* b) {
        return a->weight > b->weight;
    }
};

int huffman(Node* root, int depth) {
    if (root->left == nullptr && root->right == nullptr) {
        return root->weight * depth;
    }
    int sum = 0;
    if (root->left != nullptr) {
        sum += huffman(root->left, depth + 1);
    }
    if (root->right != nullptr) {
        sum += huffman(root->right, depth + 1);
    }
    return sum;
}

int main() {
    int n;
    cin >> n;

    priority_queue<Node*, vector<Node*>, Compare> pq;
    for (int i = 0; i < n; i++) {
        int w;
        cin >> w;
        pq.push(new Node(w));
    }

    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);
    }

    Node* root = pq.top();
    int ans = huffman(root, 0);
    cout << ans << endl;

    delete root;
    return 0;
}

在这个示例中，我们定义了一个`Node`类来表示哈夫曼树的节点，其中包含权值、左子节点和右子节点。我们还定义了一个`Compare`类来实现节点的比较，用于构建哈夫曼树的优先队列。`huffman`函数用于计算哈夫曼树的最小权值和，它使用递归来遍历整棵树，计算每个叶子节点的权值和深度的乘积。

在`main`函数中，我们首先读入节点的数量和权值，然后使用优先队列来构建哈夫曼树。最后，我们计算哈夫曼树的最小权值和并输出结果。需要注意的是，在程序结束时，我们需要手动删除根节点来释放内存。