如下构建哈夫曼树并求总权值的方法哪里有错误？为什么我得到的树是错误的？

Question

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

Answer 1

参考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 ;
}