二叉排序树.doc

1. 实验内容：二叉排序树。
任意给定一组数据， 设计一个算法， 建立一棵二叉排序树， 对它进行查找、 插入、删除等操作。
2. 实验说明： 二叉排序树存储结构如下：
typedef struct BiTNode
{
　　　// 结点结构 struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;
3. 程序代码
#define ok 1
#define error 0
#define STACK_INIT_SIZE 100
#define OVERFLOW -1
#define STACKCRE 10
#include<stdio.h>
#include<stdlib.h>
typedef int Status;
typedef struct BiTNode{
int data;
struct BiTNode * lchild,* rchild;
}BiTNode,* BiTree;
Status Search(BiTree T,int key,BiTree f,BiTree &p)
{
if(!T)
{
p=f;
return NULL;
}
else if(key==T->data)
{
p=T;
return ok;
}
else if(key<T->data)
return Search(T->lchild,key,T,p);
else return Search(T->rchild,key,T,p);
}

Status Insert(BiTree &T,int e)
{
BiTree p,s;
if(!Search(T,e,NULL,p))
{
s=(BiTree)malloc(sizeof(BiTNode));
s->data=e;
s->lchild=NULL;
s->rchild=NULL;
if(!p)T=s;
else if(e<p->data)p->lchild=s;
else p->rchild=s;
return ok;
}
else return false;
}

Status CreateBiTree(BiTree &T,int n)
{
int i;
T=NULL;
printf("建立二叉排序树且节点关键字： \n");
for(i=0;i<n;i++)
{
int key;
scanf("%d",&key);
Insert(T,key);
}
return ok;
}

Status Delete(BiTree &p)
{
BiTree q,s;
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;
if(q!=p)
q->rchild=s->lchild;
else
q->lchild=s->lchild;
delete s;
}
return ok;
}

Status DeleteBST(BiTree &T,int key)
{
if(!T)return false;
else {
if(key==T->data)return Delete(T);
else if(key<T->data)return DeleteBST(T->lchild,key);
else return DeleteBST(T->rchild,key);
}
}
Status PreOrder(BiTree T)
{
if(T!=NULL){
printf("%d ",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
return ok;
}

bool InsertBST(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=NULL;
if(!p)
T=s;
else if(key<p->data)
p->lchild=s;
else
p->rchild=s;
return ok;
}
else
return error;
}

int main()
{
BiTree C,p;
int N,Key;
printf("创建N个节点的排序二叉树：\n");
scanf("%d",&N);
CreateBiTree(C,N);
loop :int num;
printf("**************** 1.插入节点 ****************\n");
printf("**************** 2.删除节点 ****************\n");
printf("**************** 3.查找节点 ****************\n");
printf("**************** 4.输出二叉树 ****************\n");
printf("**************** 5.退出 ****************\n");
scanf("%d",&num);
switch(num)
{
case 1:
printf("请输入要插入的节点:");
scanf("%d",&Key);
if(InsertBST(C,Key))
{ printf("插入成功\n");
printf("先序输出\n");
PreOrder(C);
printf("\n");
}
else
printf("插入失败\n");
break;
case 2:
printf("请输入删除的节点:");
scanf("%d",&Key);
if(DeleteBST(C,Key))
{
printf("删除成功\n");
if(C!=NULL)
printf("先序输出\n");
else
{
printf("二叉树为空");
printf("\n");
}
}
else
printf("删除失败\n");
PreOrder(C);
printf("\n");
break;
case 3:
printf("请输入查找的节点:");
scanf("%d",&Key);
if(Search(C,Key,NULL,p))
printf("查找成功！\n");
else
printf("查找失败！\n");
break;
case 4:
PreOrder(C);
printf("\n");
break;
case 5:
exit(1);
break;
}
printf("继续选择操作!\n");
goto loop;
return ok;
}
4. 实验总结：
通过这次的实验，我认识到：仅仅掌握课本上的知识是不够的，在实际操作时， 常常遇到一些问题，自己看不懂，更无法解决。不过，经过自己不断的思考，尝 试着去更改代码中出现的问题。虽然开始很困难，但在老师和同学的帮助下，我 逐渐的熟悉了许多操作，为后继工作的顺利进行做了准备。 个人的力量是薄弱的，我学会了咨询别人，不再胆怯，不再保守。 在过程 中和同学相互讨论，询问老师，不断进步。 也许，我们可以说，编一个程仅仅是开始，调试和运行相比之下更难。实践 中收获的远比想象的多。 看到自己完成了所要求的任务，有一种无法用言语来形容的欣慰之感，这也 是无法从学习书本知识中得到的。