一、需求分析
在现实世界层次化的数据模型中，数据与数据之间的关系纷繁复杂。其中很多关系无法使用简单的线性结构表示清楚，比如祖先与后代的关系、整体与部分的关系等。于是人们借鉴自然界中树的形象创造了一种强大的非线性结构——树。树形结构的具体形式有很多种，其中最常用的就是二叉树。而二叉树的多层次遍历遍历则是二叉树的重要内容。
本程序用Microsoft Visual C++ 6.0编写，可以实现对二叉树的多种方式的创建、采用递归和非递归等两种方式先序、中序、后序进行遍历。
1.主功能模块
通过合理的界面设计，根据提示信息，使用者可以方便快捷地运行本程序来完成创建、遍历二叉树等操作。界面美观，人性化，程序智能，安全性高。
2.创建树模块
当进入程序运行界面后，根据提示输入需要建立的二叉树，共有三种方法来创建二叉树,即：1：
广义表构造法、2：先序和中序构造法、3：中序和后序构造法。建立完二叉树后自动进入下一个功能模块。
3.遍历树模块
    实现对该二叉树的先序递归遍历、先序非递归遍历、中序递归遍历、中序非递归遍历、后序递归遍历、后序非递归遍历、层序非递归遍历等方式的遍历操作，并输出各遍历序列。当对该二叉树进行层序非递归遍历时，直接输出该树的逻辑结构图，以便更直观地显示其层次关系。
二、概要设计
1.功能设计
（1）创建二叉树
利用二叉树模板类，创建二叉树时产生类模板，调用类的构造函数来创建，修改二叉树的结构时，可以调用赋值语句直接把广义表转换成二叉树。相关类或函数如下：
class BinaryTree;
BinaryTree();
BinaryTree<T>& operator=(const string& str);
（2）先序递归遍历
若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。相关函数如下：
void PreOrderTraverse(const BinaryTreeNode<T>* p) const;
（3）中序递归遍历
若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。相关函数如下：
void InOrderTraverse(const BinaryTreeNode<T>* p) const;
（4）后序递归遍历
若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。相关函数如下：
void PostOrderTraverse(const BinaryTreeNode<T>* p) const;
（5）先序非递归遍历
若二叉树为空，则空操作；否则引入栈模拟递归工作栈，初始时栈为空。相关函数如下：
void PreOrderTraverse() const;
（6）中序非递归遍历
若二叉树为空，则空操作；否则引入栈模拟递归工作栈，初始时栈为空。相关函数如下：
void InOrderTraverse() const;
（7）后序非递归遍历
若二叉树为空，则空操作；否则引入栈和标记模拟递归工作栈，初始时栈为空。相关函数如下：
void PostOrderTraverse() const;
（8）层序非递归遍历
按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。相关函数如下：
    void LevelOrderTraverse() const;
2.算法流程图
图2-1  创建二叉树
图2-2  前序递归遍历
图2-3  中序递归遍历
图2-4  后序递归遍历
图2-5  先序非递归遍历
图2-6  中序非递归遍历
图2-7  后序非递归遍历
图2-8  层序非递归遍历
三、详细设计
1.界面设计
图3-1  系统运行主界面
图3-2  创建二叉树界面
图3-3  某二叉树层序遍历界面
2.详细代码分析
（1）主模块
本模块定义了系统运行主界面的相关内容和相关操作函数，源代码如下：
int main()
{
    system("color A9");      //设置屏幕背景和字体颜
    cout<<endl<<endl<<endl<<endl<<endl;
>二叉树中序遍历非递归算法

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。