下面是重写后的代码：
#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 printTree(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);
printTree(root);
int wpl = calculateWPL(root, 0);
cout << "最优二元树的权： " << wpl << endl;
return 0;
}
这段代码实现了哈夫曼树的构建，打印树结构和计算最优二元树的权。
内容由零声教学AI助手提供，问题来源于学员提问
