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

1、内蒙古科技大学课程设计说明书内蒙古科技大学本科生课程设计说明书题 目：数据结构课程设计 二叉排序树的操作 学生姓名： 许闻杰学 号：1467159228专 业：软件工程班 级：14级软件2班指导教师：周李勇日 期：2016年 1月 8 日34内蒙古科技大学课程设计任务书课程名称数据结构课程设计设计题目二叉排序树的操作指导教师周李勇时间2016.12016.1一、教学要求1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力4. 训练用系统的观点和

2、软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。以二叉链表表示二叉排序树，在此基础上实现二叉排序树的操作。要求设计类（或类模板）来描述二叉排序树，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：v 创建二叉排序树v 输出二叉排序树v 在二叉排序树中查找给定值v 在二叉排序树中插入新结点v 在二叉排序树中删除给定值 并设计主函数测试该类（或类模板）。三、设计要求及成果1. 分析课程设计题目的要求2. 写出详细设计说明3. 编写程序代码，调试程序使其能正确运行

3、4. 设计完成的软件要便于操作和使用5. 设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1. 根据平时上机考勤、表现和进度，教师将每天点名和检查2. 根据课程设计完成情况，必须有可运行的软件。3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4. 根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1数据结构 （c语言版）严蔚敏、吴伟民 主编 清华大学出版社 2004.112数据结构课程设计案例精编（用c/c+描述），李建学 等

4、编著，清华大学出版社 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附录：程

5、序代码11参考文献12致谢13第一章 需求分析1.1 引言二叉排序树的操作1.2 任务概述以二叉链表表示二叉排序树，在此基础上实现二叉排序树的操作。1.3 数据描述以二叉链表表示二叉排序树，在此基础上实现二叉排序树的操作。要求设计类（或类模板）来描述二叉排序树，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：adt bt数据对象root：先定义一个二叉树结点的结构体：typedef struct bstchar data;struct bst *left;struct bst *right;struct bst *father;bstree,*bst;root是指向二叉树结点

6、的指针；1.4 功能需求创建二叉排序树输出二叉排序树在二叉排序树中查找给定值在二叉排序树中插入新结点在二叉排序树中删除给定值 并设计主函数测试该类（或类模板）。1.5 任务计划主程序流程图算法：主程序主要用运了switch结构，使得主程序更加方便的调用成员函数，各个成员函数间的关系也清晰明了。输入与功能相对应的序号执行功能是否存在开始结束否是 函数调用关系main 主程序显示菜单创建根节点插入结点查找结点删除结点中序遍历二叉排序树第二章 概要设计2.1 总体设计二叉排序树34系统功能结构567退出删除二排序叉树结点设置二叉排序树根结点添加二排序叉树结点查找给定的二叉树结点输出二排序叉树8910

7、1112131415161718系统的功能结构：设置二叉排序树根结点、添加二排序叉树结点、删除二排序叉树结点、查找给定的二叉树结点、输出二排序叉树、退出。功能说明：l 设置二叉排序树根结点：为新创建的二叉排序树创建根节点。l 添加二排序叉树结点：需要输入创建节点的数目，然后创建一定数目的二叉排序树结点。l 删除二排序叉树结点：给定一个数据(字母)，然后查找，找到后删除，否则，告知未找到，l 查找给定的二叉树结点：给定一个数据(字母)，然后查找，并给出提示。l 输出二排序叉树：按照先序遍历并输出二叉排序树的结点数据。l 退出：退出程序。2.2 数据类型设计（或数据结构设计）adt bt数据对象r

8、oot：先定义一个二叉树结点的结构体：typedef struct bstchar data;struct bst *left;struct bst *right;struct bst *father;bstree,*bst;root是指向二叉树结点的指针；数据关系：r=|v,cd, 表示由运算符p结合起来的表达式e基本操作：bst initroot()操作结果：为空二叉排序树创建一个根节点，输入一个字符型数据，将这个字符型数据存入结点的数据域中同时给左右孩子指针和父指针置空，并返回一个结点的基址给指针。void inserter(root, key)初始条件：二叉排序树不为空，存在根节点；操

