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

课 程 设 计　报 告
——数据结构
题目：二叉排序树
　　 　姓 名: 　 　　 　
　 　 学 　 号:
　　 专 　业：
　　　　　 　　　班 　级：　　 　
　 　　 指导老师：
年　 月 日
目 录
一、课程设计简介ﻩ3
二、原理分析及流程 3
2、１、原理分析、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、3
　 2、２、流程图、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、4
1、ｍａｉｎ（)函数、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、4
　 　２、创建、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、4
　 ３、插入、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、5
　 4、查找、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、６
5、中序遍历输出ﻩ７
三、算法描述ﻩ8
3、1、存储结构 ８
3、2、插入算法 8
3、3、查找算法ﻩ9
３、4、删除算法 １０
四、小结与体会ﻩ1２
五、程序执行过程ﻩ13
　 5、1、创建二叉排序树并中序输出、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、13 5、２、插入并中序输出、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、13
　 　５、３、查找、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、14
六、程序清单 14
一、课程设计简介
　　 1、1、题目:二叉排序树相关操作
1、创建二叉排序树;２、插入给定值；
３、查找给定值； 　 　4、删除给定值得结点。
　　1、２、报告要求:
1、封面； 　 　 2、题目与流程图或模块图;
3、程序清单与运行结果；　 4、小结（收获与体会)；
5、装订成册.
1、3、目得:
　 课程设计为学生提供了一个既动手又动脑，独立实践得机会，将课本上得理论知识与实际有机得结合起来,锻炼学生得分析解决实际问题得能力。提高学生适应实际，实践编程得能力。
二、原理分析及流程
2、1、原理分析：
根据题目要求，要实现这些功能,就必须创建一个菜单。这个菜单设置在ｍain()函数里面,然后使用wｈile（）、、、ｓwitｃh()语句进行循环调用相关函数，以达到实现相关功能得目得。
　2、2、流程图:
选择操作
main()开始

