二叉排序树【BST】——创建、查找、删除、输出

1、结点值大小

        左子树结点值 <= 根结点值 <= 右子树值

2、进行中序遍历可以得到一个递增的有序序列

3、查找

        若树非空，目标值与根结点的值比较：

                ①若相等，则查找成功；

                ②若小于根结点，则在左子树上查找，否则在右子树上找；

        查找成功返回结点指针，失败返回NULL

4、新插入的结点一定是叶子结点

5、叶子结点可直接删除

6、删除结点——A

        ①若A只有一颗子树，则让A的子树成为A父结点的子树，代替A

        ②若A有两个子树，则令A的直接后继（前驱）代替A，然后从树中删掉这个结点

【注】A的前驱：A的左子树最右下结点；

           A的后继：A的右子树最左下结点

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

//二叉排序树的基本运算算法

typedef int KeyType;
typedef char InfoType;
typedef struct node{
	KeyType key;		//关键字
	InfoType data;		//其他数据域
	struct node *lchild,*rchild;	//左右孩子指针 
}BSTNode;

void DispBST(BSTNode *b);		//函数声明

//在以bt为根结点的BST中插入一个关键字为K的结点
bool InsertBST(BSTNode *&bt,KeyType k){
	if(bt == NULL){		//原树为空，新插入的记录为根结点
		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);	//插入bt的左子树中
	else 
		return  InsertBST(bt->rchild,k);	//插入bt的右子树中
} 

//由数组B中的关键字建立一颗二叉排序树
BSTNode *CreateBST(KeyType B[],int n){
	BSTNode *bt=NULL;		//初始时bt为空数
	int i=0;
	while(i<n)
		if(InsertBST(bt,B[i]) == 1)	{		//将B[i]插入二叉排序树T中 
			printf("  第%d步，插入%d：",i+1,B[i]);
			DispBST(bt);
			printf("\n");
			i++;
		}
	return bt;		//返回建立的二叉树的跟指针 
} 

//删除结点p[有左、右孩子，r指向其左孩子]
void Deletel(BSTNode *p,BSTNode *&r){
	BSTNode *q;
	if(r->rchild != NULL)		//递归找结点r的最右下结点
		Deletel(p,r->rchild);
	else{		//找到了最右下结点
		p->key=r->key;		//将结点r的值存放到结点p中（结点值代替）
		p->data=r->data;
		q=r;			//删除结点r
		r=r->lchild;	//用结点r的左孩子代替r
		free(q);		//释放结点r的空间 
		
	} 
} 

//从二叉排序树中删除p结点
void Delete(BSTNode *&p){
	BSTNode *q;
	if(p->rchild == NULL){		//p结点没有右子树[也包括叶子结点] 
		q=p;p=p->lchild;free(q); 
	}
	else if(p->lchild == NULL){		//p结点没有左子树 
		q=p;p=p->rchild;free(q);
	}
	else Deletel(p,p->lchild);		//p既有左子树又有右子树 
} 


//在bt中删除关键字为K的结点
bool DeleteBST(BSTNode *&bt,KeyType k){
	if(bt==NULL)	return false;	//空树删除失败
	else{
		if(k<bt->key)
			return DeleteBST(bt->lchild,k);		//递归在左子树中删除关键字为k的结点
		else if(k>bt->key)
			return DeleteBST(bt->rchild,k);		//递归在右子树中删除关键字为k的结点
		else{
			Delete(bt);			//删除bt结点 
			return true;
		} 
	} 
} 

//以非递归方式输出从根结点到查找到的结点的路径
void SearchBST1(BSTNode *bt,KeyType k,KeyType path[],int i){
	int j;
	if(bt==NULL)	return;
	else if(k==bt->key){	//找到关键字为k的结点
		path[i+1]=bt->key ;		//输出其路径
		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);	//在左子树中递归查找
		else
			SearchBST1(bt->rchild,k,path,i+1);	//在右子树中递归查找 
	}
} 
 
//以递归方式输出从根结点到查找到的结点的路径
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);	//在左子树中递归查找
	else
		SearchBST2(bt->rchild,k);	//在右子树中递归查找 
		
	printf("%3d",bt->key);
} 
 
//以括号表示法输出二叉排序树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;	//全局变量，保存当前结点中序前驱的值
 
//判断bt是否为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;
	}
} 
 
//销毁一棵树
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)创建一颗BST数：");
	printf("\n");
	bt=CreateBST(a,n);
	printf("(2)BST：");DispBST(bt);printf("\n");
	printf("(3)bt%s\n",(JudgeBST(bt)?"是一颗BST":"不是一颗BST"));
	printf("(4)查找%d关键字（非递归，逆序）：",k);SearchBST1(bt,k,path,-1);
	printf("(5)查找%d关键字（递归，顺序）：",k);SearchBST2(bt,k);
	printf("\n(6)删除操作：\n");
	printf("	原BST：");DispBST(bt);printf("\n");
	printf("	删除结点4：");
	DeleteBST(bt,4);DispBST(bt);printf("\n");
	printf("	删除结点5：");
	DeleteBST(bt,5);DispBST(bt);printf("\n");
	printf("(7)销毁BST\n");DestroyBST(bt);
	return 1;

}