9、作结果：输入一个字符型数据，先寻找二叉排序树中是否有此数据，有则返回主菜单，没有则就二叉排序树的构造方法返回要插入旳数据应该插入位置的父节点地址，创建一个新结点，将这个字符型数据存入结点的数据域中，并将左右孩子指针置空，父指针指向父节点地址，然后返回主菜单。bstree *searchkey(root,key)初始条件：二叉排序树不为空，存在根节点；操作结果：输入一个字符型数据，先寻找二叉排序树中是否有此数据的，有则返回次数据项的地址给指针变量，没有则就返回该数据按照二叉排序树规则，应该插入位置的父节点地址。void deletekey(root,key);初始条件：二叉排序树不为空，存在根节

10、点；操作结果：输入一个字符型数据，调用bstree *searchkey(root,key)函数，先寻找二叉排序树中是否有此数据的，有则返回次数据项的地址给指针变量，然后就此节点的特征分为四类：删除叶子节点；删除只有右孩子的节点；删除只有左孩子的节点；删除左右孩子都有的节点，根据结点类型进入不同删除模块，删除结点，修改相应二叉树结点指针，返回主菜单；没有则就返回提示语句“没有找到该数据”。void chaintree_ldr(root)初始条件：二叉排序树不为空，存在根节点；操作结果：按照中序遍历并输出有序的数据序列。 adt btbt抽象数据类型的设计class btprivate:bst

11、root;public:bt() :root(null) bst initroot();void inserter(bstree *t,char key);bstree *searchkey(bstree *t,char key);void deletekey(bstree *t,char key);void chaintree_ldr(bstree *bt);第三章 详细设计3.1 输入模块设计bstree* bt:initroot()bst node;if(node=new bstree)coutnode-data;node-left=null;node-right=null;node-f

12、ather=null;return node;/初始化根节点3.2 添加模块设计if(root=null)cout空树!禁止操作!;coutendl;elsecoutn;fflush(stdin);for(i=0;in;i+)coutkey;a.inserter(root,key);fflush(stdin);3.3 输出模块设计coutendl;if(root=null)cout空树!禁止操作!;coutendl;elsea.chaintree_ldr(root);coutendl;break;3.4 查找模块设计bstree *key;coutkey2;key=a.searchkey(ro

13、ot,key2);if(key-data=key2)cout二叉树中有此数据!;coutendl;elsecout二叉树中没有此数据!;coutendl;排序模块设计3.5 删除模块设计if(root=null)cout 空树!禁止操作!;coutendl;elsecoutkey1;a.deletekey(root,key1);coutendl;第四章 测试分析4.1 测试程序执行情况主界面：设置二叉排序树根节点：在主界面输入1，进入“设置二叉排序树根节点”功能，按提示输入根节点数据，结束到主界面。添加二叉排序树结点：在主界面时，输入2，进入“添加二叉排序树结点”功能。先进行判空操作，若二叉排

14、序树为空，给出提示：否则按提示输入要添加的结点数目，并依此添加节点数据：输出二叉排序树：在主界面时，输入5。先进行判空操作，若二叉排序树为空，给出提示：否则中序遍历并输出二叉排序树：删除二叉排序树结点：在主界面，输入3，进入删除界面。先进行判空操作，若二叉排序树为空，给出提示否则按照提示输入要删除的结点数据：（1）若输入数据在二叉排序树中不存在：（2）若输入数据在二叉排序树中存在，则删除：（如图所示结点l已删除）查找给定二叉排序树结点：在主界面，输入4，进入查找界面。先进行判空操作，若二叉排序树为空，给出提示：按照提示输入要查找的结点数据：（1） 若存在：（2） 若不存在退出程序：在主界面，输

