这是一个使用哈夫曼编码构建最优二叉树的示例代码，计算并输出最优二叉树的权值。以下是代码的改写结果：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct HuffmanNode {
int weight;
HuffmanNode* left, * right;
HuffmanNode(int leaf) : weight(leaf), left(nullptr), right(nullptr) {}
};
struct Compare {
bool operator()(HuffmanNode* l, HuffmanNode* r) {
return l->weight > r->weight;
}
};
HuffmanNode* buildHuffmanTree(vector<int>& tree) {
priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
for (int i = 0; i < tree.size(); i++) {
pq.push(new HuffmanNode(tree[i]));
}
while (pq.size() > 1) {
HuffmanNode* left = pq.top();
pq.pop();
HuffmanNode* right = pq.top();
pq.pop();
HuffmanNode* combined = new HuffmanNode(left->weight + right->weight);
combined->left = left;
combined->right = right;
pq.push(combined);
}
return pq.top();
}
void print_tree(HuffmanNode* root) {
queue<HuffmanNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
HuffmanNode* tmp = q.front();
cout << tmp->weight << " ";
q.pop();
if (tmp->left != nullptr) {
q.push(tmp->left);
}
if (tmp->right != nullptr) {
q.push(tmp->right);
}
}
cout << endl;
}
}
int calculateWPL(HuffmanNode* root, int depth) {
if (root == nullptr)
return 0;
if (root->left == nullptr && root->right == nullptr) {
return root->weight * depth;
}
return calculateWPL(root->left, depth + 1) + calculateWPL(root->right, depth + 1);
}
int main() {
vector<int> tree = {1, 3, 4, 5, 6};
HuffmanNode* root = buildHuffmanTree(tree);
print_tree(root);
int wpl = calculateWPL(root, 0);
cout << "最优二元树的权： " << wpl << endl;
// 计算并输出最终结果
return wpl;
}
修改后的代码会计算并返回最优二叉树的权值。你可以在主函数中通过调用return wpl;来仅输出最终结果。
内容由零声教学AI助手提供，问题来源于学员提问
