【参考答案】讨论3.4 如何用堆栈实现后序遍历的非递归程序

<p>(1)&nbsp;&nbsp; 借助堆栈实现前序遍历、中序遍历非递归程序的本质是利用堆栈模拟递归函数调用时的入栈和出栈过程。而前序遍历、中序遍历和后序遍历在递归函数执行时，结点（作为函数参数）的入栈和出栈过程是完全一样的。</p><p>(2)&nbsp;&nbsp; 前序遍历是在结点入栈时输出结点信息，然后开始分别对该结点左右子树的遍历；而在中序遍历中，结点出栈时表明刚完成对该结点左子树的遍历，此时可输出该结点信息。</p><p>(3)&nbsp;&nbsp; 后序遍历必须在左右子树均输出的情况下才能输出该结点。如果直接采用前序遍历、中序遍历的非递归程序，我们没法判别该结点的右子树什么时候遍历结束。为了能知道结点右子树什么时候遍历结束，可以在其左子树遍历结束（即该结点出栈）时，将该结点再次入栈，等到它再次出栈时就说明其右子树刚刚遍历完毕，此时可以输出该结点。</p><p>(4)&nbsp;&nbsp; 也就是在后序遍历的非递归过程中，可以让每个结点两次入出栈，第一次出栈说明其左子树已遍历完成，第二次出栈说明右子树也遍历完成，可以输出结点信息。为了区分到底是第几次入出栈，可以给每个入栈结点增加一个标记（也就需要采用结构，其中一个分量作为标记以区分第几次入出栈）。</p><p><br ></p>