C++课程设计-二叉树的应用.doc

课程设计报告书 二叉树的应用 2010-10 Hunan Normal University ELECTRONIC INFORMATION ENGINEERING DEPARTMENT 课程设计题目 二叉树的应用 指导教师姓名 指导老师职称 学生姓名 所属班级 任务要求 二叉树的中序、前序、后序的递归与非递归遍历算法，按层次遍历的非递归遍历算法的实现，应包含建树的实现，树与二叉树的转换的实现 主要实施步骤 构造二叉树，树以及相关的数据结构 建立二叉树 二叉树的不同遍历 树的遍历 树与二叉树的转换 届面的设计 结 论 通过这次的课程设计，进一步的加强了对二叉树及树的了解，尝试了 种新的建树的方法，通过类似于建查找二叉树：大的是兄弟，小的孩子来建树，这样不会限制树的维度，只根据于用户输入的数据来建，降低了用户输入的难度。 另外，也发现将二叉树用于其它的系统的数据存储，查找时会比较容易，以后可试着研究把二叉树作为一种有效的存储手段。 湖南师范大学工学院电子与信息工程系课程设计登记表 注：此表格内容中的任务要求为指导教师提供的课程设计要求，主要实施步骤是指课程设计的时间安排，结论是指通过课程设计得出的有关结论及课程设计不足之处或进一步开发方向。 目 录 1引言 4 1.1 课程设计目标 4 1.2编程工具（编程环境）介绍 4 1.3实施时间及主要实施步骤 4 2.需求分析 4 3系统总体设计 5 4数据结构设计 5 5详细设计与实现 6 5.1功能模块1 6 5.1.1详细设计 6 5.1.2算法流程 6 5.1.3界面设计及测试结果 7 5.2功能模块 8 5.2.1详细设计 8 5.2.2算法流程 8 5.2.3界面设计及测试结果 10 5.3功能模块 12 5.3.1详细设计 12 5.3.2算法流程 12 5.3.3界面设计及测试结果 14 6算法分析 15 7、测试结果 15 8结论 22 9参考文献 22 引言 课程设计目标 建树的实现 二叉树的中序、前序、后序的递归与非递归遍历算法的实现 按层次遍历的非递归遍历算法的实现 树与二叉树的转换的实现 编程工具（编程环境）介绍 在Windeow X P 下用的 Dev-c++ 4.9.9.2 编程工具 C++是一种静态数据类型检查的，支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。 实施时间及主要实施步骤 实施时间：9月13号—9月24号 主要实施步骤：1、构造二叉树，树以及相关的数据结构 2、建立二叉树 3、二叉树的不同的遍历 4、树的遍历 5、树与二叉树的转换 6、届面的设计 需求分析 本程序的功能是采用查找二叉树的方法建树，并对二叉树进行递归前序遍历、中序遍历和后序遍历，用栈实现非递归的前序、中序和后序遍历，还有对二叉树的层次遍历，以及树的建立，树的广度优先和深度优先遍历，树与二叉树的转换。 本程序要求用户以字符输入，以#结束输入，采用查找二叉树的方法建树。 本程序输出结果以用户要求为准，可打印出二叉树的递归与非递归的先序、中序和后序遍历以及层次遍历，还有树的广度优先和深度优先遍历以及树转换成二叉树后的先序遍历。 演示程序以用户与计算机对话的方式进行，即在计算机终端上显示提示信息后，由用户在键盘上输入相应动作的序号和相应的输入数据。 测试数据：第一组：j ld e b a h i u x f d h n 第二组：7 4 3 2 8 9 0 第三组：* ） （ ？ % ^ ! = + 系统总体设计 系统共分为三个模块：first,arytree,ntree first模块是作为与用户交流的第一个接口，通过它将选择是对树或二叉树进行操作。 arytree模块是对二叉树的全部操作，它又分为建树（maketree）模块、先序遍历（xianxu）模块、中序遍历（zhongxu）模块、后序遍历（houxu）模块、层次遍历（cenchi）模块，它们分别完成二叉树的建立，以及递归和非递归的先序遍历、中序遍历、后序遍历和层次遍历算法。 ntree模块是对树的全部操作，它又分为建树（makentree）模块、深度优先遍历（shendu）模块、广度优先遍历（guangdu）模块、树转换成二叉树（change）模块，它们分别完成树的建立，以及深度优先、广度优先和树转换成二叉树算法。 数据结构设计 二叉树的数据结构： 二叉树结点：JieDian:class data:char leftchild:JieDian