Binary search tree

Binary search tree concept

Binary search tree （BST,Binary Search Tree）, Also called binary sort tree or binary search tree .

Binary search tree ： A binary tree , Can be null ; If it's not empty , Satisfy the following properties ：

1. All key values of a non empty left subtree are less than the key values of its root node .
2. All key values of a non empty right subtree are greater than the key values of its root node .
3. Left 、 Right subtrees are binary search trees .

The abstract data types of binary search tree are as follows ：

Binary search tree lookup

Find an element

• Search starts at the root , If the tree is empty , return NULL
• If the search tree is not empty , Then the root key and X Compare , And do different things ：
   if X Less than the root key value , Just continue searching in the left subtree ;
   If X Greater than the key value of the root , Continue searching in the right subtree ;
   If the result of the comparison is equal , search complete , Return the pointer to this node .

This is called tail recursion , That is to say return Recursion at , Tail recursion can generally be rewritten into a loop ：

Search operation for binary search tree , The efficiency of its search depends on the height of the tree . If all nodes have only left sons and no right sons , At this point, a chain is formed , The efficiency of search is less than logn, It can also be understood from here , Only the more balanced the tree is （ The nodes of the left subtree and the right subtree are similar ）, The more efficient the search will be , The closer the logn.
This part can refer to the binary search decision tree https://blog.csdn.net/qq_38048756/article/details/118874713.

Find the maximum and minimum elements

There are two ways to find the implementation of the largest element and the smallest element , One is recursion , One is a cycle .

Insertion node of binary search tree

First, compare with the current node , If it is larger than the current node value , Recursion to the right subtree , At this time, the recursive function is required to return the position of the inserted root node , Then hang this position on the right pointer of the current node ; If it is smaller than the current node value , Recurse to the left subtree , At this time, the recursive function is required to return the position of the inserted root node , Then hang this position on the left pointer on the current node .

Delete node of binary search tree

There are three situations to consider when deleting a binary search tree ：

• The leaf node to be deleted ： Delete directly , And then modify its parent node pointer （ Set as NULL）
• The node to be deleted has only one child node ： Point the pointer of its parent node to the child node to delete
• The node to be deleted has left 、 Two subtrees on the right ： Replace the deleted node with another node ： The smallest element of the right subtree or the largest element of the left subtree , Then delete the smallest element of the right subtree or the largest element of the left subtree .

Case one ：

The second case ：

The third case ：

The overall code

The following is the code of all the implementations ：

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

typedef int ElementType;
typedef struct TreeNode *BinTree;
struct TreeNode{
    
	ElementType Data;
	BinTree Left;
	BinTree Right;
};
BinTree create(BinTree BST);

void preorder(BinTree BST);
void inorder(BinTree BST);

BinTree Find(ElementType x, BinTree BST);
BinTree Find2(ElementType x, BinTree BST);
BinTree FindMin(BinTree BST);
BinTree FindMax(BinTree BST);

BinTree Insert(ElementType x, BinTree BST);
BinTree Delete(ElementType x, BinTree BST);

int main()
{
    
     BinTree BST = NULL;
     BinTree postion = NULL;
     BST = create(BST);
     postion = Find(33, BST);
     printf("%d\n", postion->Data);
     inorder(BST);
     printf("\n");
     postion = FindMax(BST);
     printf(" Maximum %d\n", postion->Data);
     postion = FindMin(BST);
     printf(" minimum value %d\n", postion->Data);

     Insert(35, BST);
     inorder(BST);

     printf("\n");
     Delete(41, BST);
     inorder(BST);



     return 0;
}

void preorder(BinTree BST)
{
    
     if(BST)
     {
    
          printf("%d ", BST->Data);
          preorder(BST->Left);
          preorder(BST->Right);
     }
}
void inorder(BinTree BST)
{
    
     if(BST)
     {
    
          inorder(BST->Left);
          inorder(BST->Right);
          printf("%d ", BST->Data);

     }
}
BinTree Insert(ElementType x, BinTree BST)
{
    
     // The tree is empty. , Generate and return a binary search prime tree of a node 
     if(!BST)
     {
    
          BST = (BinTree)malloc(sizeof(struct TreeNode));
          BST->Data = x;
          BST->Left = NULL;
          BST->Right = NULL;
     }
     else{
      // Find the location of the inserted element 
          if(x < BST->Data)
               BST->Left = Insert(x, BST->Left);  // Recursively insert the left subtree 
          else if(x > BST->Data)
               BST->Right = Insert(x, BST->Right);  // Recursively insert right subtree 
          //else x This value already exists , Don't do anything? 
     }
     return BST;
}
BinTree Delete(ElementType x, BinTree BST)
{
    
     BinTree tmp;
     if(!BST) printf(" The element to be deleted was not found ");
     else if (x < BST->Data)
          BST->Left = Delete(x, BST->Left);
     else if (x > BST->Data)
          BST->Right = Delete(x, BST->Right);
     else{
    
               if(BST->Left && BST->Right)
               {
    
                    tmp = FindMin(BST->Right);
                    BST->Data = tmp->Data;
                    BST->Right = Delete(BST->Data, BST->Right);
               }
               else{
    
                    tmp = BST;
                    if(!BST->Left)
                         BST = BST->Right;
                    else if(!BST->Right)
                         BST = BST->Left;
                    free(tmp);
               }
     }
     return BST;
}

BinTree create(BinTree BST)
{
    
     BST = Insert(30, BST);
     BST = Insert(15, BST);
     BST = Insert(41, BST);
     BST = Insert(33, BST);
     BST = Insert(50, BST);
     return BST;

}

BinTree Find(ElementType x, BinTree BST)
{
    
     if(!BST) return NULL;
     if(x > BST->Data)
          return Find(x, BST->Right);
     else if(x < BST->Data)
          return Find(x, BST->Left);
     else
          return BST;
}
BinTree Find2(ElementType x, BinTree BST)
{
    
     while(BST)
     {
    
          if(x > BST->Data)
               BST = BST->Right;
          else if(x < BST->Data)
               BST = BST->Left;
          else
               return BST;
     }
     return NULL;
}
BinTree FindMin(BinTree BST)
{
    
     /* //  Recursive solution  if(!BST) return NULL; // Empty binary search tree , return NULL else if(!BST->Left) return BST; // Find the leftmost leaf node and return  else return FindMin(BST->Left); // Continue searching along the left branch  */
     // Iterative solution 
     if(BST)
     {
    
          while(BST->Left)
               BST = BST->Left;
     }
     return BST;
}
BinTree FindMax(BinTree BST)
{
    

     //  Recursive solution 
     if(!BST)
          return NULL;  // Empty binary search tree , return NULL
     else if(!BST->Right)
          return BST;  // Find the leftmost leaf node and return 
     else
          return FindMax(BST->Right);  // Continue searching along the left branch 
     /* // Iterative solution  if(BST) { while(BST->Right) BST = BST->Right; } return BST; */
}

Reference resources ： Data structure of Zhejiang University