数据结构课程设计报告_遍历叉树.docVIP

XXXX大学 《数据结构》课程设计 报 告 课题名称: 遍历二叉树 系 （院）: 专 业: 班 级: 组员姓名: 学 号: 指导教师: 开课时间: 学年 学期 摘要 树结构在客观世界中广泛存在, 如人类社会的族谱和各种社会组织机构都可用树形象表示. 树在计算机领域中也得到广泛应用, 如在编译源程序时, 可用树表示源程序的语法结构. 又如在数据库系统中, 树型结构也是信息的重要组织形式之一. 一切具有层次关系的问题都可用树来描述. 针对这样的问题, 我选择了二叉树的遍历作为我的课程设计主题, 编写程序, 实现对二叉树的遍历. 在本次课程设计中, 二叉树的建立使用了递归算法；在前序、中序和后续遍历的算法中则同时使用了递归与非递归的算法, 即在这些遍历算法的实现中使用了栈结构与队列结构, 提供了6种不同的遍历方式, 供使用者选择. 同时, 该程序具有输出层序遍历的功能, 层序遍历模块使用了非递归算法. 该程序基本实现了对二叉树的遍历, 对于递归与非递归算法, 我们应从实际应用中体验这些算法的优越性. 关键词: 层次关系, 二叉树建立, 递归与非递归, 遍历, 栈, 队列 目 录 一、 问题描述 1 二、 需求分析 1 2.1主功能模块 1 2.2创建树模块 1 2.3遍历树模块 1 三、 概要设计 2 3.1主界面设计思想流程图 2 3.2. 创建二叉树 2 3.2.1二叉树创建的思想 2 3.2.2二叉树创建的算法流程图 2 3.3.先序递归遍历 3 3.3.1先序递归遍历思想 3 3.3.2先序递归遍历的算法流程图 3 3.4.中序递归遍历 3 3.4.1中序递归遍历思想 3 3.4.2中序递归遍历的算法流程图 4 3.5.后序递归遍历 4 3.5.1后序递归遍历思想 4 3.5.2后序递归遍历的算法流程图 5 3.6.先序非递归遍历 5 3.6.1先序非递归遍历思想 5 3.6.2先序非递归遍历的算法流程图 6 3.7.中序非递归遍历 6 3.7.1中序非递归遍历思想 6 3.7.2中序非递归遍历的算法流程图 7 3.8.后序非递归遍历 7 3.8.1后序非递归遍历思想 7 3.8.2后序非递归遍历的算法流程图 8 3.9.层序非递归遍历 8 3.9.1层序非递归遍历思想 8 3.9.2层序非递归遍历的算法流程图 9 四、 详细设计 10 4.1界面设计 10 4.2.详细代码分析 11 4.2.1主模块 11 4.2.2创建树模块 12 4.2.3遍历树模块 13 五、 调试分析 13 5.1.调试结果 13 5.1.1实验数据 13 5.1.2创建树界面 14 5.1.3输出结果界面 14 5.2.算法分析 16 5.2.1时间复杂度 16 5.2.2空间复杂度 16 5.3.程序的不足 16 5.3.1程序不足之处 16 六、 心得体会 17 七、 参考文献 17 问题描述 建立二叉树, 层序、先序、中序、后序遍历.(用递归或非递归的方法都可以) 要求能够输入树的各个结点, 并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数. 需求分析 在现实世界层次化的数据模型中, 数据与数据之间的关系纷繁复杂. 其中很多关系无法使用简单的线性结构表示清楚, 比如祖先与后代的关系、整体与部分的关系等. 于是人们借鉴自然界中树的形象创造了一种强大的非线性结构——树. 树形结构的具体形式有很多种, 其中最常用的就是二叉树. 而二叉树的多层次遍历遍历则是二叉树的重要内容. 本程序用Microsoft Visual C++ 6.0编写, 可以实现对二叉树的创建、采用递归和非递归等两种方式先序、中序、后序进行遍历. 2.1主功能模块 通过合理的界面设计, 根据提示信息, 使用者可以方便快捷地运行本程序来完成创建、遍历二叉树等操作. 界面美观, 人性化, 程序智能, 安全性高. 2.2创建树模块 当进入程序运行界面后, 根据提示输入需要建立的二叉树, 按照先序次序输入各个结点的值, 完成二叉树的建立. 2.3遍历树模块 实现对该二叉树的先序递归遍历、先序非递归遍历、中序递归遍历、中序非递归遍历、后序递归遍历、后序非递归遍历、层序非递归遍历等方式