Huffman Tree指针指向异常位置问题排查与修复求助

嘿，我帮你找到了代码出问题的核心原因，咱们一步步拆解，再给你修复方案：

为什么会出现诡异的深度和无限递归？ #

你的代码里有两个致命的内存管理问题，直接导致了野指针和非法内存访问：

1. 优先级队列存的是Node对象，而非指针 #

你用priority_queue<Node, vector<Node>, Greater>存储的是Node的实例拷贝。每次调用weights_queue.top()时，拿到的是队列中对象的临时拷贝，然后你把这个临时对象的地址（&l1、&l2）传给新创建的l3节点。一旦l1和l2这两个临时对象被销毁（比如出了当前循环块），l3的左右子指针就变成了野指针——指向已经被系统回收的内存。后续访问这些指针时，会读到随机的垃圾数据，这就是你看到深度为4700、无限递归的直接原因。

2. 队列参数按值传递，加剧拷贝问题 #

build_Huffman_tree的参数是priority_queue<Node, vector<Node>, Greater> weights_queue，这会把整个队列拷贝一份，不仅效率低，还会产生更多临时对象，让野指针问题更严重。

修复后的完整代码 #

我们需要把队列改为存储Node*指针，用动态分配内存的方式避免临时对象被销毁，同时调整相关逻辑：

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

struct Node {
    int weight, depth;
    Node *left, *right;
    Node(int value):weight(value), left(nullptr),right(nullptr),depth(0){}
    Node(int value, Node* left_leaf_ptr, Node* right_leaf_ptr) 
        : weight(value), left(left_leaf_ptr), right(right_leaf_ptr), depth(0) {}
};

// 优先级队列的比较器：比较指针指向的Node权重
struct Greater {
    bool operator () (Node* a, Node* b){
        return a->weight > b->weight;
    }
};

// 判断是否是叶子节点（用指针更高效）
bool isleaf(Node* node) {
    return node->left == nullptr && node->right == nullptr;
}

// 更新树的深度（用指针避免拷贝）
void update_depth(Node* node, int depth) {
    node->depth = depth;
    if (!isleaf(node)) {
        depth++;
        update_depth(node->left, depth);
        update_depth(node->right, depth);
    }
}

// 传递队列的引用，避免拷贝
Node* build_Huffman_tree(priority_queue<Node*, vector<Node*>, Greater>& weights_queue) {
    while (weights_queue.size() > 1) {
        Node* l1 = weights_queue.top();
        weights_queue.pop();
        Node* l2 = weights_queue.top();
        weights_queue.pop();
        // 动态分配新节点，左右子树指向取出的两个节点
        Node* l3 = new Node(l1->weight + l2->weight, l1, l2);
        update_depth(l3, 0);
        weights_queue.push(l3);
    }
    return weights_queue.top();
}

// 递归删除整个树，避免内存泄漏
void delete_tree(Node* node) {
    if (node == nullptr) return;
    delete_tree(node->left);
    delete_tree(node->right);
    delete node;
}

int main() {
    priority_queue<Node*, vector<Node*>, Greater> weights_queue;
    // 动态创建节点入队
    weights_queue.push(new Node(1));
    weights_queue.push(new Node(1));
    weights_queue.push(new Node(3));
    weights_queue.push(new Node(5));
    
    Node* root = build_Huffman_tree(weights_queue);
    
    // 可以在这里打印测试深度，比如 cout << root->left->depth << endl;
    delete_tree(root); // 释放内存
    return 0;
}

关键修复点说明 #

• 改用指针存储：优先级队列存Node*，避免临时对象拷贝和销毁导致的野指针
• 动态分配内存：用new创建节点，保证内存不会被临时回收
• 队列参数用引用：避免整个队列的拷贝，提升效率
• 添加内存释放逻辑：用递归函数删除整个树，防止内存泄漏

现在运行这段代码，深度计算会完全正确，也不会出现无限递归的问题了。

内容的提问来源于stack exchange，提问作者Zirui Wei