(3). 后序遍历的非递归实现

由前面的讨论可知，后序遍历与先序遍历和中序遍历不同，在后序遍历过程中，结点在第一次出栈后，还需再次入栈，也就是说，结点要入两次栈，出两次栈，而访问结点是在第二次出栈时访问。因此，为了区别同一个结点指针的两次出栈，设置一标志flag，令
3. 由遍历序列恢复二叉树

从前面讨论的二叉树的遍历知道，任意一棵二叉树结点的先序序列和中序序列都是唯一的。反过来，若已知结点的先序序列和中序序列，能否确定这棵二叉树呢？这样确定的二叉树是否是唯一的呢？回答是肯定的。
根据定义，二叉树的先序遍历是先访问根结点，其次再按先序遍历方式遍历根结点的左子树，最后按先序遍历方式遍历根结点的右子树。这就是说，在先序序列中，第一个结点一定是二叉树的根结点。另一方面，中序遍历是中遍历左子树，然后访问根结点，最后再遍历右子树。这样，根结点在中序序列中必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，而后一个子序列是根结点的右子树的中序序列。根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。这样，就确定了二叉树的三个结点。同时，左子树和右子树的根结点又可以分别把左子序列和右子序列划分成两个子序列，如此递归下去，当取尽先序序列中的结点时，便可以得到一棵二叉树。

同样的道理，由二叉树的后序序列和中序序列也可唯一地确定一棵二叉树。因为，依据后序遍历和中序遍历的定义，后序序列的最后一个结点，就如同先序序列的第一个结点一样，可将中序序列分成两个子序列，分别为这个结点的左子树的中序序列和右子树的中序序列，再拿出后序序列的倒数第二个结点，并继续分割中序序列，如此递归下去，当倒着取取尽后序序列中的结点时，便可以得到一棵二叉树。

但是由一棵二叉树的前序序列和后序序列并不能唯一确定它。

4. 不用栈的二叉树遍历的非递归方法

常用的不用栈的二叉树遍历的非递归方法有以下三种：

(1). 对二叉树采用三叉链表存放，即在二叉树的每个结点中增加一个双亲域
parent，这样，在遍历深入到不能再深入时，可沿着走过的路径回退到任何一棵子树的根结点，并再向另一方向走。由于这一方法的实现是在每个结点的存储上又增加一个双亲域，故其存储开销就会增加。

(2). 采用逆转链的方法，即在遍历深入时，每深入一层，就将其再深入的孩
子结点的地址取出，并将其双亲结点的地址存入，当深入不下去需返回时，可逐级取出双亲结点的地址，沿原路返回。虽然此种方法是在二叉链表上实现的，没有增加过多的存储空间，但在执行遍历的过程中改变子女指针的值，这既是以时间换取空间，同时当有几个用户同时使用这个算法时将会发生问题。

(3). 在线索二叉树上的遍历，即利用具有n个结点的二叉树中的叶子结点和
一度结点的n＋1个空指针域，来存放线索，然后在这种具有线索的二叉树上遍历时，就可不需要栈，也不需要递归了。有关线索二叉树的详细内容，将在下一节中讨论。