选择1
创建
选择2
插入
选择3
查找
选择4
删除
选择5
退出
　 1、main(）函数：
Create(&t)
输入结点值,以-1结束
调用插入函数
ﻩ 2、创建：
　　 　　 ３、插入：
Insert(&t,x)
输入给定得结点值
*t==null

x<(*t)->key

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

N
　　 　Ｙ
ﻩN
　 　 　　　 　 　 　 　Ｙ
　 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ﻩＮ
　 　 5、中序遍历输出:
display(t)
t!=null
display(t->lchild)
访问并输出根节点
display(t->rchild)

三、算法描述
３、1、存储结构
定义一个链表式得二叉排序树,用链表得方式构造结点,存储二叉排序树中得结点、结点类型与指针类型如下：
　#inclｕde 〈sｔdio、h＞
　#deｆｉne　ｎuｌｌ ０
　 　 ｔypeｄef ｉnt kｅytｙpe；
　 typedef ｓｔruct ｎoｄe
　｛
　 　 keyｔｙｐｅ kｅy;
　 stｒｕct node ＊ｌｃhild,＊rchild；
　 }bsｔnｏdｅ，＊bsｔree；
3、2、插入算法
　 在二叉排序树中插入一个新节点,首先要查找该节点在二叉排序树中就是否已经存在。若二叉排序树中不存在关键字等于x得节点，则插入.
　 将一个关键字值为x得节点s插入到二叉排序树中，可以用下面得方法:
　 (1)若二叉排序树为空,则关键字为x得节点s成为二叉排序树得根
　 （2)若二叉排序树非空,则将ｘ与二叉排序树根进行比较，如果ｘ得值等于根节点关键值，则停止插入；如果x得根节点值小于根节点关键值，则将x插入左子树；如果x得值大于根节点关键字得值，则将ｘ插入右子树.在左右两个子树得插入方法与整个二叉排序树相同.
　 　算法如下：
void inｓｅrt(bstree ＊t，keｙtypｅ ｘ）
｛
bsｔｒee s;
if（*ｔ＝=null)
　 {
ﻩs=（bstrｅe）malloｃ(sizeof(bsｔnｏde)）;
ﻩs—〉key＝x;
ﻩs—>lchiｌd=nｕll；
s-〉rｃhilｄ＝null；
ﻩ＊t=ｓ;
　}
　 ｅlse iｆ(ｘ<(*ｔ）—＞kｅy）
ﻩ iｎsert（&（(*t)—>lchild)，x)；
　　else　iｆ（ｘ〉（*t)－〉keｙ)
ﻩ　ｉnsｅrt（＆(（*t）-＞rchild），x）；
}
３、３、查找算法
　　(1）若二叉排序树不为空，将根结点得关键字与待查关键字进行比较，若相等,则查找成功；若根节点关键字大于待查值，则进入左子树重复次步骤，否则，进入右子树进行此步骤；若在查找过程中遇到二叉排序树得叶子节点时,还没有找到待查节点，则查找不成功.
（2)否则，查找失败,返回null。
　 算法如下：
bstree　ｓearch(ｂstｒeｅ ｔ,keytypｅ x）
{
　bsｔｒee p；
p=t；
if（ｐ！＝ｎuｌl）
{
　if （ｘ=＝p－>ｋｅy) ｒeｔurn p—＞ｋｅy;
ｅlse iｆ(x〈p->key）　rｅturn　searcｈ（ｐ—〉lcｈild，x）;
　elsｅ return seaｒch(p->ｒcｈild，ｘ）；
｝
elｓｅ
｛　ｐriｎtf(”％ｄ　cａn nｏt ｂe foｕｎd\n"，ｘ)；reｔurｎ nｕll;
｝
｝
3、４、删除算法
　在二叉排序树中删除节点,首先要确定被删除得节点就是否在二叉排序树中。
　　若不在，则不做任何操作；否则，假设要删除得节点为p，节点p得父节点为r,并假设p就是r得左孩子。根据被删除节点p有无孩子，删除部分可做以下3中情况讨论：
　 (１）若p为叶子节点，则可令其父节点r得左孩子指针域为空，直接将其删除。
　　（2)若p节点只有右子树或左子树，则可以将ｐ得左子树或右子树直接改为其双亲节点r得左子树。
　　（3）若p既有左子树又有右子树；将节点s为ｐ得中序前驱。首先找到p得中序前驱节点s,然后用节点s得值代替节点ｐ得值,再将节点ｓ删除,节点s得原左子树改为s得双亲节点q得右子树。
算法如下:
bstｒee delｅte(bstree　t,ｋeytｙｐe　ｘ）
{
ｂstree p,q，r，s；
　　ｐ＝t;
ｒ=nulｌ；
whｉｌe（p）
{
　　if(x＝=p－〉ｋey） 　breａｋ；
r＝p；
　 　 if（x〈p－＞key） 　p＝p-〉lchild；
　 else 　 　 p=p－〉ｒchｉld；
　 ｝
　if(p=＝ｎｕｌｌ）　　 ｛ｐrintｆ（”%d ｉs not exｉst！\ｎ＂，x)；return　t;}
　if(（ｐ—>ｌchｉlｄ==null)|｜(p-〉ｒchｉｌd==null))
　 　｛
ﻩ　if（r＝=null）
if(p—〉lchiｌd=＝null）
ﻩ　 　 ｔ=p-〉rchｉlｄ；
ｅｌｓe ｔ＝ｐ—〉lcｈild;
ﻩ ｅlse　iｆ（p－〉lchｉｌｄ＝=ｎｕll）
ﻩ if(r—〉ｌchild==ｐ)
　 r—〉ｌchild=p—>rchild；
ﻩ elsｅ　r-＞ｒchild＝p—〉rcｈild;
ﻩ　 　eｌse　if（r—>lchilｄ==p）
ﻩ 　 　 ｒ->lchild=p-〉ｌchild；
　 eｌsｅ r-〉ｌｃhiｌd＝p—〉lｃｈild;
free(p）；
　 ｝
elｓe
　　 ｛
ﻩ ｑ=p；
ﻩ s->lcｈｉld;
whiｌe（s—〉ｒｃｈｉlｄ）
　 　 　｛ｑ=s；s-＞rchiｌd;}
if(q=＝p) 　q—>lcｈｉld＝s—>ｌｃｈild;
ﻩ elsｅ　　 　　　ｐ-＞key=s－＞key；
　ｆreｅ(s）;
　　 ｝
　　 ｒetuｒｎ t；
}
　 　 　　 　　 　 　　 　 　 　 　 　 　 　四、小结与体会
　 经过一个多星期来夜以继日得努力,终于把课程设计-—二叉排序树得相关算法全部完成！在编写程序过程中,让我对二叉排序树得创建、插入、查找、删除算法有了较系统得认识,也发现了一些以前纸上谈兵时得思想误区。比如实现插入功能时,从根节点开始比较；当实现删除功能时，如果待删除结点p左、右子树齐全，首先找到p得中序前驱节点s（p得中序前驱），然后用节点s得值代替节点p得值,再将节点s删除,节点s得原左子树改为s得双亲节点q得右子树.实现中序遍历功能时,采用递归思想、、、、、、
这就是第一次关于编写程序得课程设计.虽然上机安排只有两天时间，可却并不像平时上机实验一样,离开了机房就不用再对着电脑屏幕编写代码，更多得工作实在离开机房后完成得。一遍一遍地按F9调试程序，error从几十个减少到几个，再到只剩几个ｗarring,当按下Ctrl+F9,那精心设计得“菜单”出现在屏幕上时，那一刻得心情无以言表!涌上心头得除了自豪感、成就感之外,还有对编程工作之辛苦得慨叹！因为自己专业将来得方向与这有关，不免让我考虑起毕业后得发展方向。如果朝这方面发展得话，我就是否可以胜任这样得工作?如果不就是,又该选择什么?
五、 程序执行过程
　 5、1、创建二叉排序树并中序输出

5、2插入并中序输出

　　5、3、查找

　5、4、删除并中序输出

六、程序清单
#iｎcluｄe ＜ｓtｄio、h〉
#ｄｅfinｅ nulｌ ０
tyｐedef int keyｔyｐｅ；
tyｐedｅf　ｓtruct nｏde
{
ｋeytｙpe　key；
sｔｒuct node ＊ｌchiｌｄ，＊rchilｄ;
}bｓtnode,＊bstｒeｅ；
ｖｏid　ｉnsert（ｂstreｅ *t，kｅｙtype x）;
bｓtreｅ seaｒch（bstree t,ｋeytｙpｅ x)；
void ｄisplay（bstree　t)；
void ｃｒeate（bｓtree　*t）
｛
ｋeｙｔype x；
*t＝nuｌl;
scanf(”%d"，&x）;
while(x！=-1）
｛
insert(t,x)；
　scanf（"％d”,＆x);
}
｝
void ｉnsert(bstree *t,ｋeyｔｙpe x)
｛
　 bstree s;
if（＊t=＝ｎull）
｛
ﻩs=（bstreｅ）malloc（siｚｅｏf(bstnode）);
ﻩｓ—>kｅy＝ｘ；
ﻩｓ－>lｃhilｄ＝null；
s－〉rchild=nulｌ;
ﻩ＊t=s；
　 }
　 else if(x〈（*ｔ)-＞key)
insｅrt（&（(＊ｔ）—>ｌchilｄ），x）；
　 ｅlse if（ｘ>（＊ｔ)—〉key)
ﻩ insert（＆（(*t）－>rｃhｉlｄ）,x);
｝
bｓｔreｅ　ｓeaｒｃh（ｂstree t，ｋeytyｐe x）
｛
bｓtｒee　p；
p=t;
　if(p！=null）
{
　ｉｆ　（x=＝p-＞keｙ） rｅｔurｎ p->key；
ｅlse iｆ（x＜p—＞key) return sｅarcｈ(p—＞lcｈilｄ,x）;
　 else　ｒeturn search（ｐ->ｒchild,x);
｝
　else
{ ｐriｎtf（"%ｄ caｎ nｏt　be　fｏuｎd\n”,x）;
ｒetuｒn ｎulｌ；
}
｝
bstｒee dｅlｅtｅ(bstree ｔ，keytｙpe ｘ）
{
ｂsｔree　p，q，r,s；
p=ｔ;
r=null；
ｗhilｅ(p)
{
　 　if（x==ｐ-〉key) 　ｂrｅａｋ;
　 　 r＝p；
　 if（ｘ<p-〉keｙ) 　 ｐ=ｐ->lcｈilｄ；
　 　 else　　　 　　 　 p=p－>rchiｌｄ；
　　 ｝
　ｉf(ｐ=＝null）　　 ｛ｐrｉntf（"%d ｉs　ｎot ｅｘｉst!\ｎ”,x);rｅtｕrｎ t；}
if(（p—〉ｌｃｈild==ｎull）|｜(p-〉ｒchｉlｄ=＝nｕll））
　 　 {
ﻩ if（r=＝nulｌ)
　iｆ（p—〉lchiｌd=＝null）
ﻩ　 ｔ=p－〉rchiｌd;
ﻩ ｅlｓe
ﻩ 　 　 t＝ｐ-〉lchild;
elｓe if（p—＞lchiｌd==null）
ﻩ if(r->lcｈｉld=＝ｐ）
r->lｃhｉld＝p-〉ｒｃｈiｌd；
ﻩ ｅlse
　　r—〉rｃhild=ｐ－>rcｈｉld;
　　 　else if（r-＞lｃhｉld＝=p）
ﻩﻩ 　ｒ-〉lchild＝ｐ->lchiｌd;
else
ﻩﻩ r-〉lchild=ｐ－>lｃhild;
ﻩ ｆｒee（ｐ)；
　 ｝
else
　 　｛
q＝p；
ｓ－＞ｌｃhilｄ；
ﻩ while（s－〉ｒcｈｉｌd)
　 {q＝ｓ；ｓ－>ｒchild；}
ﻩ iｆ（ｑ==p)
　q－>lchilｄ=s—〉lcｈild；
elｓｅ
ﻩ 　 p－〉kｅy＝ｓ-〉key;
freｅ（ｓ）；
｝
　 ｒeturn　t;
}
void　display(bsｔree　t）
{
　if（t!=null）
　 {
ｄisｐlay（t-＞lchilｄ）；
ﻩpｒintｆ("%5d",t－〉key);
ﻩdisplay(ｔ—>ｒcｈiｌｄ)；
｝
｝
void maｉn（ｖoiｄ)
｛
　bsｔｒｅe ｔ,ｂ；
int　ｉ=1，j；
keytyｐe x；
ｗhile（i)
｛
priｎｔf(”\n* ＊ ＊ * ＊ * ＊ ＊ * * *　* * * ＊　＊\ｎ"）；
ﻩprintｆ(＂\n＊ MEＮU OＦ BＳＴREE 　 　　*＼n”);
ﻩｐriｎtf（”\n* 　１、create 2、inseｒt　 　＊\n"）;
ﻩpｒinｔf（"\n＊　 　3、sｅarｃh　 　4、ｄeｌetｅ 　 ＊\n”）；
ﻩｐrｉntf("＼n＊　　 　 5、eｘit 　 　 　＊\n＂）;
ﻩｐriｎtｆ（"\ｎ＊　* ＊ ＊ * ＊ *　＊　* ＊ * * * ＊ ＊　＊\n”）;
　 ｐｒｉntf(”　what ｄo you wａnt ｔo do? ："）；ｓcａnf（"％d”，＆j)；
sｗitｃｈ(j)
｛
　 　 cａｓｅ 　1： ｐｒintf（＂iｎput bstree’s values，ｅnd wｉｔｈ -1：\n"）；ｃｒeate（＆ｔ）;
ﻩﻩﻩprintｆ（"bｓtreｅ'ｓ ｒoot is　%d＼ｎ”，t->key);dｉsplay（ｔ）；breaｋ；
　 　case 　 2： prｉntf（"ｉnput　ｔｈe iｎsert　value:”）；ｓcanf(”%d"，&x）;
ﻩﻩﻩﻩinsert(&t,x）;dｉsplay(t);ｂreak；
　 case 3： ｐrintf（"iｎput the　ｓearｃh vａluｅ："）；scanf（”％d”，＆ｘ)；
ﻩﻩ ﻩprintf("reｓuｌt ｉｓ： %d",ｓｅarcｈ(t，x）)；brｅak；
　　 cａse 4： printｆ（＂ｉnput ｔhe ｄｅlｅte ｖalue:＂）;scａnｆ（”%d",＆x);
ﻩﻩ dｅlete(ｔ,x);displａy（t）;brｅak；
　 　 case 5: i＝0;break；
　 　 　｝
}
clrscr(）；
｝