OiO.lk Community platform!

Oio.lk is an excellent forum for developers, providing a wide range of resources, discussions, and support for those in the developer community. Join oio.lk today to connect with like-minded professionals, share insights, and stay updated on the latest trends and technologies in the development field.
  You need to log in or register to access the solved answers to this problem.
  • You have reached the maximum number of guest views allowed
  • Please register below to remove this limitation

Problem with Deleting node in BST (Binary Search Tree) function (code)

  • Thread starter Thread starter Ahmed Hamidou
  • Start date Start date
A

Ahmed Hamidou

Guest
We know that there is two ways to delete node if he had two childs in my exemple if we take the min of the maxs all is good when we take the max of the mins the program miss or remove a sub-tree of the node we remove. On my code please.

I tried to do pointer of pointer in the functions and nothing changes. I tried to do a pointer on the node we delete and do the process starting from it and still not working.

Code:
#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;
}
<p>We know that there is two ways to delete node if he had two childs
in my exemple if we take the min of the maxs all is good
when we take the max of the mins the program miss or remove a sub-tree of the node we remove.
On my code please.</p>
<p>I tried to do pointer of pointer in the functions and nothing changes.
I tried to do a pointer on the node we delete and do the process starting from it and still not working.</p>
<pre><code>#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;
}
</code></pre>
I have found how to fix this.
 

Latest posts

Top