二叉排序树的操作课程设计报告

内蒙古科技大学本科生课程设计说明书题目：数据结构课程设计——二叉排序树的操作学生姓名：许闻杰学号：1467159228专业：软件工程班级：14级软件2班指导教师：周李勇日期：2016年1月8日内蒙古科技大学课程设计任务书课程名称数据结构课程设计设计题目二叉排序树的操作指导教师周李勇时间2016.1——2016.1一、教学要求1.掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。以二叉链表表示二叉排序树，在此基础上实现二叉排序树的操作。要求设计类（或类模板）来描述二叉排序树，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：创建二叉排序树输出二叉排序树在二叉排序树中查找给定值在二叉排序树中插入新结点在二叉排序树中删除给定值并设计主函数测试该类（或类模板）。三、设计要求及成果1.分析课程设计题目的要求2.写出详细设计说明3.编写程序代码，调试程序使其能正确运行4.设计完成的软件要便于操作和使用5.设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1.根据平时上机考勤、表现和进度，教师将每天点名和检查2.根据课程设计完成情况，必须有可运行的软件。3.根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4.根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1．《数据结构（C语言版）》严蔚敏、吴伟民主编清华大学出版社2004.112．《数据结构课程设计案例精编（用C/C++描述）》，李建学等编著，清华大学出版社2007.23.《数据结构:用面向对象方法与C++语言描述》，殷人昆主编，清华大学出版社2007.6目录内蒙古科技大学课程设计任务书I第一章需求分析31.1引言31.2任务概述31.3数据描述31.4功能需求31.5任务计划4第二章概要设计52.1总体设计52.2数据类型设计（或数据结构设计）52.3接口设计//函数声明52.4运行界面设计5第三章详细设计73.1输入模块设计73.2输出模块设计73.3查找模块设计7第四章测试分析84.1测试程序执行情况84.2出现的问题和解决的方法8第五章用户手册（可选）95.1使用说明95.2运行说明9第六章课程设计总结10附录：程序代码11参考文献12致谢13第一章需求分析.1引言二叉排序树的操作.2任务概述以二叉链表表示二叉排序树，在此基础上实现二叉排序树的操作。.3数据描述以二叉链表表示二叉排序树，在此基础上实现二叉排序树的操作。要求设计类（或类模板）来描述二叉排序树，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：ADTBT{数据对象root：先定义一个二叉树结点的结构体：typedefstructbst{chardata;structbst*left;structbst*right;structbst*father;}BSTree,*BST;root是指向二叉树结点的指针；.4功能需求创建二叉排序树输出二叉排序树在二叉排序树中查找给定值在二叉排序树中插入新结点在二叉排序树中删除给定值并设计主函数测试该类（或类模板）。.5任务计划主程序流程图算法：主程序主要用运了switch结构，使得主程序更加方便的调用成员函数，各个成员函数间的关系也清晰明了。输入与功能相对应的序号执行功能是否存在开始结束否是函数调用关系main主程序显示菜单创建根节点插入结点查找结点删除结点中序遍历二叉排序树第2章概要设计.1总体设计2二叉排序树34系统功能结构567退出删除二排序叉树结点设置二叉排序树根结点添加二排序叉树结点查找给定的二叉树结点输出二排序叉树891011121314151617系统的功能结构：设置二叉排序树根结点、添加二排序叉树结点、删除二排序叉树结点、查找给定的二叉树结点、输出二排序叉树、退出。功能说明：设置二叉排序树根结点：为新创建的二叉排序树创建根节点。添加二排序叉树结点：需要输入创建节点的数目，然后创建一定数目的二叉排序树结点。删除二排序叉树结点：给定一个数据(字母)，然后查找，找到后删除，否则，告知未找到，查找给定的二叉树结点：给定一个数据(字母)，然后查找，并给出提示。输出二排序叉树：按照先序遍历并输出二叉排序树的结点数据。退出：退出程序。2.2数据类型设计（或数据结构设计）ADTBT{数据对象root：先定义一个二叉树结点的结构体：typedefstructbst{chardata;structbst*left;structbst*right;structbst*father;}BSTree,*BST;root是指向二叉树结点的指针；数据关系：R={(V或者C)P(V或者C)|V,C∈D,(V或者C)P(V或者C)表示由运算符P结合起来的表达式E}基本操作：BSTInitRoot()操作结果：为空二叉排序树创建一个根节点，输入一个字符型数据，将这个字符型数据存入结点的数据域中同时给左右孩子指针和父指针置空，并返回一个结点的基址给指针。voidInserter(root,key)初始条件：二叉排序树不为空，存在根节点；操作结果：输入一个字符型数据，先寻找二叉排序树中是否有此数据，有则返回主菜单，没有则就二叉排序树的构造方法返回要插入旳数据应该插入位置的父节点地址，创建一个新结点，将这个字符型数据存入结点的数据域中，并将左右孩子指针置空，父指针指向父节点地址，然后返回主菜单。BSTree*SearchKey(root,key)初始条件：二叉排序树不为空，存在根节点；操作结果：输入一个字符型数据，先寻找二叉排序树中是否有此数据的，有则返回次数据项的地址给指针变量，没有则就返回该数据按照二叉排序树规则，应该插入位置的父节点地址。voidDeleteKey(root,key);初始条件：二叉排序树不为空，存在根节点；操作结果：输入一个字符型数据，调用BSTree*SearchKey(root,key)函数，先寻找二叉排序树中是否有此数据的，有则返回次数据项的地址给指针变量，然后就此节点的特征分为四类：删除叶子节点；删除只有右孩子的节点；删除只有左孩子的节点；删除左右孩子都有的节点，根据结点类型进入不同删除模块，删除结点，修改相应二叉树结点指针，返回主菜单；没有则就返回提示语句“没有找到该数据”。voidChainTree_LDR(root)初始条件：二叉排序树不为空，存在根节点；操作结果：按照中序遍历并输出有序的数据序列。}ADTBTBT抽象数据类型的设计classBT{private:BSTroot;public:BT():root(NULL){}BSTInitRoot();voidInserter(BSTree*t,charkey);BSTree*SearchKey(BSTree*t,charkey);voidDeleteKey(BSTree*t,charkey);voidChainTree_LDR(BSTree*bt);};第3章详细设计.1输入模块设计BSTree*BT::InitRoot(){BSTnode;if(node=newBSTree){cout输入根节点的数据:;cinnode-data;node-left=NULL;node-right=NULL;node-father=NULL;returnnode;}}//初始化根节点.2添加模块设计if(root==NULL){cout空树!!!禁止操作!!!;coutendl;}else{cout请输入你要添加的结点数目:;cinn;fflush(stdin);for(i=0;in;i++){cout请输入你要添加的结点数据:;cinkey;a.Inserter(root,key);fflush(stdin);}}.3输出模块设计coutendl;if(root==NULL){cout空树!!!禁止操作!!!;coutendl;}else{a.ChainTree_LDR(root);coutendl;}break;.4查找模块设计BSTree*key;cout请输入你要查找的结点数据:;fflush(stdin);cinkey2;key=a.SearchKey(root,key2);if(key-data==key2){cout二叉树中有此数据!!!;coutendl;}else{cout二叉树中没有此数据!!!;coutendl;排序模块设计.5删除模块设计if(root==NULL){cout空树!!!禁止操作!!!;coutendl;}else{cout请输入你要删除的结点数据:;fflush(stdin);cinkey1;a.DeleteKey(root,key1);coutendl;}第4章测试分析.1测试程序执行情况主界面：设置二叉排序树根节点：在主界面输入1，进入“设置二叉排序树根节点”功能，按提示输入根节点数据，结束到主界面。添加二叉排序树结点：在主界面时，输入2，进入“添加二叉排序树结点”功能。先进行判空操作，若二叉排序树为空，给出提示：否则按提示输入要添加的结点数目，并依此添加节点数据：输出二叉排序树：在主界面时，输入5。先进行判空操作，若二叉排序树为空，给出提示：否则中序遍历并输出二叉排序树：删除二叉排序树结点：在主界面，输入3，进入删除界面。先进行判空操作，若二叉排序树为空，给出提示否则按照提示输入要删除的结点数据：（1）若输入数据在二叉排序树中不存在：（2）若输入数据在二叉排序树中存在，则删除：（如图所示结点l已删除）查找给定二叉排序树结点：在主界面，输入4，进入查找界面。先进行判空操作，若二叉排序树为空，给出提示：按照提示输入要查找的结点数据：（1）若存在：（2）若不存在退出程序：在主界面，输入0，退出程序；.2出现的问题和解决的方第5章课程设计总结数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且也已经成为其他理工专业的热门选修课。随着高级语言的发展，数据结构在计算机的研究和应用中已展现出强大的生命力，它兼顾了诸多高级语言的特点，是一种典型的结构化程序设计语言，它处理能力强，使用灵活方便，应用面广，具有良好的可移植性。每一处编码都是在反复的熟悉数据结构的结构特性，及其语法、函数和程序设计思想的过程，对数据结构的学习和提高很有益处，并且使我明白了程序设计过程，如解决一些实际问题，从解决实际问题的角度，我可以这样来看：第一要了解这个问题的基本要求，即输入、输出、完成从输入到输出的要求是什么；第二，从问题的要害入手，从前到后的解决问题的每个方面，即从输入开始入手，着重考虑如何从输入导出输出，在这个过程中，可确定所需的数据结构的基本类型——线性表、栈、队列、串、数组、广义表、树和二叉树以及图等，然后确定处理过程——算法，通过在编译环境中的编译与调试，可到最终的程序。最后，在这次课设的过程中，我深刻的认识到了自己在学习方面的不足之处，我知道我还有太多的基本的思想没有真正的理解，当然我不会灰心，会在以后的日子里努力弥补不足。附录：程序代码#includestdio.h#includestdlib.h#includeprocess.h#includeiostream#includeiomanipusingnamespacestd;typedefstructbst{chardata;structbst*left;structb