#include<iostream>
#include<queue>
#include<vector>
using namespace std ;
struct Node{
Node *left, *right ;
int value ;
Node(int val){
value = val ;
left = NULL ;
right = NULL ;
}
bool operator <(const Node &v2) const{
return value > v2.value ;
}
} ;
void caculateHeight(Node root,int h,int &sum){
if (root.left == NULL && root.right == NULL){
sum += root.value * h ;
return ;
}
caculateHeight(*root.left, h+1,sum) ;
caculateHeight(*root.right, h+1,sum) ;
}
int main(){
int size ;
while (cin >> size){
priority_queue<Node> queue ;
while (size--){
int val ;
cin >> val ;
queue.push(Node(val)) ;
}
while (queue.size() != 1){
Node top1 = queue.top() ;
queue.pop() ;
Node top2 = queue.top() ;
queue.pop() ;
Node *newNode = new Node(top1.value + top2.value);
newNode -> right = &top2 ;
newNode -> left = &top1 ;
queue.push(*newNode) ;
}
int sum ;
caculateHeight(queue.top(),1,sum) ;
cout << sum << endl ;
}
return 0 ;
}
如下构建哈夫曼树并求总权值的方法哪里有错误?为什么我得到的树是错误的?
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答 默认 最新
- IT_service_mesh 2023-03-26 21:54关注
参考GPT和自己的思路:在构建哈夫曼树时,新节点应该是指针类型而不是对象类型,因为在对原有的节点进行操作时,可能会出现指向已经弹出队列的对象,从而导致结果错误的情况。因此,在构建新节点时应该使用指针类型,如下所示:
... while (queue.size() != 1){ Node* top1 = new Node(queue.top().value); queue.pop(); Node* top2 = new Node(queue.top().value); queue.pop(); Node *newNode = new Node(top1->value + top2->value); newNode -> right = top2 ; newNode -> left = top1 ; queue.push(*newNode) ; } ...
另外,在调用 caculateHeight 函数时,应该使用指向根节点的指针而不是对象本身,并且必须将 sum 初始值赋为0。更正后的代码如下所示:
int main(){ int size ; while (cin >> size){ priority_queue<Node> queue ; while (size--){ int val ; cin >> val ; queue.push(Node(val)) ; } while (queue.size() != 1){ Node* top1 = new Node(queue.top().value); queue.pop(); Node* top2 = new Node(queue.top().value); queue.pop(); Node *newNode = new Node(top1->value + top2->value); newNode -> right = top2 ; newNode -> left = top1 ; queue.push(*newNode) ; } int sum = 0 ; caculateHeight(*queue.top(),1,sum) ; cout << sum << endl ; } return 0 ; }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 1无用
悬赏问题
- ¥15 装 pytorch 的时候出了好多问题,遇到这种情况怎么处理?
- ¥20 IOS游览器某宝手机网页版自动立即购买JavaScript脚本
- ¥15 手机接入宽带网线,如何释放宽带全部速度
- ¥30 关于#r语言#的问题:如何对R语言中mfgarch包中构建的garch-midas模型进行样本内长期波动率预测和样本外长期波动率预测
- ¥15 ETLCloud 处理json多层级问题
- ¥15 matlab中使用gurobi时报错
- ¥15 这个主板怎么能扩出一两个sata口
- ¥15 不是,这到底错哪儿了😭
- ¥15 2020长安杯与连接网探
- ¥15 关于#matlab#的问题:在模糊控制器中选出线路信息,在simulink中根据线路信息生成速度时间目标曲线(初速度为20m/s,15秒后减为0的速度时间图像)我想问线路信息是什么