Binary sort tree [BST] - create, find, delete, output

1、 Node value size

        Left subtree node value <= Root value <= Right subtree value

2、 An increasing ordered sequence can be obtained by traversing the middle order

3、 lookup

        If the tree is not empty , Compare the target value with the value of the root node ：

                ① If equal , Then the search is successful ;

                ② If less than the root node , Then find... In the left subtree , Otherwise, look on the right subtree ;

        The node pointer returned after successful search , Failure to return NULL

4、 The newly inserted node must be a leaf node

5、 Leaf nodes can be deleted directly

6、 Delete node ——A

        ① if A There is only one subtree , Then let A The subtree becomes A The subtree of the parent node , Instead of A

        ② if A There are two subtrees , Then order A Immediate successor （ Forerunner ） Instead of A, Then delete this node from the tree

【 notes 】A The precursor of ：A The rightmost lower node of the left subtree of ;

           A In the subsequent ：A The leftmost lower node of the right subtree of

#include<stdio.h>
#include<malloc.h>
#define MaxSize 100

// The basic operation algorithm of binary sort tree 

typedef int KeyType;
typedef char InfoType;
typedef struct node{
	KeyType key;		// keyword 
	InfoType data;		// Other data fields 
	struct node *lchild,*rchild;	// Left and right child pointer  
}BSTNode;

void DispBST(BSTNode *b);		// Function declaration 

// In order to bt For the root node BST Insert a keyword for K The node of 
bool InsertBST(BSTNode *&bt,KeyType k){
	if(bt == NULL){		// The original tree is empty , The newly inserted record is the root node 
		bt=(BSTNode *)malloc(sizeof(BSTNode));
		bt->key=k;
		bt->lchild=bt->rchild=NULL;
		return true;
	}
	else if(k==bt->key)
		return false;
	else if(k<bt->key)
		return InsertBST(bt->lchild,k);	// Insert bt In the left subtree 
	else 
		return  InsertBST(bt->rchild,k);	// Insert bt In the right subtree 
} 

// By an array of B Create a binary sort tree with keywords in 
BSTNode *CreateBST(KeyType B[],int n){
	BSTNode *bt=NULL;		// At the beginning bt Empty number 
	int i=0;
	while(i<n)
		if(InsertBST(bt,B[i]) == 1)	{		// take B[i] Insert a binary sort tree T in  
			printf("   The first %d Step , Insert %d：",i+1,B[i]);
			DispBST(bt);
			printf("\n");
			i++;
		}
	return bt;		// Return the following pointer of the established binary tree  
} 

// Delete node p[ There is left 、 The right child ,r Point to its left child ]
void Deletel(BSTNode *p,BSTNode *&r){
	BSTNode *q;
	if(r->rchild != NULL)		// Recursively find nodes r The bottom right node of 
		Deletel(p,r->rchild);
	else{		// Found the bottom right node 
		p->key=r->key;		// The node r The value of is stored in the node p in （ Node values replace ）
		p->data=r->data;
		q=r;			// Delete node r
		r=r->lchild;	// Use node r Left child instead of r
		free(q);		// Release nodes r Space  
		
	} 
} 

// Delete... From the binary sort tree p node 
void Delete(BSTNode *&p){
	BSTNode *q;
	if(p->rchild == NULL){		//p The node has no right subtree [ It also includes leaf nodes ] 
		q=p;p=p->lchild;free(q); 
	}
	else if(p->lchild == NULL){		//p Node has no left subtree  
		q=p;p=p->rchild;free(q);
	}
	else Deletel(p,p->lchild);		//p There are both left and right subtrees  
} 


// stay bt The keyword deleted in is K The node of 
bool DeleteBST(BSTNode *&bt,KeyType k){
	if(bt==NULL)	return false;	// Empty tree deletion failed 
	else{
		if(k<bt->key)
			return DeleteBST(bt->lchild,k);		// Recursively delete the keyword in the left subtree as k The node of 
		else if(k>bt->key)
			return DeleteBST(bt->rchild,k);		// Recursively delete the keyword in the right subtree as k The node of 
		else{
			Delete(bt);			// Delete bt node  
			return true;
		} 
	} 
} 

// Output the path from the root node to the found node in a non recursive way 
void SearchBST1(BSTNode *bt,KeyType k,KeyType path[],int i){
	int j;
	if(bt==NULL)	return;
	else if(k==bt->key){	// Find the keyword for k The node of 
		path[i+1]=bt->key ;		// Output its path 
		for(j=0;j<=i+1;j++)
			printf("%3d",path[j]);
		printf("\n"); 
	}else{
		path[i+1]=bt->key;
		if(k<bt->key)
			SearchBST1(bt->lchild,k,path,i+1);	// Recursively find... In the left subtree 
		else
			SearchBST1(bt->rchild,k,path,i+1);	// Recursively find... In the right subtree  
	}
} 
 
// Recursively output the path from the root node to the found node 
int SearchBST2(BSTNode *bt,KeyType k){
	if(bt==NULL)	return 0;
	else if(k==bt->key){
		printf("%3d",bt->key);
		return 1;
	}else if(k<bt->key)
		SearchBST2(bt->lchild,k);	// Recursively find... In the left subtree 
	else
		SearchBST2(bt->rchild,k);	// Recursively find... In the right subtree  
		
	printf("%3d",bt->key);
} 
 
// Output binary sort tree in parenthesis bt
void DispBST(BSTNode *bt){
	if(bt!=NULL){
		printf("%d",bt->key);
		if(bt->lchild != NULL || bt->rchild != NULL){
			printf("(");
			DispBST(bt->lchild);
			if(bt->rchild != NULL) printf(",");
			DispBST(bt->rchild);
			printf(")");
		}
	}
} 
 
KeyType predt=-32767;	// Global variables , Save the value of the sequence precursor in the current node 
 
// Judge bt Is it BST
bool JudgeBST(BSTNode *bt){
	bool b1,b2;
	if(bt == NULL)	return true;
	else{
		b1=JudgeBST(bt->lchild);
		if(b1==false || predt>=bt->key)
			return false;
		predt = bt->key;
		b2=JudgeBST(bt->rchild);
		return b2;
	}
} 
 
// Destroy a tree 
void DestroyBST(BSTNode *bt){
	if(bt != NULL){
		DestroyBST(bt->lchild);
		DestroyBST(bt->rchild);
		free(bt);
	}
} 


int main(){
	BSTNode *bt;
	int path[MaxSize];
	KeyType k=6;
	int a[]={4,9,0,1,8,6,3,5,2,7},n=10;
	printf("(1) Create a BST Count ：");
	printf("\n");
	bt=CreateBST(a,n);
	printf("(2)BST：");DispBST(bt);printf("\n");
	printf("(3)bt%s\n",(JudgeBST(bt)?" Is a BST":" Not a BST"));
	printf("(4) lookup %d keyword （ Non recursive , The reverse ）：",k);SearchBST1(bt,k,path,-1);
	printf("(5) lookup %d keyword （ recursive , The order ）：",k);SearchBST2(bt,k);
	printf("\n(6) Delete operation ：\n");
	printf("	 primary BST：");DispBST(bt);printf("\n");
	printf("	 Delete node 4：");
	DeleteBST(bt,4);DispBST(bt);printf("\n");
	printf("	 Delete node 5：");
	DeleteBST(bt,5);DispBST(bt);printf("\n");
	printf("(7) The destruction BST\n");DestroyBST(bt);
	return 1;

}