数据结构-二叉排序树（建立、查找、修改）_数据结构二叉排序树创建

二叉排序树概念

二叉排序树是动态查找表的一种，也是常用的表示方法。

其中，它具有如下性质：

1.若它的左子树非空，则其左子树的所有节点的关键值都小于根节点的关键值。

2.若它的右子树非空，则其右子树的所有节点的关键值都大于根结点的关键值。

3.它的左右子树也分别都是二叉排序树。

PS：对二叉排序树进行中序遍历，得到的序列，总会是一个升序的数列。

二叉排序树的建立

我们使用C语言来建立。

其中我们对二叉排序树的结构体定义如下：

typedef int ElemType;
typedef struct BTNode{
    ElemType key;
    struct BTNode *lchild,*rchild;
}BTNode,*BSTree;

建立二叉排序树的代码如下：

BSTree InsertBST(BSTree bst,BSTree s)		//遍历二叉排序树,找到合适的位置 
{
	if(bst==NULL)
		bst = s;
	else{
		if(s->key < bst->key)
			bst->lchild = InsertBST(bst->lchild,s);
		if(s->key > bst->key){
			bst->rchild = InsertBST(bst->rchild,s);
		}
	}
	return bst;
}
 
BSTree CreateBST()		//建立二叉排序树 
{
	BSTree bst,s;
	int key;
	bst = NULL;
	printf("请输入关键字值,输入-1结束.\n");
	while(1){
		scanf("%d",&key);
		if(key!=-1){
			s = (BSTree)malloc(sizeof(BTNode));
			s->key = key;
			s->lchild = NULL;
			s->rchild = NULL;
			bst = InsertBST(bst,s);
			printf("成功.\n");
		}
		else
			break;
	}
	return bst;
}

二叉排序树的插入

BSTree InsertBST(BSTree bst,BSTree s)		//遍历二叉排序树,找到合适的位置 
{
	if(bst==NULL)
		bst = s;
	else{
		if(s->key < bst->key)
			bst->lchild = InsertBST(bst->lchild,s);
		if(s->key > bst->key){
			bst->rchild = InsertBST(bst->rchild,s);
		}
	}
	return bst;
}
 
BSTree SearchBST(BSTree bst,int key)		//查找关键值key的节点,并且返回这个节点 
{
	if(bst == NULL)
		return NULL;
	else if(key == bst->key)
		return bst;
	else if(key > bst->key)
		return SearchBST(bst->rchild,key);
	else
		return SearchBST(bst->lchild,key);
}
 
BSTree InsertBST_key(BSTree bst,int key)		//搜寻一个关键值,如果没有就插入 
{
	BSTree s;
	s = SearchBST(bst,key);
	if(s)
		printf("该节点已经存在.");
	else{
		s = (BSTree)malloc(sizeof(BTNode));
		s->key = key;
		s->lchild = NULL;
		s->rchild = NULL;
		s = InsertBST(bst,s);
	}
	return s;
}

查找二叉排序树指定节点的双亲

BSTree SearchBST_F(BSTree bst,int key,BSTree *F)		//F存储key关键值节点的双亲节点,函数返回key关键值节点. 
{
	if(bst == NULL)
		return NULL;
	if(key == bst->key)
		return bst;
	else{
		*F = bst;
		if(key < bst->key)
			return SearchBST_F(bst->lchild,key,F);
		else
			return SearchBST_F(bst->rchild,key,F);
	}
}

 删除二叉排序树中某个节点：

对于删除二叉排序树的节点，我们有必要花大功夫来讨论一下。

对于删除二叉排序树的某个节点，大致有以下四种情况：

假设我们要删除的节点指定为P。

1.P节点的左右子树都为空

此时删除P节点，只需要P节点的父节点的左/右子树赋值NULL，并且free掉P节点即可。

值得注意的是，还有一种特殊情况，那就是P节点本身就是根节点，也就是这个树只有P节点一个

节点。

那么此时，我们只需要返回NULL，并且free掉P节点即可。

2.P节点的左子树为空

在这种情况下，我们注意到P的右子树不是空的，如下图所示：

