#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,*pBSTNode;
int path[MaxSize]; /*全局变量,用于存放路径*/
void DispBST(pBSTNode b); /*函数说明*/
int InsertBST(pBSTNode &p,KeyType k) /*在以*p为根结点的BST中插入一个关键字为k的结点*/
{
if (p==NULL) /*原树为空, 新插入的记录为根结点*/
{
p=(BSTNode *)malloc(sizeof(BSTNode));
p->key=k;
p->lchild=p->rchild=NULL;
return 1;
}
else if (k==p->key)
return 0;
else if (k<p->key)
return InsertBST(p->lchild,k); /*插入到*p的左子树中*/
else
return InsertBST(p->rchild,k); /*插入到*p的右子树中*/
}
pBSTNode CreatBST(KeyType A[],int n)
/*由数组A中的关键字建立一棵二叉排序树*/
{
pBSTNode bt=NULL; /*初始时bt为空树*/
int i=0;
while (i<n)
if (InsertBST(bt,A[i])==1) /*将A[i]插入二叉排序树T中*/
{
printf(" 第%d步,插入%d:",i+1,A[i]);
DispBST(bt);
printf("\n");
i++;
}
return bt; /*返回建立的二叉排序树的根指针*/
}
void Delete1(pBSTNode p,pBSTNode &r)
/*当被删*p结点有左右子树时的删除过程*/
{
pBSTNode q;
if (r->rchild!=NULL)
Delete1(p,r->rchild); /*递归找最右下结点*/
else /*找到了最右下结点*r*/
{
p->key=r->key; /*将*r的关键字值赋给*p*/
q=r;
r=r->lchild; /*将*r的双亲结点的右孩子结点改为*r的左孩子结点*/
free(q); /*释放原*r的空间*/
}
}
void Delete(pBSTNode &p)
/*从二叉排序树中删除*p结点*/
{
pBSTNode 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 Delete1(p,p->lchild); /**p结点既有左子树又有右子树的情况*/
}
int DeleteBST(pBSTNode &bt,KeyType k)
/*在bt中删除关键字为k的结点*/
{
if (bt==NULL)
return 0; /*空树删除失败*/
else
{
if (k<bt->key)
return DeleteBST(bt->lchild,k); /*递归在左子树中删除关键字为k的结点*/
else if (k>bt->key)
return DeleteBST(bt->rchild,k); /*递归在右子树中删除关键字为k的结点*/
else /*k=bt->key的情况*/
{
Delete(bt); /*调用Delete(bt)函数删除*bt结点*/
return 1;
}
}
}
void SearchBST1(pBSTNode bt,KeyType k,KeyType path[],int i)
/*以非递归方式输出从根结点到查找到的结点的路径*/
{
int j;
if (bt==NULL)
return;
else if (k==bt->key) /*找到了结点*/
{
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(pBSTNode 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);
return -1;
}
void DispBST(pBSTNode bt)
/*以括号表示法输出二叉排序树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; /*predt为全局变量,保存当前结点中序前趋的值,初值为-∞*/
int JudgeBST(pBSTNode bt) /*判断bt是否为BST*/
{
int b1,b2;
if (bt==NULL)
return 1;
else
{
b1=JudgeBST(bt->lchild);
if (b1==0 || predt>=bt->key)
return 0;
predt=bt->key;
b2=JudgeBST(bt->rchild);
return b2;
}
}
void main()
{
pBSTNode bt;
KeyType k=6;
int a[]={4,9,0,1,8,6,3,5,2,7},n=10;
printf(" 创建一棵BST树:");
printf("\n");
bt=CreatBST(a,n);
printf(" BST:");
DispBST(bt);
printf("\n");
printf(" bt%s\n",(JudgeBST(bt)?"是一棵BST":"不是一棵BST"));
printf("\n");
printf(" 查找%d关键字(递归):",k);
SearchBST1(bt,k,path,-1);
printf(" 查找%d关键字(非递归):",k);
SearchBST2(bt,k);
printf("\n 删除操作:\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\n");
}
