数据结构二叉排序树课程设计报告.docx
《数据结构二叉排序树课程设计报告.docx》由会员分享，可在线阅读，更多相关《数据结构二叉排序树课程设计报告.docx（18页珍藏版）》请在冰点文库上搜索。
数据结构二叉排序树课程设计报告
创作编号：
GB8878185555334563BT9125XW
创作者：
凤呜大王*
课程设计报告
——数据结构
题目：
二叉排序树
姓名：
学号：
专业：
班级：
指导老师：
年月日
2.1、原理分析............................................................................3
2.2、流程图................................................................................4
1、main（）函数....................................................................4
2、创建...............................................................................4
3、插入...............................................................................5
4、查找...............................................................................6
5.1、创建二叉排序树并中序输出.........................................135.2、插入并中序输出..............................................................13
5.3、查找..................................................................................14
一、课程设计简介
1.1、题目：
二叉排序树相关操作
1、创建二叉排序树；2、插入给定值；
3、查找给定值；4、删除给定值的结点。
1.2、报告要求：
1、封面;2、题目与流程图或模块图;
3、程序清单和运行结果;4、小结（收获和体会）;
5、装订成册。
1.3、目的：
课程设计为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。
提高学生适应实际，实践编程的能力。
二、原理分析及流程
2.1、原理分析：
根据题目要求，要实现这些功能，就必须创建一个菜单。
这个菜单设置在main（）函数里面，然后使用while（）...switch（）语句进行循环调用相关函数，以达到实现相关功能的目的。
2.2、流程图：
1、main（）函数：
2、创建：
3、插入：
N
Y
N
Y
4、查找：
Y
N
YN
5、中序遍历输出：
三、算法描述
3.1、存储结构
定义一个链表式的二叉排序树，用链表的方式构造结点，存储二叉排序树中的结点、结点类型和指针类型如下：
#include
#definenull0
typedefintkeytype;
typedefstructnode
{
keytypekey;
structnode*lchild,*rchild;
}bstnode,*bstree;
3.2、插入算法
在二叉排序树中插入一个新节点，首先要查找该节点在二叉排序树中是否已经存在。
若二叉排序树中不存在关键字等于x的节点，则插入。
将一个关键字值为x的节点s插入到二叉排序树中，可以用下面的方法：
（1）若二叉排序树为空，则关键字为x的节点s成为二叉排序树的根
（2）若二叉排序树非空，则将x与二叉排序树根进行比较，如果x的值等于根节点关键值，则停止插入；如果x的根节点值小于根节点关键值，则将x插入左子树；如果x的值大于根节点关键字的值，则将x插入右子树。
在左右两个子树的插入方法与整个二叉排序树相同。
算法如下：
voidinsert（bstree*t,keytypex）
{
bstrees;
if（*t==null）
{
s=（bstree）malloc（sizeof（bstnode））;
s->key=x;
s->lchild=null;
s->rchild=null;
*t=s;
}
elseif（x<（*t）->key）
insert（&（（*t）->lchild）,x）;
elseif（x>（*t）->key）
insert（&（（*t）->rchild）,x）;
}
3.3、查找算法
（1）若二叉排序树不为空，将根结点的关键字与待查关键字进行比较，若相等，则查找成功；若根节点关键字大于待查值，则进入左子树重复次步骤，否则，进入右子树进行此步骤；若在查找过程中遇到二叉排序树的叶子节点时，还没有找到待查节点，则查找不成功。
（2）否则，查找失败，返回null。
算法如下：
bstreesearch（bstreet,keytypex）
{
bstreep;
p=t;
if（p!
=null）
{
if（x==p->key）returnp->key;
elseif（xkey）returnsearch（p->lchild,x）;
elsereturnsearch（p->rchild,x）;
}
else
{printf（"%dcannotbefound\n",x）;returnnull;
}
}
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的右子树。
算法如下：
bstreedelete（bstreet,keytypex）
{
bstreep,q,r,s;
p=t;
r=null;
while（p）
{
if（x==p->key）break;
r=p;
if（xkey）p=p->lchild;
elsep=p->rchild;
}
if（p==null）{printf（"%disnotexist!
\n",x）;returnt;}
if（（p->lchild==null）||（p->rchild==null））
{
if（r==null）
if（p->lchild==null）
t=p->rchild;
elset=p->lchild;
elseif（p->lchild==null）
if（r->lchild==p）
r->lchild=p->rchild;
elser->rchild=p->rchild;
elseif（r->lchild==p）
r->lchild=p->lchild;
elser->lchild=p->lchild;
free（p）;
}
else
{
q=p;
s->lchild;
while（s->rchild）
{q=s;s->rchild;}
if（q==p）q->lchild=s->lchild;
elsep->key=s->key;
free（s）;
}
returnt;
}
四、小结与体会
经过一个多星期来夜以继日的努力，终于把课程设计——二叉排序树的相关算法全部完成！
在编写程序过程中，让我对二叉排序树的创建、插入、查找、删除算法有了较系统的认识，也发现了一些以前纸上谈兵时的思想误区。
比如实现插入功能时，从根节点开始比较；当实现删除功能时，如果待删除结点p左、右子树齐全，首先找到p的中序前驱节点s（p的中序前驱），然后用节点s的值代替节点p的值，再将节点s删除，节点s的原左子树改为s的双亲节点q的右子树。
实现中序遍历功能时，采用递归思想......
这是第一次关于编写程序的课程设计。
虽然上机安排只有两天时间，可却并不像平时上机实验一样，离开了机房就不用再对着电脑屏幕编写代码，更多的工作实在离开机房后完成的。
一遍一遍地按F9调试程序，error从几十个减少到几个，再到只剩几个warring，当按下Ctrl+F9，那精心设计的“菜单”出现在屏幕上时，那一刻的心情无以言表！
涌上心头的除了自豪感、成就感之外，还有对编程工作之辛苦的慨叹！
因为自己专业将来的方向与这有关，不免让我考虑起毕业后的发展方向。
如果朝这方面发展的话，我是否可以胜任这样的工作？
如果不是，又该选择什么？
5、程序执行过程
5.1、创建二叉排序树并中序输出
5.2插入并中序输出
5.3、查找
5.4、删除并中序输出
六、程序清单
#include
#definenull0
typedefintkeytype;
typedefstructnode
{
keytypekey;
structnode*lchild,*rchild;
}bstnode,*bstree;
voidinsert（bstree*t,keytypex）;
bstreesearch（bstreet,keytypex）;
voiddisplay（bstreet）;
voidcreate（bstree*t）
{
keytypex;
*t=null;
scanf（"%d",&x）;
while（x!
=-1）
{
insert（t,x）;
scanf（"%d",&x）;
}
}
voidinsert（bstree*t,keytypex）
{
bstrees;
if（*t==null）
{
s=（bstree）malloc（sizeof（bstnode））;
s->key=x;
s->lchild=null;
s->rchild=null;
*t=s;
}
elseif（x<（*t）->key）
insert（&（（*t）->lchild）,x）;
elseif（x>（*t）->key）
insert（&（（*t）->rchild）,x）;
}
bstreesearch（bstreet,keytypex）
{
bstreep;
p=t;
if（p!
=null）
{
if（x==p->key）returnp->key;
elseif（xkey）returnsearch（p->lchild,x）;
elsereturnsearch（p->rchild,x）;
}
else
{printf（"%dcannotbefound\n",x）;
returnnull;
}
}
bstreedelete（bstreet,keytypex）
{
bstreep,q,r,s;
p=t;
r=null;
while（p）
{
if（x==p->key）break;
r=p;
if（xkey）p=p->lchild;
elsep=p->rchild;
}
if（p==null）{printf（"%disnotexist!
\n",x）;returnt;}
if（（p->lchild==null）||（p->rchild==null））
{
if（r==null）
if（p->lchild==null）
t=p->rchild;
else
t=p->lchild;
elseif（p->lchild==null）
if（r->lchild==p）
r->lchild=p->rchild;
else
r->rchild=p->rchild;
elseif（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）;
}
returnt;
}
voiddisplay（bstreet）
{
if（t!
=null）
{
display（t->lchild）;
printf（"%5d",t->key）;
display（t->rchild）;
}
}
voidmain（void）
{
bstreet,b;
inti=1,j;
keytypex;
while（i）
{
printf（"\n****************\n"）;
printf（"\n*MENUOFBSTREE*\n"）;
printf（"\n*1.create2.insert*\n"）;
printf（"\n*3.search4.delete*\n"）;
printf（"\n*5.exit*\n"）;
printf（"\n****************\n"）;
printf（"whatdoyouwanttodo?
:
"）;scanf（"%d",&j）;
switch（j）
{
case1:
printf（"inputbstree'svalues,endwith-1:
\n"）;create（&t）;
printf（"bstree'srootis%d\n",t->key）;display（t）;break;
case2:
printf（"inputtheinsertvalue:
"）;scanf（"%d",&x）;
insert（&t,x）;display（t）;break;
case3:
printf（"inputthesearchvalue:
"）;scanf（"%d",&x）;
printf（"resultis:
%d",search（t,x））;break;
case4:
printf（"inputthedeletevalue:
"）;scanf（"%d",&x）;
delete（t,x）;display（t）;break;
case5:
i=0;break;
}
}
clrscr（）;
}
创作编号：
GB8878185555334563BT9125XW
创作者：
凤呜大王*
升级会员 