二叉树节点删除替换问题：复制代码后输出不符求排查

我尝试实现二叉树中删除指定节点并将其替换为最深节点的功能，但我的程序结果和参考代码不一致。参考代码会将目标节点替换为最深的右节点，而我的程序看起来像是只删除了目标节点（实际是替换成了最深的左节点）。

参考程序输出：

删除前中序遍历：7 11 12 10 15 9 8
删除后中序遍历：7 8 12 10 15 9

我的程序输出：

删除前中序遍历：7 11 12 10 15 9 8
删除后中序遍历：7 12 10 15 9 8

我的代码如下：

#include<bits/stdc++.h>
using namespace std;
struct Node {
    int key;
    struct Node* left;
    struct Node* right;
};
struct Node* newNode(int key) {
    struct Node* temp= new Node;
    temp->key=key;
    temp->left=temp->right=NULL;
    return temp;
}
void inorder(struct Node* temp) {
    if(!temp) return;
    inorder(temp->left);
    cout<<temp->key<<" ";
    inorder(temp->right);
}
void deletDeepest(struct Node* root,struct Node* d_node) {
    queue <struct Node*> q;
    q.push(root);
    struct Node* temp;
    while(!q.empty()) {
        temp = q.front();
        q.pop();
        if(temp==d_node) {
            temp=NULL;
            delete(d_node);
            return;
        }
        if(temp->right) {
            if(temp->right==d_node) {
                temp->right=NULL;
                delete(d_node);
                return;
            } else q.push(temp->right);
        }
        if(temp->left) {
            if(temp->left==d_node) {
                temp->left=NULL;
                delete(d_node);
                return;
            } else q.push(temp->left);
        }
    }
}
void deletion(struct Node* root, int key) {
    struct Node* temp;
    struct Node* key_node=NULL;
    queue <struct Node*> q;
    q.push(root);
    while(!q.empty()) {
        temp=q.front();
        q.pop();
        if(temp->key==key) key_node=temp;
        if(temp->right) q.push(temp->right);
        if(temp->left) q.push(temp->left);
    }
    int x = temp->key;
    deletDeepest(root,temp);
    key_node->key=x;
}
int main() {
    struct Node* root = newNode(10);
    root->left = newNode(11);
    root->left->left = newNode(7);
    root->left->right = newNode(12);
    root->right = newNode(9);
    root->right->left = newNode(15);
    root->right->right = newNode(8);
    cout << "Inorder traversal before deletion : ";
    inorder(root);
    int key = 11;
    deletion(root, key);
    cout << endl;
    cout << "Inorder traversal after deletion : ";
    inorder(root);
    return 0;
}

问题根源 #

输出差异的核心原因是队列中节点的入队顺序错误，导致你选中的“最深节点”和参考程序不一致：

• 参考程序在遍历二叉树时，先将左子节点入队，再将右子节点入队，这样队列最后弹出的节点是最深层最右侧的节点（也就是示例中的8）。
• 而你的代码中是先将右子节点入队，再将左子节点入队，队列最后弹出的节点变成了最深层最左侧的节点（也就是示例中的7）。

这就导致：

• 参考程序用最深右节点8替换目标节点11，然后删除8，所以中序遍历中11的位置变成8，且原8被移除。
• 你的代码用最深左节点7替换目标节点11，然后删除原7，所以中序遍历中11的位置变成7（和原7的位置重合，看起来像是11被直接删除了）。

另外，你的代码还有一个潜在问题：如果要删除的节点不存在（key_node为NULL），直接访问key_node->key会导致未定义行为（比如程序崩溃）。

修复方法 #

1. 修正队列入队顺序：在deletion函数中，先将左子节点入队，再将右子节点入队，这样就能正确获取最深层最右侧的节点。
2. 增加空指针判断：在替换节点值之前，检查key_node是否为NULL，避免非法内存访问。

修复后的deletion函数代码如下：

void deletion(struct Node* root, int key) {
    struct Node* temp;
    struct Node* key_node=NULL;
    queue <struct Node*> q;
    q.push(root);
    while(!q.empty()) {
        temp=q.front();
        q.pop();
        if(temp->key==key) key_node=temp;
        // 先入队左节点，再入队右节点，保证最后弹出的是最深最右节点
        if(temp->left) q.push(temp->left);
        if(temp->right) q.push(temp->right);
    }
    // 如果未找到要删除的节点，直接返回
    if(key_node == NULL) {
        cout << "Node with key " << key << " not found!" << endl;
        return;
    }
    int x = temp->key;
    deletDeepest(root,temp);
    key_node->key=x;
}

验证修复效果 #

修复后运行程序，输出会和参考程序一致：

删除前中序遍历：7 11 12 10 15 9 8
删除后中序遍历：7 8 12 10 15 9

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