数据结构二叉排序树优秀课程设计优质报告.doc

课 程 设 计 报 告
——数据结构

题目：二叉排序树

姓 名：
学 号：
专 业：
班 级：
指导老师：

年 月 日

目 录
一、课程设计介绍 3
二、原理分析及步骤 3
2.1、原理分析............................................................................3
2.2、步骤图................................................................................4
1、main()函数....................................................................4
2、创建...............................................................................4
3、插入...............................................................................5
4、查找...............................................................................6
5、中序遍历输出 7
三、算法描述 8
3.1、存放结构 8
3.2、插入算法 8
3.3、查找算法 9
3.4、删除算法 10
四、小结和体会 12
五、程序实施过程 13
5.1、创建二叉排序树并中序输出.........................................13 5.2、插入并中序输出..............................................................13
5.3、查找..................................................................................14
六、程序清单 14

一、课程设计介绍
1.1、题目：二叉排序树相关操作
1、创建二叉排序树；2、插入给定值；
3、查找给定值； 4、删除给定值结点。
1.2、汇报要求：
1、封面; 2、题目和步骤图或模块图;
3、程序清单和运行结果; 4、小结(收获和体会);
5、装订成册。
1.3、目标：
课程设计为学生提供了一个既动手又动脑，独立实践机会，将书本上理论知识和实际有机结合起来，锻炼学生分析处理实际问题能力。提升学生适应实际，实践编程能力。
二、原理分析及步骤
2.1、原理分析：
依据题目要求，要实现这些功效，就必需创建一个菜单。这个菜单设置在main（）函数里面，然后使用while()...switch()语句进行循环调用相关函数，以达成实现相关功效目标。

2.2、步骤图：
选择操作
main()开始

选择1
创建
选择2
插入
选择3
查找
选择4
删除
选择5
退出
1、main（）函数：

Create(&t)
输入结点值，以-1结束
调用插入函数
2、创建：

3、插入：
Insert(&t,x)
输入给定结点值
*t==null

x<(*t)->key

insert(&((*t)->lchild)x);
insert(&((*t)->rchild)x)
*t=s
结束

N

Y
N

Y

4、查找：
返回search(p->rchild,x)
输入给定结点值x,p=t
P!=null
x<p->key
返回search(p->lchild,x)
返回null
search(t,x)
返回p->key
x=p->key

Y

N

Y N

5、中序遍历输出：
display(t)
t!=null
display(t->lchild)
访问并输出根节点
display(t->rchild)

三、算法描述
3.1、存放结构
定义一个链表式二叉排序树，用链表方法结构结点，存放二叉排序树中结点、结点类型和指针类型以下：
#include <stdio.h>
#define null 0
typedef int keytype;
typedef struct node
{
keytype key;
struct node *lchild,*rchild;
}bstnode,*bstree;
3.2、插入算法
在二叉排序树中插入一个新节点，首先要查找该节点在二叉排序树中是否已经存在。若二叉排序树中不存在关键字等于x节点，则插入。
　　将一个关键字值为x节点s插入到二叉排序树中，能够用下面方法：
　 （1）若二叉排序树为空，则关键字为x节点s成为二叉排序树根
（2）若二叉排序树非空，则将x和二叉排序树根进行比较，假如x值等于根节点关键值，则停止插入；假如x根节点值小于根节点关键值，则将x插入左子树；假如x值大于根节点关键字值，则将x插入右子树。在左右两个子树插入方法和整个二叉排序树相同。
算法以下：
void insert(bstree *t,keytype x)
{
bstree s;
if(*t==null)
{
s=(bstree)malloc(sizeof(bstnode));
s->key=x;
s->lchild=null;
s->rchild=null;
*t=s;
}
else if(x<(*t)->key)
insert(&((*t)->lchild),x);
else if(x>(*t)->key)
insert(&((*t)->rchild),x);
}
3.3、查找算法
（1）若二叉排序树不为空，将根结点关键字和待查关键字进行比较，若相等，则查找成功；若根节点关键字大于待查值，则进入左子树反复次步骤，不然，进入右子树进行此步骤；若在查找过程中碰到二叉排序树叶子节点时，还没有找到待查节点，则查找不成功。
（2）不然，查找失败，返回null。
　　　算法以下：
bstree search(bstree t,keytype x)
{
bstree p;
p=t;
if(p!=null)
{
if (x==p->key) return p->key;
else if(x<p->key) return search(p->lchild,x);
else return search(p->rchild,x);
}
else
{ printf("%d can not be found\n",x);return null;
}
}
3.4、删除算法
　　在二叉排序树中删除节点，首先要确定被删除节点是否在二叉排序树中。
　　若不在，则不做任何操作；不然，假设要删除节点为p，节点p父节点为r，并假设p是r左孩子。依据被删除节点p有没有孩子，删除部分可做以下3中情况讨论：
　　（1）若p为叶子节点，则可令其父节点r左孩子指针域为空，直接将其删除。
　　（2）若p节点只有右子树或左子树，则能够将p左子树或右子树直接改为其双亲节点r左子树。
　　（3）若p现有左子树又有右子树；将节点s为p中序前驱。首先找到p中序前驱节点s，然后用节点s值替换节点p值，再将节点s删除，节点s原左子树改为s双亲节点q右子树。
　　算法以下：
bstree delete(bstree t,keytype x)
{
bstree p,q,r,s;
p=t;
r=null;
while(p)
{
if(x==p->key) break;
r=p;
if(x<p->key) p=p->lchild;
else p=p->rchild;
}
if(p==null) {printf("%d is not exist!\n",x);return t;}
if((p->lchild==null)||(p->rchild==null))
{
if(r==null)
if(p->lchild==null)
t=p->rchild;
else t=p->lchild;
else if(p->lchild==null)
if(r->lchild==p)
r->lchild=p->rchild;
else r->rchild=p->rchild;
else if(r->lchild==p)
r->lchild=p->lchild;
else r->lchild=p->lchild;
free(p);
}
else
{
q=p;
s->lchild;
while(s->rchild)
{q=s;s->rchild;}
if(q==p) q->lchild=s->lchild;
else p->key=s->key;
free(s);
}
return t;
}
四、小结和体会
经过一个多星期来夜以继日努力，最终把课程设计——二叉排序树相关算法全部完成！在编写程序过程中，让我对二叉排序树创建、插入、查找、删除算法有了较系统认识，也发觉了部分以前纸上谈兵时思想误区。比如实现插入功效时，从根节点开始比较；当实现删除功效时，假如待删除结点p左、右子树齐全，首先找到p中序前驱节点s（p中序前驱），然后用节点s值替换节点p值，再将节点s删除，节点s原左子树改为s双亲节点q右子树。实现中序遍历功效时，采取递归思想......
这是第一次相关编写程序课程设计。即使上机安排只有两天时间，可却并不像平时上机试验一样，离开了机房就不用再对着电脑屏幕编写代码，更多工作实在离开机房后完成。一遍一遍地按F9调试程序，error从几十个降低到多个，再到只剩多个warring，当按下Ctrl+F9，那精心设计“菜单”出现在屏幕上时，那一刻心情无以言表！涌上心头除了自豪感、成就感之外，还有对编程工作之辛劳慨叹！因为自己专业未来方向和这相关，不免让我考虑起毕业后发展方向。假如朝这方面发展话，我是否能够胜任这么工作？假如不是，又该选择什么？
五、 程序实施过程
5.1、创建二叉排序树并中序输出

