二叉排序树的创建、删除、插入等操作

1、淮阴工学院算法设计技能训练实习报告题目： 二叉排序树的创建、插入、删除系（院），计算机工程学院专 业：计算机科学与技术班 级：计算机M123学 号：1321124姓名：单永明指导教师：刘作军/寇海州学年学期.，20142015学年 第土学期算法设计技能训练任务书课题名称设计目的1、通过算法设计技能训练，深入理解算法设计的意义和重要性，更好地掌握算法设计的知识。Z、能够针对某一具体问题，设计算法进行解决。M、锻炼实践动手能力，提高解决问题的能力。实验环境硬件：1、PC机，奔腾w以上CPU，512MB以上内存，80G以上硬盘；软件：的况C+编程工具任务要求1分析问题，给出数学模型，选择数据结构2设

2、计算法，给出算法描述M给出源程序清单站编辑、编译、调试源程序5,撰写课程设计报告工作进度计划序号起止日期工作内容12014.12.20任务下达，查阅文献资料22014,12,25 2014,12,28总体设计、素材搜集、课题详细设计、调试32014,12,29 2013,12,31完善设计、撰写报告42014.12.31答辩指导教师（签章）:目录 TOC o 1-5 h z 7、引言4公课程设计的题目和内容52.7课程设计的题目5 HYPERLINK l bookmark16 o Current Document 2.2课程设计的内容5 HYPERLINK l bookmark21 o Cur

3、rent Document 3、课程设计报告内容63.7课程概述63.2实验内容73.3源程序代码703.4测试用例75 HYPERLINK l bookmark27 o Current Document 实验总结78 HYPERLINK l bookmark30 o Current Document 致谢79参考文献201.弓|言本算法设计技能训练的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特 性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好 的程序设计技能。公课程设计的题目和内容课程设计的题目二叉排序树的基本操作2.2、课程设计内

4、容1,用二叉链表作存储结构，2编写程序实现二叉排序树上的基本操作:M输入数列生成二叉排序树对二叉排序作中序遍历；查找二叉排序树5,删除二叉排序树3、课程设计报告内容3.1课题概述1、问题描述：（需求分析和背景意义）利用二叉排序树实现一个动态查找表。Z、基本要求：（设计阶段，概要设计和详细设计）实现动态查找表的三种功能：查找、插入、删除。3、测试数据：自行设定。彳、实现提示：（1）初始，二叉排序树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。每次插入或删除一个结点后，应更二叉排序树的显示。3）二叉排序树的显示可采用凹入表现形式，也可以采用图形界面画出树行。（3）

5、教科书已给出查找和插入算法，本题重点在于对删除算法的设计和实现。假设要删除关键字为/的结点。如果，不在叶子结点上，则用它的左子树中最大值或右子树中的最小值取代。如此反 复取代，直到删除动作传递到某个叶子结点。删除叶子结点时，若需要进行平衡交换，可采用插入的 平衡变换的反变换（如，左子树变矮对应右子树长高）。L升始依次输入.个关键字删除任意结点插入一个结点中序输出操作后二叉排序树是结束21M主要模块:1）主函数模块Main()建立n个关键字的二叉排序树并输出；从二叉树排序树T中删除任意结点，其关键字为绍；在二叉树排序树T中，插入一个结点，其关键字为右；在二叉排序树T中递归查找关键字等于邮的数据元

6、素;2)创建二叉排序树模块B腿 CeaBSW n)建立n个关键字的二叉排序树；从键盘输入调建立n个关键字依次用为初tBST7(插入函数);返回根结点T；输出过程；M)删除模块DeteNodeCBUnee &T, int x)从二叉树排序树7中删除任意结点，其关键字为.；可以实现删除根结点、叶子结点以及其它任意结点的功能；4）插入模块void InerBSF（B7re &7,Bi7Nde 物在二叉树排序树7中，插入一个结点s（递归算法）；被CneatBS7函数调用；5）查找模块Bi7re seanchBS71（B7nee 7,7EEyp key）在根指针7所指二叉排序树中递归查找关键字等于她的数

