Binary sort tree

lookup

Non recursive

Left subtree node value < Root node value < Right subtree node value
If the tree is not empty , Comparison between target value and root node value , If it is equal, the search is successful
If less than the root node , Then find... In the left subtree
Otherwise, look in the right subtree .
Find success , Return node pointer ; Search failed return NULL

// The non recursive search value of binary sort tree is key The node of 
// The worst space complexity is O(1)
BiTNode *BSTSearchNonR(BiTree T, int key){
    
    while(T != NULL && T->data != key){
    // If the tree is empty or equal to the root node value , End cycle 
        if(key < T->data){
    // Less than , Then find... In the left subtree 
            T=T->lchild;
        }
        else{
    // Greater than , Then find... On the right subtree 
            T=T->rchild;
        }
    }
    return T;
}

recursive

The recursive search value of binary sort tree is key The node of The worst spatial complexity O(h) h Is the height of the tree

BiTNode *BSTSearchR(BiTree T,int key){
    
    if(T == NULL){
    
        return NULL;// To find the failure 
    }
    if(T->data == key){
    // Find success 
        return T;
    }
    else if(key < T->data){
    
        return BSTSearchR(T->lchild,key);// Look for... In the left subtree 
    }
    else{
    
        return BSTSearchR(T->rchild,key);// Look for... In the right subtree 
    }
}

Insert

Binary sort tree insertion ( Recursive implementation ), The worst spatial complexity O(h)

bool BSTInsert(BiTree &T, int k){
    
    if(T == NULL){
    // The original tree is empty 
        T=(BiTree)malloc(sizeof(BiTNode));
        T->data = k;
        T->lchild=T->rchild=NULL;
        return true;
    }
    else if(k==T->data){
    
        printf(" The same keyword node exists in the tree  %d , Insert the failure \n",k);
        return false;
    }
    else if(k < T->data){
    

        return BSTInsert(T->lchild,k);// Insert into T The left subtree 
    }
    else{
    

        return BSTInsert(T->rchild,k);// Insert into T The right subtree 
    }
}

The construction of binary sort tree

// The construction of binary sort tree 
void CreateBST(BiTree &T,ElemType str[], int n){
    
    T=NULL;// Initially, the tree is empty 
    int i=0;
    while(i<n){
    // Insert each keyword into the binary sort tree in turn 
        BSTInsert(T,str[i]);
        i++;
    }
}

In the sequence traversal

Just like the normal traversal of binary tree , And for binary sort trees , The result of middle order traversal is output in the order from small to large

void visit(BiTree T){
    
    printf("%d ",T->data);
}
// Middle order traversal of binary trees 
void InOrder(BiTree T){
    
    if(T){
    
        InOrder(T->lchild);// Recursively traverses the left subtree 
        visit(T);
        InOrder(T->rchild);
    }
}

Delete

Analysis of three cases of deleting nodes ：

1. leaf node
2. Nodes with only left or right subtrees
3. There are nodes in both left and right subtrees
   The following algorithm recursively sorts binary trees T lookup key, Delete when found
   Replace the deleted node with the precursor of the node to be deleted
   BSTDelete This code is the same as the previous The recursive search of binary sort tree is almost identical
   The only difference is k== T->data when , Execution is Delete operation

