Binary sort tree (BST)~

Binary sort tree is also called binary search tree , Binary search tree ‍*️~

• Node type definition

typedef struct BTNode{
    
	int key;
	struct BTNode *lchild;
	struct BTNode *rchild;	
}BTNode;

• Find keywords

BTNode* BTSearch(BTNode *bt,int key){
    
	if(bt==NULL)
		return NULL;
	else{
    
		if(bt->key==key)
			return bt;
		else if(bt->key<key)
			return search(bt->rchild,key)
		else
			return search(bt->lchild,key)
	}
}

• Insert keywords

int BSTInsert(BTNode *&bt,int key){
    
	if(bt==NULL){
    
		bt=(BTNode *)malloc(sizeof(BTNode));
		bt->lchild=b->rchild=NULL;
		bt->key=key;
		return 1;
	)
	else{
    
		if(bt->key==key)
			return 0;
		else if(bt->data<key)
			return BSTInsert(bt->rchild,key);
		else 
			return BSTInsert(bt->lchild,key);
	}
}

• Construct a binary sort tree

void CreateBST(BTNode *&bt,int key[],int n){
    
	int i;
	bt=NULL;
	for(i=0;i<n;i++)
		BSTInsert(bt,key[i]);
}

• Delete keywords
  Three situations ：1. Deletion degree is 0 The node of , Delete directly
                    2. Deletion degree is 1 The node of , Delete the node , Then the left subtree （ Right subtree ） Connected to the parent node where the node is deleted
                    3. Deletion degree is 2 The node of , Take a step on the left , Go straight to the right . Or Take a step to the right , Go straight to the left