BST采用中序后继删除双孩子节点时根节点值被错误修改问题

问题表现 #

实现BST节点删除逻辑时，采用中序后继方案处理带两个子节点的目标节点，节点可被删除，但操作完成后根节点数据被错误替换为中序后继的值。
测试场景：

• 初始BST结构：

8
    3       10
  1   6         14
     4  7

• 测试目标：删除值为3的节点
• 异常中序遍历输出：1 -> 4 -> 6 -> 7 -> 4 -> 10 -> 14 ->
• 预期正确中序遍历输出：1 -> 4 -> 6 -> 7 -> 8 -> 10 -> 14 ->

原始问题代码 #

struct node *inorderSuccessor(struct node *root, int data) {
        struct node *successor = NULL;
        
        while (root != NULL) {
            
            if (data >= root->data) {
                root = root->right;
            } else {
                successor = root;
                root = root->left;
            }
        }
        
        return successor;
    }

struct node *deleteNode(struct node *root,int data){
    //if tree is empty 
    if(root==NULL){
        return root;
    }

    //finding node to be deleted
    if(data<root->data){
        root->left=deleteNode(root->left,data);
    }
    else if(data>root->data){
        root->right=deleteNode(root->right,data);
    }
    else{
        //node with only one child
        if(root->left==NULL){
            struct node *temp=root->right;
            free(root);
            return temp;
        }
        else if(root->right==NULL){
            struct node *temp=root->left;
            free(root);
            return temp;
        }
    }

    //--------------not working----
    // If the node has two children
    struct node *temp = inorderSuccessor(root,data);
    // Place the inorder successor in position of the node to be deleted
    root->data = temp->data;

    // Delete the inorder successor
    root->right = deleteNode(root->right, temp->data);
  return root;
  }

根因分析 #

核心错误是带双子节点的删除处理逻辑被写在了「匹配到待删除节点」的else分支外部：

1. 当递归找到待删除节点、且该节点同时存在左右子树时，else分支内仅处理了单/零子节点的场景，没有对双子节点场景做任何处理就直接退出了else块。
2. 所有递归路径上的节点，只要没有触发单/零子节点的删除return逻辑，都会走到函数末尾的双子节点处理代码，哪怕当前节点根本不是待删除的目标节点。
3. 以删除值为3的节点为例：最外层递归传入的根节点是8，进入data<root->data分支递归处理左子树节点3；节点3存在两个子节点，else块内没有匹配到单/零子节点的判断，直接返回到最外层递归；此时最外层的root是值为8的全局根节点，代码会继续向下执行，调用inorderSuccessor(root=8, data=3)拿到中序后继4，直接把根节点8的值替换为4，再去右子树删除值为4的节点，最终导致根节点值错误，遍历结果出现重复的4、丢失原根节点值8。

修复方案 #

将双子节点的处理逻辑移动到「命中待删除节点」的else分支内部，确保只有真正匹配到的待删除节点（且排除单/零子节点场景）才会执行中序后继替换逻辑，同时给左右子树的递归查找分支加上返回，避免非目标节点误入替换逻辑。
修复后的deleteNode代码如下：

struct node *deleteNode(struct node *root,int data){
    // 空树直接返回
    if(root==NULL){
        return root;
    }

    // 递归查找待删除节点，未命中当前节点时直接返回，不执行后续替换逻辑
    if(data<root->data){
        root->left=deleteNode(root->left,data);
        return root;
    }
    else if(data>root->data){
        root->right=deleteNode(root->right,data);
        return root;
    }
    else{
        // 命中待删除节点，先处理单/零子节点场景
        if(root->left==NULL){
            struct node *temp=root->right;
            free(root);
            return temp;
        }
        else if(root->right==NULL){
            struct node *temp=root->left;
            free(root);
            return temp;
        }

        // 双子节点场景：仅在命中待删节点时执行中序后继替换
        struct node *temp = inorderSuccessor(root,data);
        root->data = temp->data;
        // 递归删除右子树上的中序后继节点
        root->right = deleteNode(root->right, temp->data);
        return root;
    }
}

修复后重新执行删除3的操作，即可得到预期的中序遍历结果。

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