此时我们只需要令P节点的父节点C的右子树/左子树为P的右子树即可。

不过值得注意的是，此时仍有可能P是根节点，此时我们需要令根节点 = p的右子树，并且free掉p

节点即可。

3.P节点的右子树为空

此时我们注意到，这种情况根情况2（P节点的左子树为空）非常相似。

此时我们只需要令P的父节点C的左/右子树等于P的左子树即可。

不过此时P节点仍有可能作为根节点出现，此时我们只需要令根节点等于P的左子树即可。

4.P节点的左右子树都不为空

这种情况无疑是最复杂的一种情况，因为此时我们要牵扯一个大小的排序。

因此，我们可以令P节点的Key值等于P节点的直接前驱(直接后驱)的Key值，之后删掉直接前驱(直

接后驱)即可。

注意到此时的P节点的直接前驱是G（即P节点的左子树的最右侧的一个节点）。

那么此时我们可以令P节点的Key值等于G节点的Key值，同时free掉G节点即可完成操作。

不过，比较重要的一点是，G节点的左子树不一定为空，此时我们仍需要让G节点的父节点的右子

树等于G节点的左子树。

注意到，当P节点作为根结点的时候并不会出现特殊的情况，但是当P节点的前驱节点就是P的左子

树，我们需要另外的讨论，如下图所示：

注意到此时P的直接前驱节点就是D，但是如果我们直接删除D，那么D的左子树此时应该给P的左

子树。

注意到P也是D的一个父节点，P同时还是D的一个直接后继节点，此时就是一种特殊情况，需要让

P的左子树等于D的左子树，而不是D的父节点的右子树等于D的左子树！！！

代码实现：

BSTree SearchBST_F(BSTree bst,int key,BSTree *F)	//查找Key值节点的父节点,*F存储父节点,函数返回Key节点 
{
	if(bst == NULL)
		return NULL;
	if(bst->key == key)
		return bst;
	else{
		*F = bst;
		if(bst->key > key)
			return SearchBST_F(bst->lchild,key,F);
		else
			return SearchBST_F(bst->rchild,key,F);
	}
}
 
BSTree DeleteBST(BSTree bst,BSTree p,BSTree f)
{
	BSTree par,s;
	int kind;
	if(!p->lchild && !p->rchild)	//左右子树全为空 
		kind = 1;
	else if(!p->lchild)			//左子树为空 
		kind = 2;
	else if(!p->rchild)			//右子树为空 
		kind = 3;
	else			//左右子树都不为空 
		kind = 4;
	switch(kind){
		case 1:
			if(!f)			//没有父节点，p是根节点, 
				return NULL;
			else{
				if(f->lchild == p)
					f->lchild = NULL;
				else
					f->rchild = NULL;
				free(p);
			}
			break;
		case 2:
			if(!f)			//p是根节点
				bst = bst->rchild;
			else{
				if(p == f->lchild)
					f->lchild = p->rchild;
				else
					f->rchild = p->rchild;
				free(p);
			}
			break;
		case 3:
			if(!f)			//p是根节点 
				bst = bst->lchild;
			else{
				if(p == f->lchild)
					f->lchild = bst->lchild;
				else
					f->rchild = bst->lchild;
			}
			free(p);
			break;
		case 4:
			par = p;		//p节点前驱指针par 
			s = p->lchild;		//用来遍历p的直接前驱节点(左子树的最右侧) 
			while(s->rchild != NULL){		//结束条件是s的右子树为空,此时s就是p的直接前驱节点 
				par = s;
				s = s->rchild;
			}
			p->key = s->key;		//令p节点的值为s节点的值 
			if(par == p)		//特殊情况,s节点刚好是p的左子树 
				par->lchild = s->lchild;
			else
				par->rchild = s->lchild;		//par的右子树需要等于s节点的左子树 
			free(s);		//释放p节点的直接前驱s 
			break;
	}	
	return bst;
}
 
BSTree SearchDeleteBST(BSTree bst,int key)
{
	BSTree f = NULL,p;
	p = SearchBST_F(bst,key,&f);
	if(p){
		bst = DeleteBST(bst,p,f);
	}
	else
		printf("该节点不存在.\n");
	return bst;
} 