bool Delete(BiTree &p){
    // Delete p node 
    BiTree q,s;
    if(p->rchild == NULL){
    // If the right subtree is empty, you only need to reconnect its left subtree 
        q=p; /* Delete no right subtree , Only the nodes of the left subtree .  At this point, you only need to replace the left child of this node with itself , Then release the memory of this node ,  It means deleting , Don't need to care about p Of the parent node of lchild,rchild Pointer change ,！！！@@@  because p Parent node lchild,rchild The pointer means p, and p Who do you mean , The parent node does not care   Here we use q To point to the node to be released , and p Point to your left child , It is equivalent to replacing yourself with a left child  */
        p=p->lchild;
        free(q);
    }
    else if(p->lchild == NULL){
    
        // Just reconnect its right subtree 
        q=p;
        p=p->rchild;
        free(q);
    }
    else{
    // Left and right subtrees are not empty 
        q=p;// The node to be deleted p Assigned to a temporary variable p
        s=p->lchild;// then p The left child p->lchild Assign to a temporary variable s
        while(s->rchild){
    // Loop through the right node of the left subtree , To the right end 
        // Turn left , Then go right to the end （ Find the precursor of the node to be deleted ）
            q=s; // take q Point to s The precursor node of , namely <= Node to be deleted   The second node 
            s=s->rchild;
// and s Point to the node without right subtree ,s It is the precursor of the node to be deleted .
// namely < The maximum node of the node to be deleted 

        }
        p->data=s->data;//s Direct precursor to the deleted node 
        if(q!=p){
    
            q->rchild=s->lchild;// Reconnection q The right subtree 
        }
        else{
    // This description q=p be s Must be p The root node of the left subtree of , And s No right subtree 
           q->lchild=s->lchild; // Reconnection q The left subtree 
        }
// It's used here “ place a substitute by subterfuge ”, In fact, it did not delete p, But deleted s, Just put 
//s The data of is assigned to p The location of 
        free(s);
    }
    return true;
}

---

chart 8-6-13

---

chart 8-6-14

---

chart 8-6-15

---

chart 8-6-16

---

/* Delete binary sorting tree   Analysis of three cases of deleting nodes ： 1.  leaf node  2. Nodes with only left or right subtrees  3. There are nodes in both left and right subtrees   The following algorithm recursively sorts binary trees T lookup key, Delete when found   Replace the deleted node with the precursor of the node to be deleted  BSTDelete This code is the same as the previous   The recursive search of binary sort tree is almost identical   The only difference is k== T->data when , Execution is Delete operation  */
bool BSTDelete(BiTree &T,int key){
    
    if(!T){
    // If there is no keyword equal to key Data elements 
        return false;
    }
    else{
    
        if(key == T->data){
    // Finding keywords equals key Data elements 
            return Delete(T);
        }
        else if(key < T->data){
    
            return BSTDelete(T->lchild,key);
        }
        else{
    
            return BSTDelete(T->rchild,key);
        }
    }
}

Complete test code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define ElemType int
// Binary sort tree BST

