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

《构建一棵二叉排序树地C程序地设计[1]-(修复地).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、学号华夏理工学院课程设计报告书课程名称：数据结构题目：构建一棵二叉排序树的C程序的设计系名：信息工程学院专业班级：软件1152姓名：天宇指导教师:王绪梅2016年6月27日学号华夏理工学院课程设计报告书课程名称：数据结构题目：构建一棵二叉排序树的C程序的设计系名：信息工程学院专业班级：软件1152姓名：天宇指导教师:王绪梅2016年6月27日课程设计任务书设计题目：构建一棵二叉排序树的C程序的设计设计目的1.巩固和加深课堂所学知识、学会分析研究数据对象的特性及数据的组织方法；2.选择的合适数据的逻辑结构和存储结构以及相应操作，实现

2、二叉排序树的基本操作；3.提高程序设计能力、加强查阅、运用资料的能力、算法分析与程序设计素质培养；设计任务（在规定的时间完成下列任务）〔问题描述〕建立一棵二叉排序树，并完成插入结点、按值查找结点位置和显示等功能。〔基本要求〕按二叉树的插入方法，形成二叉排序树主模块给出操作菜单，用函数实现不同功能在主函数中调用〔算法提示〕首先设定二叉树的二叉链表的存储结构：在建立二叉树时将每一个结点按左右子树的规定形成挂到树上；按二叉排序树的特点进行查找，按中序遍历的方法显示树中结点；具体要完成的任务是：A.编制完成上述问题的C语言程序、进行程序调

3、试并能得出正确的运行结果。B.写出规的课程设计报告书；时间安排：6月27日---7月1日第一天布置题目，确定任务、查找相关资料第二天～第四天功能分析，编写程序，调试程序、运行系统；第五天程序验收、答辩；撰写设计报告。具体要求1.课程设计报告按统一通用格式书写，具体容如下：①设计任务与要求②总体方案与说明③软件主要模块的流程图④源程序清单与注释⑤问题分析与解决方案（包括调式报告，即在调式过程中遇到的主要问题、解决方法及改进设想）；⑥小结与体会附录：①源程序（必须有简单注释）②使用说明③参考资料2．每位学生应独立完成各自的任务且每天至

4、少在设计室工作半天；指导教师签名：2016年6月25日教研室主任（或责任教师）签名：邱珊2016年6月25日目录1实验目的与目标32.问题分析33.总体设计44.具体设计54.1递归查找算法54.2非递归查找算法64.3插入算法74.4二叉排序树的生成算法84.5中序遍历算法94.6删除算法94.7主函数104.8注意事项：115.运行环境116.上机调试116.1语法错误及修改116.2程序输出调整：136.3时间和空间性能分析：137.测试结果及分析148.用户使用说明209.参考文献20附录211实验目的与目标一、目的数据结

5、构课程设计是学习了数据结构课后的一个综合性实践环节，是对课程学习的综合和补充。通过课程设计培养学生运用已学过的理论和技能去分析和解决实际问题的能力、加强学生的实践动手能力和创新能力。二、目标1、结合c和数据结构的理论知识，按要求独立设计方案，培养独立分析和解决实际问题的能力。加强学生的实践动手能力和创新能力。2、学会查阅资料，熟悉常用算法的用途与技巧。3、认真撰写课程设计报告，培养严谨的作风和科学态度。2.问题分析本次程序需要完成如下要求：首先输入任一组数据，使之构造成二叉排序树，并对其作中序遍历，然后输出遍历后的数据序列；其次，

6、该二叉排序树能实现对数据（即二叉排序树的结点）的查找、插入和删除等基本操作。实现本程序需要解决以下几个问题：1、如何构造二叉排序树。2、如何通过中序遍历输出二叉排序树。3、如何实现多种查找。4、如何实现插入删除等操作。二叉排序树的定义：其左子树非空，则左子树上所有结点的值均小于根结点的值。若其右子树非空，则右子树上所有结点的值大于根结点的值。其左右子树也分别为二叉排序树。本问题的关键在于对于二叉排序树的构造。根据上述二叉排序树二叉排序树的生成需要通过插入算法来实现：输入（插入）的第一个数据即为根结点；继续插入，当插入的新结点的关键

7、值小于根结点的值时就作为左孩子，当插入的新结点的关键值大于根结点的值时就作为右孩子；在左右子树中插入方法与整个二叉排序树相同。当二叉排序树建立完成后，要插入新的数据时，要先判断已建立的二叉排序树序列中是否已有当前插入数据。因此，插入算法还要包括对数据的查找判断过程。本问题的难点在于二叉排序树的删除算法的实现。删除前，首先要进行查找，判断给出的结点是否已存在于二叉排序树之中；在删除时，为了保证删除结点后的二叉树仍为二叉排序树，要考虑各种情况，选择正确的方法。删除操作要分几种情况讨论，在后面有介绍。3.总体设计用二叉链表作为二叉排序树

8、的存储结构，其中key为结点关键值，*lchlid、*rchild分别为左右孩子指针。该程序的流程图所示：节点是否为0输入节点值开始N非递归查找J=22递归查找输入J=1显示删除插入查找退出I=2I=4I=3I=1I=0输入i进入主菜单Y总流程图4