二叉排序树的所有代码汇总： 

#include<stdio.h>
#include<malloc.h>
typedef int ElemType;
typedef struct BSNode{
	ElemType key;
	struct BSNode *lchild,*rchild;
}BSNode,*BSTree;
 
BSTree SearchBST(BSTree bst,BSTree s)
{
	if(bst == NULL)
		bst = s;
	else{
		if(bst->key > s->key)
			bst->lchild = SearchBST(bst->lchild,s);
		if(bst->key < s->key)
			bst->rchild = SearchBST(bst->rchild,s);
	}
	return bst;
}
 
BSTree CreateBSTree()
{
	int key;
	BSTree bst = NULL;
	printf("请输入节点关键值,输入-1结束.\n");
	while(1){
		scanf("%d",&key);
		if(key != -1){
			BSTree s = (BSTree)malloc(sizeof(BSNode));
			s->key = key;
			s->lchild = NULL;
			s->rchild = NULL;
			bst = SearchBST(bst,s);
			printf("创建节点成功.\n");
		}
		else
			break;
		
	}
	return bst;
}
 
void PostTraverse(BSTree bst)
{
	if(bst){
		PostTraverse(bst->lchild);
		printf("%d ",bst->key);
		PostTraverse(bst->rchild);
	}
}
 
BSTree SearchBST_F(BSTree bst,int key,BSTree *F)	//查找Key值节点的父节点,*F存储父节点,函数返回Key节点 
{
	if(bst == NULL)
		return NULL;
	if(bst->key == key)
		return bst;
	else{
		*F = bst;
		if(bst->key > key)
			return SearchBST_F(bst->lchild,key,F);
		else
			return SearchBST_F(bst->rchild,key,F);
	}
}
 
BSTree DeleteBST(BSTree bst,BSTree p,BSTree f)
{
	BSTree par,s;
	int kind;
	if(!p->lchild && !p->rchild)	//左右子树全为空 
		kind = 1;
	else if(!p->lchild)			//左子树为空 
		kind = 2;
	else if(!p->rchild)			//右子树为空 
		kind = 3;
	else			//左右子树都不为空 
		kind = 4;
	switch(kind){
		case 1:
			if(!f)			//没有父节点，p是根节点, 
				return NULL;
			else{
				if(f->lchild == p)
					f->lchild = NULL;
				else
					f->rchild = NULL;
				free(p);
			}
			break;
		case 2:
			if(!f)			//p是根节点
				bst = bst->rchild;
			else{
				if(p == f->lchild)
					f->lchild = p->rchild;
				else
					f->rchild = p->rchild;
				free(p);
			}
			break;
		case 3:
			if(!f)			//p是根节点 
				bst = bst->lchild;
			else{
				if(p == f->lchild)
					f->lchild = bst->lchild;
				else
					f->rchild = bst->lchild;
			}
			free(p);
			break;
		case 4:
			par = p;		//p节点前驱指针par 
			s = p->lchild;		//用来遍历p的直接前驱节点(左子树的最右侧) 
			while(s->rchild != NULL){		//结束条件是s的右子树为空,此时s就是p的直接前驱节点 
				par = s;
				s = s->rchild;
			}
			p->key = s->key;		//令p节点的值为s节点的值 
			if(par == p)		//特殊情况,s节点刚好是p的左子树 
				par->lchild = s->lchild;
			else
				par->rchild = s->lchild;		//par的右子树需要等于s节点的左子树 
			free(s);		//释放p节点的直接前驱s 
			break;
	}	
	return bst;
}
 
BSTree SearchDeleteBST(BSTree bst,int key)
{
	BSTree f = NULL,p;
	p = SearchBST_F(bst,key,&f);
	if(p){
		bst = DeleteBST(bst,p,f);
	}
	else
		printf("该节点不存在.\n");
	return bst;
} 
 
int main()
{
	BSTree bst;
	bst = CreateBSTree();
	SearchDeleteBST(bst,5);
	PostTraverse(bst);
	return 0;
}