二叉树广度优先打印函数为何会异常删除节点？

嘿，我一眼就瞅到问题出在哪了——你的函数参数用了Node *& cur_root，这是对指针的引用啊！要是你在函数里不小心修改了这个引用指向的内容（比如把它置成NULL，或者释放了节点内存），那直接就会把原树的节点给搞没，这就是为啥最后树变空了。

核心问题拆解 #

从你给的代码片段来看，你已经把当前节点的左右子节点入队了，但大概率你后续处理队列的时候，做了类似这样的操作：

cur_root = NULL; // 或者 delete cur_root;
// 或者把队列弹出的节点赋值给cur_root，同时动了原节点的指针

因为cur_root是引用，你改它就等于改原树里对应的节点指针，这不就把原树的节点一个个清空了嘛！

修复方案来啦 #

方案1：去掉参数的引用（最简单） #

把函数参数改成普通指针Node *cur_root，这样函数内部对cur_root的任何修改都不会影响原树的结构：

void BST::breadth(Node *cur_root) {
    if (cur_root != NULL) {
        cout << cur_root->m_value;
        if (cur_root->m_left != NULL) {
            myqueue.push(cur_root->m_left);
        }
        if (cur_root->m_right != NULL) {
            myqueue.push(cur_root->m_right);
        }
        // 处理队列剩余节点的逻辑
        while (!myqueue.empty()) {
            Node *next_node = myqueue.front();
            myqueue.pop();
            breadth(next_node); // 这里传普通指针，别用引用！
        }
    }
}

方案2：用迭代式BFS（更稳妥） #

其实BFS用迭代实现本来就更清晰，还能避免递归带来的指针引用坑，推荐你直接换成这种写法，完全不会碰原树的节点指针：

void BST::breadth(Node *root) {
    if (root == NULL) return;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node *current = q.front();
        q.pop();
        cout << current->m_value;
        // 左右子节点入队
        if (current->m_left != NULL) {
            q.push(current->m_left);
        }
        if (current->m_right != NULL) {
            q.push(current->m_right);
        }
    }
}

这种写法用局部队列，不依赖类成员的myqueue，也只会读取节点的值和子节点指针，绝对不会搞坏原树。

额外注意点 #

• 检查你之前的代码里有没有delete cur_root或者cur_root = NULL这类操作，赶紧删掉！BFS遍历只需要访问节点，不需要修改或者删除它们。
• 如果你非要用类成员的myqueue，记得每次调用BFS前先清空它，不然上次遍历的残留节点会搞乱这次的输出顺序。

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