7、据元素;若成功，返回指向该数据元素结点的指针；否则返回空指针；源程序代码:#inclodeusing name space std;typedef int KeyType;typedef struct tree/ 声明树的结构struct tree *lft /存放左子树的指针struct tree night; 存放又子树的指针KeyType key; /存放节点的内容 BSTNd * BSW /声明二叉树的链表BSTree inettBST(BSTiee tptr/KeyType key)/ 在二叉排序树中插入结点/若二叉排序树惭中没有关键字为绍的结点，则插入，否则直接返回BSTree f

8、,阡咿;/p的初值指向根结点whie(p)/查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲if(p-key=key) /树中已有 绍，无须插入return tptr;f=p; /f保存当前查找的结点，即f是p的双亲fr=(BSTnee )mdlc(5僧STNd); /生成新结点p-key=key; p-left=p-ncght=NULL;if(tptr=NULL) /原树为空，新插入的结点为新的根华冗二p;elsef(keykey)if(keykey)f-left=p；elsef-ri佩二p；return tptr;BSTree eneateBSTO/建立二叉树BSTnee t=

9、NULL; /根结点KeyType key;einkey;l=cn4entBST(t,key);l=cn4entBST(t,key);w4cle(key!=-1)return t;void in&Jtg(BSTg 51中序遍历打印二叉排序树4(p!=NUU)(4(p!=NUU)(left );left );keycout keynight );int seanchBSTCBSTnee t,KeyType key)/查找if(key=t-key)if(key=t-key)inorder_btree(p-rcght );int seanchBSTCBSTnee t,KeyType key)/查找4

