构建一棵二叉排序树的C程序的设计[1]-(修复的)

1学号10212815213武汉华夏理工学院课程设计报告书课程名称：数据结构题目：构建一棵二叉排序树的C程序的设计系名：信息工程学院专业班级：软件1152姓名：李天宇指导教师:王绪梅2016年6月27日2课程设计任务书设计题目：构建一棵二叉排序树的C程序的设计设计目的1.巩固和加深课堂所学知识、学会分析研究数据对象的特性及数据的组织方法；2.选择的合适数据的逻辑结构和存储结构以及相应操作，实现二叉排序树的基本操作；3.提高程序设计能力、加强查阅、运用资料的能力、算法分析与程序设计素质培养；设计任务（在规定的时间内完成下列任务）〔问题描述〕建立一棵二叉排序树，并完成插入结点、按值查找结点位置和显示等功能。〔基本要求〕按二叉树的插入方法，形成二叉排序树主模块给出操作菜单，用函数实现不同功能在主函数中调用〔算法提示〕首先设定二叉树的二叉链表的存储结构：在建立二叉树时将每一个结点按左右子树的规定形成挂到树上；按二叉排序树的特点进行查找，按中序遍历的方法显示树中结点；具体要完成的任务是：A.编制完成上述问题的C语言程序、进行程序调试并能得出正确的运行结果。B.写出规范的课程设计报告书；时间安排：6月27日---7月1日第一天布置题目，确定任务、查找相关资料第二天～第四天功能分析，编写程序，调试程序、运行系统；第五天程序验收、答辩；撰写设计报告。具体要求1.课程设计报告按统一通用格式书写，具体内容如下：①设计任务与要求②总体方案与说明③软件主要模块的流程图④源程序清单与注释⑤问题分析与解决方案（包括调式报告，即在调式过程中遇到的主要问题、解决方法及改进设想）；⑥小结与体会附录：①源程序（必须有简单注释）②使用说明③参考资料2．每位学生应独立完成各自的任务且每天至少在设计室工作半天；指导教师签名：2016年6月25日教研室主任（或责任教师）签名：邱珊2016年6月25日3目录1实验目的与目标.....................................................................................42.问题分析..................................................................................................43.总体设计..................................................................................................54.具体设计..................................................................................................64.1递归查找算法................................................................................64.2非递归查找算法............................................................................74.3插入算法........................................................................................84.4二叉排序树的生成算法................................................................94.5中序遍历算法..............................................................................104.6删除算法......................................................................................104.7主函数...........................................................................................114.8注意事项：..................................................................................125.运行环境................................................................................................126.上机调试................................................................................................126.1语法错误及修改..........................................................................126.2程序输出调整：..........................................................................146.3时间和空间性能分析：..............................................................147.测试结果及分析...................................................................................158.用户使用说明.......................................................................................219.参考文献................................................................................................21附录...........................................................................................................2341实验目的与目标一、目的数据结构课程设计是学习了数据结构课后的一个综合性实践环节，是对课程学习的综合和补充。通过课程设计培养学生运用已学过的理论和技能去分析和解决实际问题的能力、加强学生的实践动手能力和创新能力。二、目标1、结合c和数据结构的理论知识，按要求独立设计方案，培养独立分析和解决实际问题的能力。加强学生的实践动手能力和创新能力。2、学会查阅资料，熟悉常用算法的用途与技巧。3、认真撰写课程设计报告，培养严谨的作风和科学态度。2.问题分析本次程序需要完成如下要求：首先输入任一组数据，使之构造成二叉排序树，并对其作中序遍历，然后输出遍历后的数据序列；其次，该二叉排序树能实现对数据（即二叉排序树的结点）的查找、插入和删除等基本操作。实现本程序需要解决以下几个问题：1、如何构造二叉排序树。2、如何通过中序遍历输出二叉排序树。3、如何实现多种查找。4、如何实现插入删除等操作。二叉排序树的定义：其左子树非空，则左子树上所有结点的值均小于根结点的值。若其右子树非空，则右子树上所有结点的值大于根结点的值。其左右子树也分别为二叉排序树。本问题的关键在于对于二叉排序树的构造。根据上述二叉排序树二叉排序树的生成需要通过插入算法来实现：输入（插入）的第一个数据即为根结点；继续插入，当插入的新结点的关键值小于根结点的值时就作为左孩子，当插入的新结点的关键值大于根结点的值时就作为右孩子；在左右子树中插入方法与整个二叉排序树相同。当二叉排序树建立完成后，要插入新的数据时，要先判断已建立的二叉排序树序列中是否已有当前插入数据。因此，插入算法还要包括对数据的查找判断5过程。本问题的难点在于二叉排序树的删除算法的实现。删除前，首先要进行查找，判断给出的结点是否已存在于二叉排序树之中；在删除时，为了保证删除结点后的二叉树仍为二叉排序树，要考虑各种情况，选择正确的方法。删除操作要分几种情况讨论，在后面有介绍。3.总体设计用二叉链表作为二叉排序树的存储结构，其中key为结点关键值，*lchlid、*rchild分别为左右孩子指针。该程序的流程图所示：NY开始输入节点值节点是否为0进入主菜单输入iI=0I=1I=2I=3I=4退出查找插入删除显示输入J=1递归查找J=22非递归查找6总流程图4.具体设计首先定义二叉排序树的数据类型如下：typedefstructnode{intkey;//关键字项structnode*lchild,*rchild;//左右孩子指针}Bstnode;然后按一定顺序来编写算法程序：44..11递递归归查查找找算算法法具体思想如下：（1）若二叉树为空，则查找失败。（2）否则，将根结点的关键值与待查关键字进行比较，若相等，则查找成功；若根结点关键值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤；若在查找过程的中遇到二叉排序树的叶子结点时，还没有找到待查结点，则查找不成功。if(t==NULL)returnNULL;else{if(t-data==x)returnt;if(xt-data)return(Bsearch(t-lchild,x));elsereturn(Bsearch(t-rchild,x));}7二叉排序树归查找算法流程图44..22非非递递归归查查找找算算法法查找过程是从根结点开始逐层向下进行的。并定义一个标记量记录是否找到结点。Bstnode*searchBST(Bstnode*t,intx){Bstnode*p;intflag=0;p=t;//定义*p结点用于逐层查找，丛根结点开始查找while(p!=NULL)//二叉排序树不为空{if(p-key==x)//查找成功{printf(该结点值存在!);flag=1;break;}//查找不成功，到下一层继续查找if(xp-key)p=p-lchild;//查找左子树elsep=p-rchild;//查找右子树}if(flag==0){printf(找不到值为%d的结点!,x);p=NULL;}returnp;8}YYN二叉排序树非递归查找算法流程图44..33插插入入算算法法从根结点开始，根据比较规则，逐一与待插入结点的值比较，查找到插入结点在二叉排序树中的未来位置，然后插入该结点。将一个关键字的值为x的结点s插入到二叉排序树中，方法如下：（1）若二叉排序树为空，则关键字值为x的结点s成为二叉排序树的根。（2）若二叉排序树非空，则将x与二叉排序树的根进行比较，如果x的值等于根结点关键字的值，则停止插入；如果x的值小于根结点关键字的值，则将x插入左子树；如果x的值大于根结点关键字的值，则将x插入右子树。在左右子树中插入方法与整个二叉排序树相同。Bstnode*InsertBST(Bstnode*t,intx)//插入关键值为x的元素{Bstnode*s,*p,*f;//*s为待插结点，*p为逐层查找结点，*f为待插结点的父结点p=t;while(p!=NULL){f=p;//查找过程中，f指向*p的父结点if(x==p-key)//若二叉树中已有关键值为x的元素，无需插入returnt;if(xp-key){p=p-lchild;}else{p=p-rchild;}}(p-key==x)查找成功下一层？p=p-lchild;p