5.2插入并中序输出

5.3、查找

5.4、删除并中序输出

六、程序清单
#include <stdio.h>
#define null 0
typedef int keytype;
typedef struct node
{
keytype key;
struct node *lchild,*rchild;
}bstnode,*bstree;

void insert(bstree *t,keytype x);
bstree search(bstree t,keytype x);
void display(bstree t);
void create(bstree *t)
{
keytype x;
*t=null;
scanf("%d",&x);
while(x!=-1)
{
insert(t,x);
scanf("%d",&x);
}
}
void insert(bstree *t,keytype x)
{
bstree s;
if(*t==null)
{
s=(bstree)malloc(sizeof(bstnode));
s->key=x;
s->lchild=null;
s->rchild=null;
*t=s;
}
else if(x<(*t)->key)
insert(&((*t)->lchild),x);
else if(x>(*t)->key)
insert(&((*t)->rchild),x);
}
bstree search(bstree t,keytype x)
{
bstree p;
p=t;
if(p!=null)
{
if (x==p->key) return p->key;
else if(x<p->key) return search(p->lchild,x);
else return search(p->rchild,x);
}
else
{ printf("%d can not be found\n",x);
return null;
}
}
bstree delete(bstree t,keytype x)
{
bstree p,q,r,s;
p=t;
r=null;
while(p)
{
if(x==p->key) break;
r=p;
if(x<p->key) p=p->lchild;
else p=p->rchild;
}
if(p==null) {printf("%d is not exist!\n",x);return t;}
if((p->lchild==null)||(p->rchild==null))
{
if(r==null)
if(p->lchild==null)
t=p->rchild;
else
t=p->lchild;
else if(p->lchild==null)
if(r->lchild==p)
r->lchild=p->rchild;
else
r->rchild=p->rchild;
else if(r->lchild==p)
r->lchild=p->lchild;
else
r->lchild=p->lchild;
free(p);
}
else
{
q=p;
s->lchild;
while(s->rchild)
{q=s;s->rchild;}
if(q==p)
q->lchild=s->lchild;
else
p->key=s->key;
free(s);
}
return t;
}
void display(bstree t)
{
if(t!=null)
{
display(t->lchild);
printf("%5d",t->key);
display(t->rchild);
}
}
void main(void)
{
bstree t,b;
int i=1,j;
keytype x;
while(i)
{
printf("\n* * * * * * * * * * * * * * * *\n");
printf("\n* MENU OF BSTREE *\n");
printf("\n* 1.create 2.insert *\n");
printf("\n* 3.search 4.delete *\n");
printf("\n* 5.exit *\n");
printf("\n* * * * * * * * * * * * * * * *\n");
printf(" what do you want to do? :");scanf("%d",&j);
switch(j)
{
case 1: printf("input bstree's values,end with -1:\n");create(&t);
printf("bstree's root is %d\n",t->key);display(t);break;

case 2: printf("input the insert value:");scanf("%d",&x);
insert(&t,x);display(t);break;

case 3: printf("input the search value:");scanf("%d",&x);
printf("result is: %d",search(t,x));break;

case 4: printf("input the delete value:");scanf("%d",&x);
delete(t,x);display(t);break;

case 5: i=0;break;
}
}
clrscr();
}