1、 数 据 结 构数 据 结 构 课 程 设 计 说 明 书课 程 设 计 说 明 书 题目: 遍历二叉树 院 系： 专业班级： 学 号： 学生姓名： 同 组 人： 指导教师： 年 月 日 遍历二叉树 1 目目 录录 一、 需求分析 2 1. 主功能模块. 2 2. 创建树模块. 2 3. 遍历树模块. 2 二、 概要设计 3 1. 功能设计 3 （1） 创建二叉树 3 （2） 先序递归遍历. 3 （3） 中序递归遍历. 3 （4） 后序递归遍历. 3 （5） 先序非递归遍历 . 3 （6） 中序非递归遍历 . 4 （7） 后序非递归遍历 . 4 （8） 层序非递归遍历 . 4 2. 算法流程图
2、. 4 三、 详细设计 12 1. 界面设计 12 2. 详细代码分析 . 14 （1） 主模块 . 14 （2） 创建树模块 15 （3） 遍历树模块 16 （4） 源程序清单 16 3. 调试分析 35 （1） 调试结果 35 （2） 算法分析 36 四、 心得体会 37 五、 参考文献 38 遍历二叉树 2 一、一、 需求分析需求分析 在现实世界层次化的数据模型中， 数据与数据之间的关系纷繁复杂。 其中很多关系无法 使用简单的线性结构表示清楚，比如祖先与后代的关系、整体与部分的关系等。于是人们借 鉴自然界中树的形象创造了一种强大的非线性结构树。树形结构的具体形式有很多种， 其中最常用的就
3、是二叉树。而二叉树的多层次遍历遍历则是二叉树的重要内容。 本程序用 Microsoft Visual C+ 6.0 编写，可以实现对二叉树的多种方式的创建、采 用递归和非递归等两种方式先序、中序、后序进行遍历。 1.1. 主功能模块主功能模块 通过合理的界面设计，根据提示信息，使用者可以方便快捷地运行本程序来完成创建、 遍历二叉树等操作。界面美观，人性化，程序智能，安全性高。 2.2. 创建树模块创建树模块 当进入程序运行界面后， 根据提示输入需要建立的二叉树， 共有三种方法来创建二叉树, 即：1：广义表构造法、2：先序和中序构造法、3：中序和后序构造法。建立完二叉树后自 动进入下一个功能模块
4、。 3.3. 遍历树模块遍历树模块 实现对该二叉树的先序递归遍历、先序非递归遍历、中序递归遍历、中序非递归遍历、 后序递归遍历、后序非递归遍历、层序非递归遍历等方式的遍历操作，并输出各遍历序列。 当对该二叉树进行层序非递归遍历时， 直接输出该树的逻辑结构图， 以便更直观地显示其层 次关系。 遍历二叉树 3 二、二、 概要设计概要设计 1.1. 功能设计功能设计 （1 1） 创创建二叉树建二叉树 利用二叉树模板类，创建二叉树时产生类模板，调用类的构造函数来创建，修改二叉树 的结构时，可以调用赋值语句直接把广义表转换成二叉树。相关类或函数如下： class BinaryTree; BinaryTr
5、ee(); BinaryTree （2 2） 先序递归遍历先序递归遍历 若二叉树为空，则空操作；否则（1）访问根结点； （2）先序遍历左子树； （3）先序遍 历右子树。相关函数如下： void PreOrderTraverse(const BinaryTreeNode* p) const; （3 3） 中序递归遍历中序递归遍历 若二叉树为空，则空操作；否则（1）中序遍历左子树； （2）访问根结点； （3）中序遍 历右子树。相关函数如下： void InOrderTraverse(const BinaryTreeNode* p) const; （4 4） 后序递归遍历后序递归遍历 若二叉树为空，
6、则空操作；否则（1）后序遍历左子树； （2）后序遍历右子树； （3）访 问根结点。相关函数如下： void PostOrderTraverse(const BinaryTreeNode* p) const; （5 5） 先序非递归先序非递归遍历遍历 若二叉树为空，则空操作；否则引入栈模拟递归工作栈，初始时栈为空。相关函数如 下： void PreOrderTraverse() const; 遍历二叉树 4 （6 6） 中序非递归遍历中序非递归遍历 若二叉树为空，则空操作；否则引入栈模拟递归工作栈，初始时栈为空。相关函数如 下： void InOrderTraverse() const; （7 7） 后序非递归遍历后序非递归遍历 若二叉树为空，则空操作；否则引入栈和标记模拟递归工作栈，初始时栈为空。相关 函数如下： void PostOrderTraverse() const; （8 8） 层序非递归遍历层序非递归遍历
