遍历二叉树课程设计

《遍历二叉树课程设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、遍历二叉树河南城建学院数据结构课程设计说明书题目:遍历二叉树　　　院系：计算机科学与工程系专业班级：0614082学号：061408263学生姓名：闫建明同组人：金强指导教师：张延红2010年6月25日38遍历二叉树目录一、需求分析21.主功能模块22.创建树模块23.遍历树模块2二、概要设计31.功能设计3（1）创建二叉树3（2）先序递归遍历3（3）中序递归遍历3（4）后序递归遍历3（5）先序非递归遍历3（6）中序非递归遍历4（7）后序非递归遍历4（8）层序非递归遍历42.算法流程图4三、详细设计121.界面设计122.详细代码分析14（1）主模块14（2）创建树模块

2、15（3）遍历树模块16（4）源程序清单163.调试分析35（1）调试结果35（2）算法分析36四、心得体会37五、参考文献3838遍历二叉树一、需求分析在现实世界层次化的数据模型中，数据与数据之间的关系纷繁复杂。其中很多关系无法使用简单的线性结构表示清楚，比如祖先与后代的关系、整体与部分的关系等。于是人们借鉴自然界中树的形象创造了一种强大的非线性结构——树。树形结构的具体形式有很多种，其中最常用的就是二叉树。而二叉树的多层次遍历遍历则是二叉树的重要内容。本程序用MicrosoftVisualC++6.0编写，可以实现对二叉树的多种方式的创建、采用递归和非递归等两种方式

3、先序、中序、后序进行遍历。1.主功能模块通过合理的界面设计，根据提示信息，使用者可以方便快捷地运行本程序来完成创建、遍历二叉树等操作。界面美观，人性化，程序智能，安全性高。2.创建树模块当进入程序运行界面后，根据提示输入需要建立的二叉树，共有三种方法来创建二叉树,即：1：广义表构造法、2：先序和中序构造法、3：中序和后序构造法。建立完二叉树后自动进入下一个功能模块。3.遍历树模块实现对该二叉树的先序递归遍历、先序非递归遍历、中序递归遍历、中序非递归遍历、后序递归遍历、后序非递归遍历、层序非递归遍历等方式的遍历操作，并输出各遍历序列。当对该二叉树进行层序非递归遍历时，直接

4、输出该树的逻辑结构图，以便更直观地显示其层次关系。38遍历二叉树一、概要设计1.功能设计（1）创建二叉树利用二叉树模板类，创建二叉树时产生类模板，调用类的构造函数来创建，修改二叉树的结构时，可以调用赋值语句直接把广义表转换成二叉树。相关类或函数如下：classBinaryTree;BinaryTree();BinaryTree&operator=(conststring&str);（2）先序递归遍历若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。相关函数如下：voidPreOrderTraverse(constBinary

5、TreeNode*p)const;（3）中序递归遍历若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。相关函数如下：voidInOrderTraverse(constBinaryTreeNode*p)const;（4）后序递归遍历若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。相关函数如下：voidPostOrderTraverse(constBinaryTreeNode*p)const;（5）先序非递归遍历若二叉树为空，则空操作；否则引入栈模拟递归工作栈，初始时栈为空。

6、相关函数如下：voidPreOrderTraverse()const;38遍历二叉树（1）中序非递归遍历若二叉树为空，则空操作；否则引入栈模拟递归工作栈，初始时栈为空。相关函数如下：voidInOrderTraverse()const;（2）后序非递归遍历若二叉树为空，则空操作；否则引入栈和标记模拟递归工作栈，初始时栈为空。相关函数如下：voidPostOrderTraverse()const;（3）层序非递归遍历按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。相关函数如下：voidLevelOrderTraverse()const;1.算法流程图开

7、始结束先序和中序构造法广义表中序和后序构造法图2-1创建而二叉树38遍历二叉树开始判断结点是否空访问根结点结束按前根遍历方式遍历左子树按前根遍历方式遍历左子树YN图2-2前序递归遍历38遍历二叉树开始判断结点是否空按中根遍历方式遍历左子树结束访问根结点按中根遍历方式遍历右子树YN图2-3中序递归遍历38遍历二叉树开始判断结点是否空按后根遍历方式遍历左子树结束按后根遍历方式遍历右子树访问根结点YN图2-4后序递归遍历38遍历二叉树开始申请一个STL栈stack<*>s判断结点是否空输出结点值p->datas.push(p)结点的值变为它的左