数据结构课程设计-二叉排序树的实现.doc

课 程 设 计 说 明 书课程名称： 数据结构 设计题目： 二叉排序树的实现 院 系： 学生姓名： 学 号： 专业班级： 指导教师： 2010年5月29日课 程 设 计 任 务 书设计题目二叉排序树的实现 姓名罗浩 院系计算机科学与信息工程系专业、年级、 班08软件工程1班设计要求：a) 以回车(n)为输入结束标志,输入数列l，生成一棵二叉排 序树t；b) 对二叉排序树t作中序遍历，输出结果；c) 输入元素x,查找二叉排序树t,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；学生应完成的工作：1、按设计要求完成各项任务。2、测试数据及测试结果在上交的资料中写明，必须上机调试通过。l3、按数据结构课程设计大纲中的要求完成课程设计报告格式。4、设计结束后，上交如下材料：1）课程设计报告打印稿一份 2）课程设计的源代码电子文档一份参考文献阅读：1 李春葆 尹为民 李蓉蓉 蒋晶鈺 喻丹丹.数据结构教程上机实验指导.2 谭浩强.c程序设计教程3唐宁九 游洪跃 朱宏.数据结构与算法（c+版） 工作计划：共计一周时间，进度安排如下：1 选题，在上机实验之前看透设计要求，翻阅资料完成程序设计大致提纲 。2 选好题，上级编写程序（需求分析、概要设计） 。3 填写算法，实现设计要求的各项功能（详细设计） 。4. 调试和分析，最终完成较合理的程序设计 。5. 按数据结构课程设计大纲中的要求完成课程设计报告格式。任务下达日期： 2010 年 5 月 27 日 任务完成日期： 2010 年 6 月 3 日指导教师（签名）： 学生（签名）：罗浩（设计题目）摘 要：设计一个程序，根据任一数列生成一棵二叉排序树；实现基本的遍历方法；查询结点并删除结点且保证仍为二叉排序树。具体要求：用顺序和二叉链表作存储结构,输入数列l，以回车(n)为输入结束标志生成一棵二叉排序树t；对二叉排序树t作中序遍历，输出结果；输入元素x,查找二叉排序树t,若存在含x的结点,则删除该结点,否则输出信息“无x”。 根据二叉排序树的概念，查找当前插入的元素的位置；删除结点如果不是叶子结点，要注意考虑如何使树仍为二叉排序树。关键词：二叉排序树，二叉链表，遍历，查询，删除目 录1. 设计背景41.1 问题的提出41.2 任务与分析42.设计方案42.1整体设计方案43. 方案实施53.1主程序模块设计方案53.2初始化模块设计方案51）.实现二叉树的初始化52）. 创建一棵二叉树：63.3中序遍历模块设计方案：73.4 查找并删除元素模块设计方案81) 查找元素x：82) 删除元素x：83.5 主函数设计方案104. 结果与结论114.1结果演示114.2结果演示125. 收获与致谢125.1总结：125.2致谢：136. 参考文献137. 附件137.1源程序：131. 设计背景1.1 问题的提出根据自己的知识功底和能力水平，选择二叉排序树的实现问题。而随着计算机发展并逐渐成为各行业不可缺少的东西，数据结构与算法包含计算机科学与技术的许多重要方面，对训练学生编出质量高、风格好的程序，又语言的发展，c+已成为用处最为广泛的语言。该设计运用数据结构知识，利用c+编写，来锻炼和提高我自己的编程及独立解决问题的能力，故选较为基础，但知识点广泛的题目。1.2 任务与分析 任务是一个二叉排序树的实现问题，根据任一数列生成一棵二叉排序树；实现基本的遍历方法；查询结点并删除结点且保证仍为二叉排序树。根据二叉排序树的概念，查找当前插入的元素的位置；删除结点如果不是叶子结点，要注意考虑如何使树仍为二叉排序树。2.设计方案2.1整体设计方案此课题研究二叉排序树的实现，建立二叉排序树；中序遍历并显示遍历结果；输入元素x,查找x；若存在删除之，否则输出“无x”；然后再进行中序遍历输出遍历结果。为方便起见，画出流程图如图1：初始化模块createbst()中序遍历二叉排序树inorder()中序遍历二叉排序树inorder()查找元素xbstsearch()主程序模块图1该程图描述了主要程序及函数。3. 方案实施3.1主程序模块设计方案#include typedef int keytype;typedef char elemtype10;typedef struct tnodekeytype key;elemtype data;struct tnode *lchild,*rchild;bstnode;定义全局变量、分配储存空间。3.2初始化模块设计方案1）.实现二叉树的初始化bstnode *creatbst(keytype a,int n)/由数组中的关键字建立一棵二叉排序树bstnode *bt=null; /初始时bt为空树int i=0;while(ikey=k)return(0);f=p;/*f指向*p结点的双亲结点*/if (p-keyk)p=p-lchild;/*在左子树中查找*/elsep=p-rchild;/*在右子树中查找*/p=new bstnode;/*建立新结点*/p-key=k;p-lchild=p-rchild=null;if (bt=null)/*原树为空时,*p作为根结点插入*/bt=p;else if (kkey)f-lchild=p;/*插入*p作为*f的左孩子*/elsef-rchild=p;/*插入*p作为*f的右孩子*/return(1);void createbst(bstnode *&bt,keytype str,int n)bt=null; /*初始时bt为空树*/int i=0;while (ilchild);coutkeyrchild);3.4 查找并删除元素模块设计方案1) 查找元素x：bstnode *bstsearch(bstnode *bt,keytype k)bstnode *p=bt;while (p!=null & p-key!=k)if (kkey) p=p-lchild; /*沿左子树查找*/else p=p-rchild; /*沿右子树查找*/return(p);2) 删除元素x：int bstdelete(bstnode *&bt,keytype k)bstnode *p=bt,*f,*r,*f1;f=null;/*p指向待比较的结点,f指向*p的双亲结点*/while (p!=null & p-key!=k)/*查找值域为x的结点*/f=p;if (p-keyk) p=p-lchild;/*在左子树中查找*/elsep=p-rchild;/*在右子树中查找*/if (p=null)/*未找到key域为k的结点*/return(0);else if (p-lchild=null) /*p为被删结点,若它无左子树*/if (f=null)/*p是根结点,则用右孩子替换它*/bt=p-rchild;else if (f-lchild=p)/*p是双亲结点的左孩子,则用其右子替换它*/f-lchild=p-rchild;delete p;else if(f-rchild=p)/*p是双亲结点的右孩子,则用其右孩子替换它*/f-rchild=p-rchild;delete p;else if (p-rchild=null)/*p为被删结点,若它无右子树*/if (f=null)/*p是根结点,则用左孩子替换它*/bt=p-lchild;if (f-lchild=p)/*p是双亲结点的左孩子,则用其左孩子替换它*/f-lchild=p-lchild;delete p;else if(f-rchild=p)/*p是双亲结点的右孩子,则用其左孩子替换它*/f-rchild=p-lchild;delete p;else/*p为被删结点,若它有左子树和右子树*/f1=p;r=p-lchild;/*查找*p的左子树中的最右下结点*r*/while (r-rchild!=null)/*r一定是无右子树的结点,*f1作为r的双亲*/f1=r;r=r-rchild;if (f1-lchild=r)/*r是*f1的左孩子,删除*r*/f1-lchild=r-rchild;else if (f1-rchild=r)/*r是*f1的右孩子,删除*r*/f1-rchild=r-lchild;r-lchild=p-lchild;/*以下语句是用*r替代*p*/r-rchild=p-rchild; if (f=null)/*f为根结点*/bt=r;/*被删结点是根结点*/else if (f-lchild=p)/*p是*f的左孩子*/f-lchild=r;else/*p是*f的右孩子*/f-rchild=r;delete p;return(1);3.5 主函数设计方案void main()int n;bstnode *bt=null,*p;keytype a200,k;cout n;cout 请输入数据:; for(int i=0;iai;createbst(bt,a,n);coutbst:; bstdisp(bt);coutendl;cout中序遍历二叉排序树:endl;inorder(bt);coutn;/cout先序遍历二叉排序树:;/preorder(bt);/coutn;coutk;p=bstsearch(bt,k);if(p!=null)bstdelete(bt,k);cout 已经删除值为k的结点endl;cout中序遍历二叉排序树:; inorder(bt);elsecout无kn;4. 结果与结论4.1结果演示（删除元素在二叉排序树中）运行结果如图2：4.2结果演示（删除元素不在二叉排序树中）运行结果如图3：5. 收获与致谢5.1总结：这几天的工作，终于完成了程序设计。可也遇到了不少问题，其中较为麻烦的是程序的调试。经过这几天的的上机实践和查阅资料 ，我变改变思路用c+编写，最终实现了所有要求。了虽然问题出现了不少，但收获也是颇丰：认识到自己的不足，要努力。解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；、 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 通过课程设计，提高了自己的编程能力。掌握了以往不太熟悉的知识，比如：c中的标准函数库、函数的调用及嵌套调用。通过实践的学习，我认识到学好计算机要重视实践操作，不仅仅是数据结构，还有其它的计算机方面的知识都要重在实践，以后在学习过程中，我会更加注重实践操作能力的培养，无论学习什么，亲自动手去做了才能有最深刻的体会。5.2致谢：首先需要感谢的是指导老师兼数据结构老师冯慧玲老师，在她的督促下我们按时完成这个课程设计，并且对于提出的各种问题很热情耐心的解答。没有她的教导自然就不可能有基础来完成课程设计了。还有整个完成的过程中我们小组齐心合力，经过翻阅资料、编程，调试最终完成了此次课程设计，大家都得到了应有的收获。6. 参考文献1 李春葆 尹为民 李蓉蓉 蒋晶鈺 喻丹丹.数据结构教程上机实验指导.2 谭浩强.c程序设计教程3唐宁九 游洪跃 朱宏.数据结构与算法（c+版）7. 附件7.1源程序：#include typedef int keytype;typedef char elemtype10;typedef struct tnodekeytype key;elemtype data;struct tnode *lchild,*rchild;bstnode;void bstdisp(bstnode *b);bstnode *bstsearch(bstnode *bt,keytype k)bstnode *p=bt;while (p!=null & p-key!=k)if (kkey) p=p-lchild; /*沿左子树查找*/else p=p-rchild; /*沿右子树查找*/return(p);int bstinsert(bstnode *&bt,keytype k)bstnode *f,*p=bt;while (p!=null)if (p-key=k)return(0);f=p;/*f指向*p结点的双亲结点*/if (p-keyk)p=p-lchild;/*在左子树中查找*/elsep=p-rchild;/*在右子树中查找*/p=new bstnode;/*建立新结点*/p-key=k;p-lchild=p-rchild=null;if (bt=null)/*原树为空时,*p作为根结点插入*/bt=p;else if (kkey)f-lchild=p;/*插入*p作为*f的左孩子*/elsef-rchild=p;/*插入*p作为*f的右孩子*/return(1);/*bstnode *creatbst(keytype a,int n)/由数组中的关键字建立一棵二叉排序树bstnode *bt=null; /初始时bt为空树int i=0;while(in)if(bstinsert(bt,ai) /将ai插入二叉排序树t中count 第i+1步，插入:ai;dispbst(bt); printf(n);i+;return bt; /返回建立的二叉排序树的根指针*/void createbst(bstnode *&bt,keytype str,int n)bt=null; /*初始时bt为空树*/int i=0;while (ikey!=k)/*查找值域为x的结点*/f=p;if (p-keyk) p=p-lchild;/*在左子树中查找*/elsep=p-rchild;/*在右子树中查找*/if (p=null)/*未找到key域为k的结点*/return(0);else if (p-lchild=null) /*p为被删结点,若它无左子树*/if (f=null)/*p是根结点,则用右孩子替换它*/bt=p-rchild;else if (f-lchild=p)/*p是双亲结点的左孩子,则用其右子替换它*/f-lchild=p-rchild;delete p;else if(f-rchild=p)/*p是双亲结点的右孩子,则用其右孩子替换它*/f-rchild=p-rchild;delete p;else if (p-rchild=null)/*p为被删结点,若它无右子树*/if (f=null)/*p是根结点,则用左孩子替换它*/bt=p-lchild;if (f-lchild=p)/*p是双亲结点的左孩子,则用其左孩子替换它*/f-lchild=p-lchild;delete p;else if(f-rchild=p)/*p是双亲结点的右孩子,则用其左孩子替换它*/f-rchild=p-lchild;delete p;else/*p为被删结点,若它有左子树和右子树*/f1=p;r=p-lchild;/*查找*p的左子树中的最右下结点*r*/while (r-rchild!=null)/*r一定是无右子树的结点,*f1作为r的双亲*/f1=r;r=r-rchild;if (f1-lchild=r)/*r是*f1的左孩子,删除*r*/f1-lchild=r-rchild;else if (f1-rchild=r)/*r是*f1的右孩子,删除*r*/f1-rchild=r-lchild;r-lchild=p-lchild;/*以下语句是用*r替代*p*/r-rchild=p-rchild; if (f=null)/*f为根结点*/bt=r;/*被删结点是根结点*/else if (f-lchild=p)/*p是*f的左孩子*/f-lchild=r;else/*p是*f的右孩子*/f-rchild=r;delete p;return(1);/先序遍历/*void preorder(bstnode *t) if(t!=0) coutkeylchild);preorder(t-rchild);*/中序遍历void inorder(bstnode *t) if(t!=0) inorder(t-lchild);coutkeyrchild);void bstdisp(bstnode *bt)if(bt!=null)coutkey;if(bt-lchild !=nu