10、(t=NUU)4(t=NUU)return 1;if(keykey)if(keykey)netunn 0;seanchBST(t-left,key);netunn seanchBST(lef,key);elseBSTree deleteBSTBSTree tptr,KeyType 龙y/删除BSTree p,tmp,panent=NULL;p=tptr;4(p-ky=ky)4(p-ky=ky)while(p)break;pnent二p；if(fp) return NtLL;if(fp) return NtLL;else cf(p=pannt-right)tmp=p;4（毕-叫农&毕-/*p的左

11、右子树都为空*/（4（!g） /要删根，须修改根指针tptn=NULL;else cf(p=pannt-right)panen-rcght=NULL;elsepanen-left=NULL;fnee(p);char cmd;BSTree root;do(c&utnnendl;couttt请选择你要执行的操作,endl；ccotnendl;eootVgt C创建一棵二叉排序树n, coot% E.结束本程序n;endl;coutnntt* fag=0;do(4(fag/=0)coutcmd;f+;、Wde(cmd!=&cmd!=C&cmd!=a&cmd!=AJ;cf(cmd=ecmd=C)叱请输

12、入你所要创建的二叉树的结点的值，以-/结束：n, noot=cneateBST(); do (flag=0；叱Mn中序遍历二叉树:edcnondet_bttee(noot);eoatVnVVendl;cou(tt*请选择你要对这棵二叉树所做的操 作：end/.coutlt*endl;eoutt*S查找你想要寻找的结点*edeoutt*I插入你想要插入的结点*泓;eoutt*D删除你想要删除的结点*endl;eoutt*2结束对这棵二叉树的操作*edcoutlt*蛔;cout tt*endldo4(fag!=0)叱选择操作错误！请重新选择！ n;ffu战(sdn);saf(%c”,&cmd);f

13、lag+;Me(她!= S &cmd!= S &md!= i &cmd!=I &cmd!= d &cmd!2 &cmd!= q &md!= 2 ); swctch(emd)case s：case S：eootkey;teS=seawhBS7(noot,key);if(test=0)叱七对不起，你所查找的结点ykey不存在尸；else如七成功找到结点n绍”,break;case i:case I:站TVV请输入你要插入结点的关键字：n,cinkey;noot=cnsentBST(noot,key); /注意必须将值传回根break;case d: case Dcoot输入你要删除结点的关键字：W

14、, cinkey;noot=deleteBST(noot,key); /注意必须将值传回根4(rot=NULL)翊七对不起，你所删除的结点”右”不存在A/,elsen成功删除结点key如。成功删除结点key;whde(cmd!=q&cmd!=2);whde(cmd!=q&cmd!=2);、we(cmd!=e&cmd!=E);、we(cmd!=e&cmd!=E);break;netum 0;实验内容3.4测试用例：/,程序运行时菜单显示如下:当输入的二叉树序列为：2,698,4时，创建二叉排序树，并输出结果如下:中序遍历二叉树:24&8请选择你要对这棵二叉树所做的操作*S.*I *D.*Q.-.

15、KJOCKJOCKKKKKKKKJCKJOCKJOOtJOOOCKKKKKKJCKJOCKJOOtJOOOCKKKKKKJCKKZ查找9结点时，运行结果如下:请选择你要对这棵二叉树所做的操作JC J JOC K JOC K作 占点占漆 结结结的 找A除叉 寻孺二 要要暮 想想想这 SS 查MKMMKMKMMXMKXMXMKXMXMMXMMMMXMMMMMMKMMXMKKMXMKXMXMKXKX2删除结点6时运行结果如下:D:Pr-ogram FilesMicrosoft Vrsual StudicMyPrqjject5yuesefuDebugyuese.1请输入你要删除结点的关键字，成功删除结

16、点6中序遍历二叉树;2489M-M-请选择你要对这棵二叉树所做的操作:WWWWWWMW想想想这对 找入鉴占5点占操 结结结的 w:的的树 找入除叉 寻S3二三插入结点7时运行结果如下:D:Pr-ogram FilesMicrosoft Visual StudicMyProjectsyuesefuDebLigyLiese.请输入你要插入结点的关键字:7中序遍历二叉树;2478XKJOCJOOOt请选择你要对这棵二叉树所做的操作作 占5点占操 结结结的 找A除叉 #1- 要要矗 想想想这 SS 找入纂rrr实验内容实验总结通过这次的实验，我认识到：仅仅掌握课本上的知识是不够的，在实际操作时，常常

17、遇到一些问题，自己看不懂，更无法解决。不过，经过自己不断的思考，尝试着去更改代 码中出现的问题。虽然开始很困难，但在老师和同学的帮助下，我逐渐的熟悉了许多操作， 为后继工作的顺利进行做了准备。个人的力量是薄弱的，我学会了咨询别人，不再胆怯，不再保守。 在过程中和同学 相互讨论，询问老师，不断进步。也许，我们可以说，编一个程仅仅是开始，调试和运行相比之下更难。实践中收获的 远比想象的多。看到自己完成了所要求的任务，有一种无法用言语来形容的欣慰之感，这也是无法从学 习书本知识中得到的。致谢本设计是在指导教师刘作军老师和寇海洲老师的亲切关怀和细心指导下完成的。刘作 军老师从设计方案的选定，设计计划的安排，都给予了精心的指导及严格的要求。寇海洲 老师在实验过程中给予了我们很大的支持与帮助。这个算法设计和报告的完成，凝结着两 位老师的心血和汗水。二位老师严谨的治学态度，开拓性的工作作风和科学的思维方法都 使我受益非浅。二位老师对我的设计和报告给予了莫大的关心和帮助，在此，我表示衷心 的感谢和诚挚的谢意。在设计过程中也得到了同学们的指点和帮助，特别是在编程中遇到技术性问题的时候， 同学的指点使我茅塞顿开，顺利的解决了问题。在此我表示诚挚的感谢。参考文献1.钱能舛+程序设计教程（修订版），北京：清华大学出