// Storage structure   Node of binary sort tree 
typedef struct BiTNode{
    
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

/* Left subtree node value  <  Root node value  <  Right subtree node value   If the tree is not empty , Comparison between target value and root node value , If it is equal, the search is successful   If less than the root node , Then find... In the left subtree   Otherwise, look in the right subtree .  Find success , Return node pointer ; Search failed return NULL */
// The non recursive search value of binary sort tree is key The node of 
// The worst space complexity is O(1)
BiTNode *BSTSearchNonR(BiTree T, int key){
    
    while(T != NULL && T->data != key){
    // If the tree is empty or equal to the root node value , End cycle 
        if(key < T->data){
    // Less than , Then find... In the left subtree 
            T=T->lchild;
        }
        else{
    // Greater than , Then find... On the right subtree 
            T=T->rchild;
        }
    }
    return T;
}

// The recursive search value of binary sort tree is key The node of   The worst spatial complexity O(h) h Is the height of the tree 
BiTNode *BSTSearchR(BiTree T,int key){
    
    if(T == NULL){
    
        return NULL;// To find the failure 
    }
    if(T->data == key){
    // Find success 
        return T;
    }
    else if(key < T->data){
    
        return BSTSearchR(T->lchild,key);// Look for... In the left subtree 
    }
    else{
    
        return BSTSearchR(T->rchild,key);// Look for... In the right subtree 
    }
}

// Binary sort tree insertion ( Recursive implementation ), The worst spatial complexity O(h)
bool BSTInsert(BiTree &T, int k){
    
    if(T == NULL){
    // The original tree is empty 
        T=(BiTree)malloc(sizeof(BiTNode));
        T->data = k;
        T->lchild=T->rchild=NULL;
        return true;
    }
    else if(k==T->data){
    
        printf(" The same keyword node exists in the tree  %d , Insert the failure \n",k);
        return false;
    }
    else if(k < T->data){
    

        return BSTInsert(T->lchild,k);// Insert into T The left subtree 
    }
    else{
    

        return BSTInsert(T->rchild,k);// Insert into T The right subtree 
    }
}

bool Delete(BiTree &p){
    
    BiTree q,s;
    if(p->rchild == NULL){
    // If the right subtree is empty, you only need to reconnect its left subtree 
        q=p;
        p=p->lchild;
        free(q);
    }
    else if(p->lchild == NULL){
    
        // Just reconnect its right subtree 
        q=p;
        p=p->rchild;
        free(q);
    }
    else{
    // Left and right subtrees are not empty 
        q=p;
        s=p->lchild;
        while(s->rchild){
    
        // Turn left , Then go right to the end （ Find the precursor of the node to be deleted ）
            q=s;
            s=s->rchild;
        }
        p->data=s->data;//s Direct precursor to the deleted node 
        if(q!=p){
    
            q->rchild=s->lchild;// Reconnection q The right subtree 
        }
        else{
    
           q->lchild=s->lchild; // Reconnection q The left subtree 
        }
        free(s);
    }
    return true;
}


/* Delete binary sorting tree   Analysis of three cases of deleting nodes ： 1.  leaf node  2. Nodes with only left or right subtrees  3. There are nodes in both left and right subtrees   The following algorithm recursively sorts binary trees T lookup key, Delete when found   Replace the deleted node with the precursor of the node to be deleted   This code is the same as the previous   The recursive search of binary sort tree is almost identical   The only difference is k== T->data when , Execution is Delete operation  */
bool BSTDelete(BiTree &T,int key){
    
    if(!T){
    // If there is no keyword equal to key Data elements 
        return false;
    }
    else{
    
        if(key == T->data){
    // Finding keywords equals key Data elements 
            return Delete(T);
        }
        else if(key < T->data){
    
            return BSTDelete(T->lchild,key);
        }
        else{
    
            return BSTDelete(T->rchild,key);
        }
    }
}



// The construction of binary sort tree 
void CreateBST(BiTree &T,ElemType str[], int n){
    
    T=NULL;// Initially, the tree is empty 
    int i=0;
    while(i<n){
    // Insert each keyword into the binary sort tree in turn 
        BSTInsert(T,str[i]);
        i++;
    }
}


void visit(BiTree T){
    
    printf("%d ",T->data);
}
// Middle order traversal of binary trees 
void InOrder(BiTree T){
    
    if(T){
    
        InOrder(T->lchild);// Recursively traverses the left subtree 
        visit(T);
        InOrder(T->rchild);
    }
}


// After the sequence traversal , Destroy the binary sort tree 
bool DestroyBiTree(BiTree T){
    // Delete without &
    if(T==NULL){
    
        printf(" Blank nodes #\n");
        return false;
    }
    DestroyBiTree(T->lchild);
    DestroyBiTree(T->rchild);
    printf(" The destruction %d\n",T->data);
    free(T);
    T=NULL;// To prevent the generation of wild pointers 
    return true;

}

int main(){
    
    ElemType a[6]={
    45,24,53,45,12,24};
    BiTree T=NULL;
    printf(" Construct a binary sort tree , Insert... In turn {45,24,53,45,12,24}\n");
    CreateBST(T,a,6);
    printf(" In the sequence traversal :");
    InOrder(T);
    printf("\n");


    BSTInsert(T,48);
    printf(" Insert node 48  Middle order traversal after :");
    InOrder(T);
    printf("\n");


    BSTDelete(T,45);
    printf(" Delete node 45  Middle order traversal after :");
    InOrder(T);
    printf("\n");
/* BSTDelete(T,12); printf(" Delete node 12  Middle order traversal after :"); InOrder(T); printf("\n");*/
    printf("\n Remember to destroy it after use （ Traverse and destroy in sequence ）!\n");
    DestroyBiTree(T);


}

The test sample