二叉树的实现 K：二叉树的非递归遍历

??二叉树的三种遍历方式(先序遍历，中序遍历，后序遍历)的非递归实现，虽然递归方式的实现较为简单且易于理解，但是由于递归方式的实现受其递归调用栈的深度的限制，当递归调用的深度超过限制的时候，会出现抛出异常的情况。为此，通过显示的使用栈的方式来实现二叉树遍历的非递归方式，其在使用上会更加的灵活。

运用下图对二叉树的三种遍历方式进行介绍:

??所谓的后序遍历是指对一棵二叉树按照左子树，右子树，根节点的顺序递归的在一棵二叉树的左右子树中访问相关节点的方式。如图1.1所示的一棵二叉树，其后序遍历的结果为DEBCA

??实现非递归方式的后序遍历，有两种。

第一种:

??使用两个栈来进行实现。注意到，后序遍历可以看做以下遍历过程的逆过程：先遍历某个节点，然后遍历其右孩子节点，再遍历其左孩子节点，该过程的逆过程，即为后序遍历的遍历过程。如图:

为此，我们可以按照如下的算法得到二叉树的后序遍历结果:

初始化两个栈，一个用于保存中间遍历过程称为栈s，一个用于保存最终的结果称为栈output

push根节点到第一个栈s中

从第一个栈s中pop出一节点，并将其push到第二个栈output中

将第一个栈s中pop出的节点的孩子节点，按左孩子，右孩子的顺序push到第一个栈s中

重复步骤3和4直到栈s为空

栈s为空时，所有节点都已push到栈output中，且按后序遍历顺序存放，依次将栈output的节点pop出并进行访问，即为二叉树后序遍历的结果

以图1.1为例，其过程如下:

示例代码如下：

/**
 * 用于实现二叉树的非递归方式的后序遍历，方式1
 * @param root 二叉树的根节点
 */
public void PostRootTraverse(BinaryTreeNode root)
{
    BinaryTreeNode T=root;
    Stack s=new Stack();
    Stack output=new Stack();
    s.push(root);
    //用于执行压入栈的过程
    while(!s.isEmpty())
    {
        T=s.pop();
        output.push(T);
        if(T.leftChild!=null)
            s.push(T.leftChild);
        if(T.rightChild!=null)
            s.push(T.rightChild);
    }
    //用于执行对遍历结果的每个节点的访问过程
    while(!output.isEmpty())
    {
        System.out.println(((BinaryTreeNode)output.pop()).data);
    }
}

第二种:

??使用一个栈来进行实现，在搜索遍历的过程中，从二叉树的根节点出发，沿着该节点的左子树向下搜索，在搜索的过程中每遇到一个节点判断该节点是否是第一次经过，若是，则不立即访问，而是将该节点入栈保存，遍历该节点的左子树。当左子树遍历完毕后再返回该节点，这时还不能立即访问该节点，而是应当继续进入该节点的右子树进行遍历，当左右子树均遍历完毕后，才能从栈顶弹出该节点并访问它。由于在决定栈顶节点是否能访问时，需要知道该节点的右子树是否已经被遍历完毕。二叉树的实现因此，为解决这个问题，在算法中还应当引入一个布尔型的访问标志变量flag和一个节点指针p。二叉树的实现其中flag用来标志当前栈顶节点是否被访问过，当值为true的时候，表示栈顶节点已被访问过，当值为false的时候，表示当前栈顶节点未被访问过，指针p指向当前遍历过程中最后一个访问的节点。若当前栈顶节点的右孩子节点是空，或者就是p指向的节点，则表明当前节点的右子树已遍历完毕，此时就可以访问当前栈顶节点。其操作的实现过程描述如下:

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-59017-1.html