二叉排序树是一种动态树表，其特点是，树的结构通常不是一资生成的，面是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p){
if(!T) {p=f;return FALSE;}
else if EQ(key,T->data.key){ p=T;return TRUE;}
else if LT(key,T->data.key) SearchBsT(T->lchild,key,T,p);
else SearchBST(T->rchild,key,T,p);
}//SearchBST
插入算法：
Status InsertBST(BiTree &T,ElemType e){
if(!SearchBST(T,e.key,NULL,p){
s=(BiTree)malloc(sizeof(BiTNode));
s->data=e;s->lchild=s->rchild=NULL;
if(!p) T=s;
else if (LT(e.key,p->data.key) p->lchild=s;
else p->rchild=s;
return TRUE;
}
else return FALSE;
}//InsertBST
在二叉排序树中删除一个节点的算法：
Status DeleteBST(BiTree &T,KeyType key){
if(!T) return FALSE;
else{
if EQ(key,T->data.key) Delete(T);
else if LT(key,T->data.key) DeleteBST(T->lchild,key);
else DeleteBST(T->rchild,key);
return TRUE;
}
}
void Delete(BiTree &p){
if(!p->rchild){
q=p; p=p->lchild; free(q);
}
else if(!p->lchild){
q=p;p=p->rchild; free(q);
}
else{
//方法一：如图示
q=p;s=p->lchild;
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的左子树 （方法一结束）
//或可用方法二：
//q=s=(*p)->l;
//while(s->r) s=s->r;
//s->r=(*p)->r;
//free(*p);
//(*p)=q;
}
}
请看一个示例源程序。
#include <alloc.h>
#define ERROR 0;
#define FALSE 0;
#define TRUE 1;
#define OK 1;
typedef int ElemType;
typedef int Status;
typedef int KeyType;
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))
typedef struct BinaryTree
{
ElemType data;
struct BinaryTree *l;
struct BinaryTree *r;
}*BiTree,BiNode;
BiNode * new()
{
return( (BiNode *)malloc(sizeof(BiNode)) );
}
CreateSubTree(BiTree *T,ElemType *all,int i)
{
if ((all[i]==0)||i>16)
{
*T=NULL;
return OK;
}
*T=new();
if(*T==NULL) return ERROR;
(*T)->data=all[i];
CreateSubTree(&((*T)->l),all,2*i);
CreateSubTree(&((*T)->r),all,2*i 1);
}
CreateBiTree(BiTree *T)
{
ElemType all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};
CreateSubTree(T,all,1);
}
printelem(ElemType d)
{
printf("%d\n",d);
}
PreOrderTraverse(BiTree T,int (*Visit)(ElemType d))
{
if(T){
if(Visit(T->data))
if(PreOrderTraverse(T->l,Visit))
if(PreOrderTraverse(T->r,Visit)) return OK;
return ERROR;
} else return OK;
}
InOrderTraverse(BiTree T,int (*Visit)(ElemType d))
{
if(T){
if(InOrderTraverse(T->l,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->r,Visit)) return OK;
return ERROR;
}else return OK;
}
Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){
if(!T) {*p=f;return FALSE;}
else if EQ(key,T->data){ *p=T;return TRUE;}
else if LT(key,T->data) SearchBST(T->l,key,T,p);
else SearchBST(T->r,key,T,p);
}
Status InsertBST(BiTree *T,ElemType e){
BiTree p;
BiTree s;
if(!SearchBST(*T,e,NULL,&p)){
s=(BiTree)malloc(sizeof(BiNode));
s->data=e;s->l=s->r=NULL;
if(!p) *T=s;
else if (LT(e,p->data)) p->l=s;
else p->r=s;
return TRUE;
}
else return FALSE;
}
void Delete(BiTree *p){
BiTree q,s;
if(!(*p)->r){
q=(*p);
(*p)=(*p)->l;
free(q);
}
else if(!(*p)->l){
q=(*p);
(*p)=(*p)->r;
free(q);
}
else {
/* q=(*p);
s=(*p)->l;
while(s->r) {q=s; s=s->r;}
(*p)->data=s->data;
if(q!=(*p) ) q->r=s->l;
else q->l=s->l;
free(s);
*/
q=s=(*p)->l;
while(s->r) s=s->r;
s->r=(*p)->r;
free(*p);
(*p)=q;
}
}
Status DeleteBST(BiTree *T,KeyType key){
if (!(*T) )
{return FALSE;}
else{
if ( EQ(key,(*T)->data)) Delete(T);
else if ( LT(key,(*T)->data)) DeleteBST( &((*T)->l), key);
else DeleteBST( &((*T)->r),key);
return TRUE;
}
}
main()
{
BiTree root;
BiTree sroot=NULL;
int i;
int a[10]={45,23,12,3,33, 27,56,90,120,62};
system("cls");
CreateBiTree(&root);
printf("PreOrderTraverse:\n");
PreOrderTraverse(root,printelem);
printf("InOrderTraverse:\n");
InOrderTraverse(root,printelem);
for(i=0;i<10;i )
InsertBST(&sroot,a[i]);
printf("InOrderTraverse:\n");
InOrderTraverse(sroot,printelem);
for(i=0;i<3;i )
DeleteBST(&sroot,a[i]);
printf("Now sroot has nodes:\n");
InOrderTraverse(sroot,printelem);
}
