BST（二叉搜索树）函数中删除节点的问题（代码）

Question

我们知道如果节点有两个孩子，有两种方法可以删除它 在我的例子中，如果我们取最大值的最小值，一切都很好 当我们取分钟的最大值时，程序会丢失或删除我们删除的节点的子树。 请在我的代码上。

我尝试在函数中做指针的指针，但没有任何变化。 我尝试在我们删除的节点上做一个指针，并从它开始执行该过程，但仍然不起作用。

#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;
}

Answer 1

问题是你的递归函数并不总是执行

return

语句。值得注意的是，在节点没有两个子节点的情况下，在进行递归调用后不会返回根。

解决方案是将最后一个

return root;

语句移出两个嵌套的

else

块，以便在前几种情况下也执行该语句。