本文共 1593 字，大约阅读时间需要 5 分钟。

二叉排序树，又称二叉查找树。它或是一颗空树，或者是具有以下性质的二叉树。

1. 若它的左子树不空，则左子树上所有节点的值均小于它的根结构值；
2. 若它的右子树不空，则右子树上所有节点的值均小于它的根结构值；
3. 它的左右子树分别为二叉排序树。

#include
   
    typedef struct BiTNode{	int data;	struct BiTNode *lchild,*rchild;	}BiTNode,*BiTree;//递归查找二叉排序树T中是否存在key//指针f指向T的双亲，其初始值为NULL//若查找成功，则指针p指向该数据元素节点，并返回RTUE//否则指针p指向查找路径上访问的最后一个节点并返回FALSEint Search(BiTree T,int key,BiTree f,BiTree *p){	if(!T)	{		*p = f;		return -1;	}	else if(T->data == key)	{ 		*p = T;		return 0;	}	else if(T->data > key)	{		return Search(T->lchild,key,T,p);	}	else	{		return Search(T->rchild,key,T,p);	}}int Insert(BiTree *T,int key){	BiTree p,s;	if(!Search(*T,key,NULL,&p))	{		s = (BiTree)malloc(sizeof(BiTNode));		s->data = key;		s->lchild = s->rchild = key;				if(!p)			*T =s; //insert new root node		else if (key < p->data)			p->lchild = s;		else 			p->rchild = s;	}	else	 return -1;}int Delete(BiTree *p){	BiTree q,s;	if((*p)->rchild ==  NULL)/*右子树为空则只需重接它的左子树*/		{		q = *p;		*p = *p->lchild;		free(q);	}	else if((*p)->lchild == NULL)/*重接右子树*/	{		q = *p;		*p = *p->rchild;		free(q);	}	else/*左右子树都不为空*/	{		q = *p;		s = (*p)->rchild;		while(s->rchild)/*转左，然后向右找到尽头（待删除节点的前驱）*/		{			q=s;			s = s->rchild;		}		(*p)->data = s->data;/*s指向被删除节点的直接前驱*/			if(q != *(p))			q->rchild = s->lchild;/*重接q的右子树*/		else			q->lchild = s->lchild;/*重接q的左子树*/		free(s);			}	return 1;}/* 删除分为三种情况分析1,叶子节点2,仅有左或者右子树的节点3,左右子树都有的节点我们用递归的方法查找key */int DeleteBST(BiTree *T,int key){	if(!*T)			return -1;	else	{		if(key == (*T)->data)			return Delete(T);		else if(key<(*T)->data)			return DeleteBST(&(*T)->lchild,key);		else			return DeleteBST(&(*T)->rchild,key);				}}