目录 一．选题背景 ..................................................... 1 二．问题描述 ..................................................... 1 三．概要设计 ..................................................... 2 3.1.创建二叉树 ................................................ 2 3.2.二叉树的非递归前序遍历示意图 .............................. 2 3.3.二叉树的非递归中序遍历示意图 .............................. 2 3.4.二叉树的后序非递归遍历示意图 .............................. 3 四．详细设计 ..................................................... 4 4.1 创建二叉树 ................................................ 4 4.2 二叉树的非递归前序遍历算法 ................................ 4 4.3 二叉树的非递归中序遍历算法 ................................ 5 4.4 二叉树的非递归后序遍历算法 ................................ 5 五．测试数据与分析 ............................................... 7 六．源代码 ....................................................... 7 总结............................................................ 11 参考文献: ....................................................... 12 1 一．选题背景 二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉链存储结构的每个结点包含三个域，分别是数据域，左孩子指针域，右孩子指针域。因此每个结点为 由二叉树的定义知可把其遍历设计成递归算法。共有前序遍历、中序遍历、后序遍历。 可先用这三种遍历输出二叉树的结点。 然而所有递归算法都可以借助堆栈转换成为非递归算法。以前序遍历为例，它要求首先要访问根节点，然后前序遍历左子树和前序遍历右子树。特点在于所有未被访问的节点中，最后访问结点的左子树的根结点将最先被访问，这与堆栈的特点相吻合。因此可借助堆栈实现二叉树的非递归遍历。将输出结果与递归结果比较来检验正确性。。 二．问题描述 对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。画出搜索顺序示意图。 leftchild data rightchild 2 三．概要设计 3 .1 .创建二叉树...
