二叉搜索树(BST)节点删除异常：左子树最大节点替换致子树丢失

在二叉搜索树（BST）的节点删除操作中，删除拥有两个子节点的节点时有两种常见方案：采用右子树最小节点替换时功能正常，但采用左子树最大节点替换时，程序会丢失或误删待删节点的子树。尝试过指针的指针、直接从待删节点开始处理等方法，问题仍未解决，请排查代码。

#include<stdio.h>
#include<stdlib.h>

typedef struct noeud Node;
struct noeud
{
    int valeur;
    Node *gauche;
    Node *droit;
};

Node *createNode(int val)
{
    Node *newNode = malloc(sizeof(Node));
    newNode->valeur = val;
    newNode->gauche = NULL;
    newNode->droit = NULL;
    return newNode;
}

void infixe(Node *root)
{
    if (root == NULL)
        return;
    infixe(root->gauche);
    printf("%d - ",root->valeur);
    infixe(root->droit);
}

Node* findMin(Node* root){
    Node* current=root;
    while(current->gauche!=NULL)
        current=current->gauche;

    return current;
}
Node* findMax(Node* root){
    Node* current=root;
    while(current->droit!=NULL)
        current=current->droit;

    return current;
}

Node* deleteInBST(Node* root,int val){
     
    if(root==NULL) return root;

    if(val<root->valeur){
        root->gauche=deleteInBST(root->gauche,val);
    }
    else if(val>root->valeur){
        root->droit=deleteInBST(root->droit,val);
    }
    else{
            //! here of the root we wanna delete hasn't gauche child so we take the droit and we delete the root
            if(root->gauche==NULL){
                Node* temp=root->droit;
                free(root);
                return temp;
            }   
            //! here of the root we wanna delete hasn't droit child so we take the gauche and we delete the root
            else if(root->droit==NULL){
                Node* temp=root->gauche;
                free(root);
                return temp;
            }
            else{
            //! here if the root has two child so we have 02 ways to do it 
                //! the first we take the min of the maxs
                /*Node* temp=findMin(root->droit);
                root->valeur=temp->valeur;
                root->droit=deleteInBST(root->droit,temp->valeur);
                //! the second we take the max of the mins 
                */
                Node* temp=findMax(root->gauche);
                root->valeur=temp->valeur;
                root->gauche=deleteInBST(root->gauche,temp->valeur);
                
                return root;
            }
    }
}


int main(){ 
    
    Node* root = createNode(25);
    root->gauche = createNode(10);
    root->droit = createNode(60);
    root->gauche->gauche = createNode(5);
    root->gauche->droit = createNode(20);
    root->gauche->droit->gauche = createNode(15);
    

    root->droit->gauche = createNode(35);
    root->droit->gauche->gauche = createNode(30);
    root->droit->gauche->droit = createNode(45);

    
    root->droit->gauche->droit->gauche = createNode(40);
    root->droit->gauche->droit->gauche->gauche = createNode(37);
    root->droit->gauche->droit->gauche->droit = createNode(43);


    root->droit->droit = createNode(65);
    root->droit->droit->droit = createNode(70);



    printf("\n");
    infixe(root);

    /*//! here if we do root=deleteInBST(root,60) we lose the tree if we keep it like i wrote it we lose the sub_tree of 60 in the 
        // !most left           */

    deleteInBST(root,60);
    printf("\n");
    infixe(root);
    
    return 0;
}

问题根源 #

代码的核心问题是deleteInBST函数的返回值处理不完整：

• 当递归处理左/右子树的删除操作时（val < root->valeur或val > root->valeur分支），函数没有返回当前的root节点，导致上层调用无法正确接收更新后的子树指针，进而引发子树丢失的未定义行为。
• 右子树最小节点替换方案看似正常，只是测试用例未触发潜在的未定义行为，本质上存在同样的漏洞。

修复方案 #

修改deleteInBST函数，确保所有分支都有明确的返回值，同时在main中正确接收删除操作后的根节点：

修复后的deleteInBST函数

Node* deleteInBST(Node* root,int val){
     
    if(root==NULL) return root;

    if(val<root->valeur){
        root->gauche=deleteInBST(root->gauche,val);
    }
    else if(val>root->valeur){
        root->droit=deleteInBST(root->droit,val);
    }
    else{
            // 无左子节点
            if(root->gauche==NULL){
                Node* temp=root->droit;
                free(root);
                return temp;
            }   
            // 无右子节点
            else if(root->droit==NULL){
                Node* temp=root->gauche;
                free(root);
                return temp;
            }
            else{
            // 双子女节点：左子树最大节点替换方案
                Node* temp=findMax(root->gauche);
                root->valeur=temp->valeur;
                root->gauche=deleteInBST(root->gauche,temp->valeur);
            }
    }
    // 关键：处理完子树删除后，返回当前根节点
    return root;
}

修改main中的调用

// 接收删除操作后的根节点，避免根节点失效时丢失整棵树
root = deleteInBST(root,60);

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