15、入0，退出程序；4.2 出现的问题和解决的方第五章 课程设计总结 数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且也已经成为其他理工专业的热门选修课。随着高级语言的发展，数据结构在计算机的研究和应用中已展现出强大的生命力，它兼顾了诸多高级语言的特点，是一种典型的结构化程序设计语言，它处理能力强，使用灵活方便，应用面广，具有良好的可移植性。 每一处编码都是在反复的熟悉数据结构的结构特性，及其语法、函数和程序设计思想的过程，对数据结构的学习和提高很有益处，并且使我明白了程序设计过程，如解决一些实际问题，从解决实际问题的角度，我可以这样来看：第一要了解这个问题的基本要求

16、，即输入、输出、完成从输入到输出的要求是什么；第二，从问题的要害入手，从前到后的解决问题的每个方面，即从输入开始入手，着重考虑如何从输入导出输出，在这个过程中，可确定所需的数据结构的基本类型线性表、栈、队列、串、数组、广义表、树和二叉树以及图等，然后确定处理过程算法，通过在编译环境中的编译与调试，可到最终的程序。最后，在这次课设的过程中，我深刻的认识到了自己在学习方面的不足之处，我知道我还有太多的基本的思想没有真正的理解，当然我不会灰心，会在以后的日子里努力弥补不足。附录：程序代码#include#include#include#include#includeusing namespace s

17、td;typedef struct bstchar data;struct bst *left;struct bst *right;struct bst *father;bstree,*bst;class btprivate:bst root;public:bt() :root(null) bt();bst initroot();void inserter(bstree *t,char key);bstree *searchkey(bstree *t,char key);void deletekey(bstree *t,char key);void chaintree_ldr(bstree *

18、bt);bstree* bt:initroot()bst node;if(node=new bstree)coutnode-data;node-left=null;node-right=null;node-father=null;return node;/初始化根节点void bt:inserter(bstree *t,char key)bstree *p,*parent,*head;if(!(p=new bstree)coutdata=key;p-left=null;p-right=null;p-father=null;head=t;while(head)parent=head;if(key

19、data)head=head-left;else if(keyhead-data)head=head-right;else if(key=head-data)cout该数据已存在!;break;if(keydata)parent-left=p;p-father=parent;else if(keyparent-data)parent-right=p;p-father=parent;bst bt:searchkey(bstree *t,char key)bstree *parent=null,*head;head=t;while(head)parent=head;if(key=head-data

20、)parent=head;break;else if(keydata)head=head-left;else if(keyhead-data)head=head-right;return parent;void bt:deletekey(bstree *t,char key)bstree *p=null,*q=null,*r=null;p=searchkey(t,key);if(p-data=key)if(p-left=null&p-right=null) /删除叶子节点if(p-father-left-data=key)r=p;p-father-left=null;else if(p-fat

21、her-right-data=key)p-father-right=null;free(p);elseif(p-left=null&p-right!=null)/删除只有右孩子的节点if(t-data=key)q=t;t-right-father=null;t=q-right;free(q);else if(p-father-left=p)q=p;p-right-father=p-father;p-father-left=p-right;free(q);else if(p-father-right=p)q=p;p-right-father=p-father;p-father-right=p-r

22、ight;free(q);elseif(p-left!=null&p-right=null)/删除只有左孩子的节点if(t-data=key)q=t;t-left-father=null;t=t-left;free(q);else if(p-father-left=p)q=p;p-left-father=p-father;p-father-left=p-right;free(q);else if(p-father-right=p)q=p;p-left-father=p-father;p-father-right=p-right;free(q);elseif(p-left!=null&p-rig

23、ht!=null)/删除左右孩子都有的节点bstree *b;q=p-right;while(q)b=q;q=q-left;p-data=b-data;if(b-right!=null)b-right-father=b-father;b-father-right=b-right;else if(b-right=null)b-father-right=null;free(b);else if(p-data!=key) coutleft);coutsetw(3)data;chaintree_ldr(bt-right);return;/先序递归遍历二叉树int main()system(color 0e);bt a;bstree *root=null;int select1,n,i;char key,key1,key2;docoutendl