Binary search tree insert delete find

Binary search tree is a binary tree that satisfies the following conditions:
1. All node values in the left subtree are less than the root node values,
2. All node values in the right subtree are not less than the root node values,
3. Left and right subtrees also meet the above two conditions.

The insertion process of binary search tree is as follows:
1. If the current binary search tree is empty, then the inserted element is the root node,
2. If the value of the inserted element is less than the value of the root node, then the element is inserted into the left subtree.
3. If the value of the inserted element is not less than the value of the root node, the element is inserted into the right subtree.

The deletion of binary search tree is processed in three cases:
1. P is the leaf node, directly delete the node, and then modify the pointer of its parent node (note that it is divided into root node and non-root node), As shown in figure a.

2. P is a single node (that is, only the left or right subtree). Connect the subtree of p to the parent node of p, and delete p; (note that there are root and non-root nodes); As shown in figure b.

3. The left and right subtrees of p are not empty. Find the successor y of p, because y must not have left subtree, so you can delete y, and let the father node of y become the father node of the right subtree of y, and replace the value of p with the value of y; Or the second way is to find the precursor x of p, x must not have a right subtree, so you can delete x and make the parent node of x the parent node of the left subtree of y. As shown in figure c.

< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201309/201309040923182.png ">    

< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201309/201309040923183.png ">

< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201309/201309040923184.png ">

Insert node code:

struct node
{
    int val;
    pnode lchild;
    pnode rchild;
};
pnode BT = NULL;

//Recursive methods insert nodes
pnode insert(pnode root, int x)
{
    pnode p = (pnode)malloc(LEN);
    p->val = x;
    p->lchild = NULL;
    p->rchild = NULL;
    if(root == NULL){
        root = p;    
    }    
    else if(x < root->val){
        root->lchild = insert(root->lchild, x);    
    }
    else{
        root->rchild = insert(root->rchild, x);    
    }
    return root;
}
// non Recursive methods insert nodes
void insert_BST(pnode q, int x)
{
    pnode p = (pnode)malloc(LEN);
    p->val = x;
    p->lchild = NULL;
    p->rchild = NULL;
    if(q == NULL){
        BT = p;
        return ;    
    }        
    while(q->lchild != p && q->rchild != p){
        if(x < q->val){
            if(q->lchild){
                q = q->lchild;    
            }    
            else{
                q->lchild = p;
            }        
        }    
        else{
            if(q->rchild){
                q = q->rchild;    
            }    
            else{
                q->rchild = p;    
            }
        }
    }
    return;
} 

pnode search_BST(pnode p, int x)
{
    bool solve = false;
    while(p && !solve){
        if(x == p->val){
            solve = true;    
        }    
        else if(x < p->val){
            p = p->lchild;    
        }
        else{
            p = p->rchild;    
        }
    }
    if(p == NULL){
        cout << " Could not find " << x << endl;    
    } 
    return p;
}

bool delete_BST(pnode p, int x) //Returns a flag indicating whether the deleted element was found
{
    bool find = false;
    pnode q;
    p = BT;
    while(p && !find){  //Look for the deleted element
        if(x == p->val){  //Find the deleted element
            find = true;    
        }    
        else if(x < p->val){ //Follow the left subtree
            q = p;
            p = p->lchild;    
        }
        else{   //Follow the right subtree
            q = p;
            p = p->rchild;    
        }
    }
    if(p == NULL){   //Did not find
        cout << " Could not find " << x << endl;    
    }

    if(p->lchild == NULL && p->rchild == NULL){  //P is the leaf node
        if(p == BT){  //P is the root node
            BT = NULL;    
        }
        else if(q->lchild == p){   
            q->lchild = NULL;
        }        
        else{
            q->rchild = NULL;    
        }
        free(p);  //Release node p
    }
    else if(p->lchild == NULL || p->rchild == NULL){ //P is a single subtree
        if(p == BT){  //P is the root node
            if(p->lchild == NULL){
                BT = p->rchild;    
            }    
            else{
                BT = p->lchild;    
            }
        }    
        else{
            if(q->lchild == p && p->lchild){ //P is the left subtree of q and p has the left subtree
                q->lchild = p->lchild;    //Links the left subtree of p to the left pointer to q
            }    
            else if(q->lchild == p && p->rchild){
                q->lchild = p->rchild;    
            }
            else if(q->rchild == p && p->lchild){
                q->rchild = p->lchild;    
            }
            else{
                q->rchild = p->rchild;
            }
        }
        free(p);
    }
    else{ //The left and right subtrees of p are not empty
        pnode t = p;
        pnode s = p->lchild;  //We start with the left child of p
        while(s->rchild){  //Find the precursor of p, that is, the node with the largest value in the left subtree of p
            t = s;   
            s = s->rchild;    
        }
        p->val = s->val;   //Assign the value of node s to p
        if(t == p){
            p->lchild = s->lchild;    
        }    
        else{
            t->rchild = s->lchild;    
        }
        free(s); 
    }
    return find;
}