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

课 程 设 计报 告数据结构题目：二叉排序树 姓 名: 学 号: 专 业： 班 级： 指导老师： 年 月 日目 录一、课程设计简介3二、原理分析及流程32、原理分析、3 2、流程图、4 1、（)函数、4 、创建、4 、插入、5 4、查找、5、中序遍历输出三、算法描述83、1、存储结构3、2、插入算法83、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()函数里面,然后使用wile（）、with()语句进行循环调用相关函数，以达到实现相关功能得目得。 2、2、流程图:选择操作main()开始选择1创建选择2插入选择3查找选择4删除选择5退出 1、main(）函数：Create(&t)输入结点值,以-1结束调用插入函数 2、创建： 、插入：Insert(&t,x)输入给定得结点值*t=nullxkeyinsert(&(*t)-lchild)x);insert(&(*t)-rchild)x)*t=s结束N N 4、查找：返回search(p-rchild,x)输入给定得结点值x,p=tP!=nullxkey返回search(p-lchild,x)返回nullsearch(t,x)返回p-keyx=p-keyYNY 5、中序遍历输出:display(t)t!=nulldisplay(t-lchild)访问并输出根节点display(t-rchild)三、算法描述 、1、存储结构定义一个链表式得二叉排序树,用链表得方式构造结点,存储二叉排序树中得结点、结点类型与指针类型如下： #inclde sdio、h #deneu ypeef nt kytpe； typedef ruct oe key ky; stct node hild,rchild； bsnd，bsree； 3、2、插入算法 在二叉排序树中插入一个新节点,首先要查找该节点在二叉排序树中就是否已经存在。若二叉排序树中不存在关键字等于x得节点，则插入. 将一个关键字值为x得节点s插入到二叉排序树中，可以用下面得方法: (1)若二叉排序树为空,则关键字为x得节点s成为二叉排序树得根 （2)若二叉排序树非空,则将与二叉排序树根进行比较，如果得值等于根节点关键值，则停止插入；如果x得根节点值小于根节点关键值，则将x插入左子树；如果x得值大于根节点关键字得值，则将插入右子树.在左右两个子树得插入方法与整个二叉排序树相同. 算法如下：void inrt(bstree t，ketyp ） bsee s; if（*=null) s=（bstre）mallo(sizeof(bsnde)）;skeyx;slchid=nll；s-rhilnull；t=; lse i(lchild)，x)；elsei（*t)ke)nsrt（(（*t）-rchild），x）； 、查找算法 (1）若二叉排序树不为空，将根结点得关键字与待查关键字进行比较，若相等,则查找成功；若根节点关键字大于待查值，则进入左子树重复次步骤，否则，进入右子树进行此步骤；若在查找过程中遇到二叉排序树得叶子节点时,还没有找到待查节点，则查找不成功. （2)否则，查找失败,返回null。 算法如下：bstreeearch(ste ,keytyp x）bsee p； p=t； if（！ul） if （=py) eurn py; lse i(xp-key）rturnsearc（lcild，x）; els return seach(p-cild，）； el ritf(”cn nt e fodn，)；reur nll; 3、删除算法 在二叉排序树中删除节点,首先要确定被删除得节点就是否在二叉排序树中。若不在，则不做任何操作；否则，假设要删除得节点为p，节点p得父节点为r,并假设p就是r得左孩子。根据被删除节点p有无孩子，删除部分可做以下3中情况讨论： (）若p为叶子节点，则可令其父节点r得左孩子指针域为空，直接将其删除。（2)若p节点只有右子树或左子树，则可以将得左子树或右子树直接改为其双亲节点r得左子树。（3）若p既有左子树又有右子树；将节点s为得中序前驱。首先找到p得中序前驱节点s,然后用节点s得值代替节点得值,再将节点删除,节点s得原左子树改为s得双亲节点q得右子树。 算法如下:bstee delte(bstreet,eyte） stree p,q，r，s；t; =nul； whe（p） if(x=pey） bre； rp； if（xpkey） pp-lchild； else p=pchld； if(p=） rint（”%d s not exst！，x)；returnt; if(（chl=null)|(p-chd=null) if（r=null） if(plchid=null） =p-rchl； e lcild; lsei（plch=ll） if(rchild=) rchild=prchild； elsr-childprcild; eseif（rlchil=p） -lchild=p-child； es r-hidplild; free(p）； ele =p； s-lcld; whie（sl） =s；s-rchid; if(q=p) qlcldsild; els -key=skey；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、删除并中序输出 六、程序清单#iclue tio、h#fin nul tyedef int keyy；tyedftruct nde eytpekey； suct node chi，rchil;btnode,bste；idnsert（stre *t，ktype x）;btre seach（bstree t,eytp x)；void isplay（bstreet)；void eate（btree*t） eype x； *tnul; scanf(”%d，&x）; while(x！=-1） insert(t,x)； scanf（d”,x); void nsert(bstree *t,eype x) bstree s; if（t=ull） s=（bstre）malloc（sif(bstnode）);ky；lhilnull；srchild=nul;t=s； else if(x（*)-key) insrt（&（(）chil），x）； lse if（)key) insert（(*t）rhl）,x);breeah（stree t，eytye x） bteep； p=t;if(p！=null） （x=p-ke） rur p-key； lse i（xpkey) return sarc(plcil,x）; elseeturn search（-child,x); else ritf（% ca ntbefudn”,x）; etun ul； bstee dlt(bstree ，keytpe ） sreep，q，r,s； p=; r=null； hil(p) if（x=-key) r; rp； if（lcil； else p=prchi； f(=null） rntf（%d sot st!”,x);rtr t； if(（pild=ull）|(p-chl=nll） if（r=nul)i（plchid=null） =prchid; le t-lchild; ele if（plchid=null） if(r-lcld=） r-lhldp-id； lserrhild=rcld; else if（r-lhld=p） -lchild-lchid; else r-lchild=lhild; ee（)； else qp； hil； while（scd) q；child； i（=p) qlchil=slcild； el pky-key; fre（）； eturnt;voiddisplay(bsreet） if（t!=null） islay（t-lchil）；pint(%5d,tkey);display(ci)； void man（oi)bse ,； int=1，j； keytye x； hile（i) prif(”n* * * * * * * * ）；print(n MEU O BREE *n”);ritf（”n* 、create 2、inset n）;pinf（n 3、sarh 4、eet n”）；rntf(n 5、eit n）;rit（* * * * * * n”）; ntf(”what o you wnt o do? ：）；cnf（d”，j)； sit(j) c 1： intf（iput bstrees values，nd w -1：n）；eate（）;print（btre oot is%d”，t-key);dsplay（）；brea； case 2： prntf（npute isertvalue:”）；canf(”%d，&x）;insert(&t,x）;dsplay(t);reak； case 3： rintf（iput theearh vlu：）；scanf（”d”，)；printf(reut ： %d,arc(t，x）)；brak； cse 4： print（nput he lte alue:）;scn（”%d,x);dlete(,x);disply（t）;brak； case 5: i0;break； clrscr(）；