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

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

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

第一种:

??注意到，先序遍历的过程为“根左右”，后序遍历的过程为“左右根”，其后序遍历的逆过程为“根右左”，其后序遍历过程可以采用两个栈形式来进行实现，实现的过程中，第一个栈存放当前节点的左孩子节点和右孩子节点，而其得到的出栈结果为“根右左”，为此，我们只需要将入第一个栈的节点顺序调换以下(即先入右节点，再入左节点)即可得到“根左右”的出栈顺序，其具体步骤如下描述:

初始化一个栈和一个队列

push根节点入栈

从该栈中pop出其一节点，并将该节点加入到队列中

将该栈中pop出的节点的孩子节点，按照右孩子和左孩子的顺序push到该栈中

重复步骤2和步骤3直至栈为空

完成之后，所有的节点都push到该队列中，且按先序遍历的方式顺序存放，直接pop出队列中的节点，即为二叉树的先序遍历结果。

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

示意代码如下:

/**
 * 用于实现二叉树的非递归方式的先序遍历，方式1
 * @param root 二叉树的根节点
 */
public void PreRootTraverse(BinaryTreeNode root)
{
    BinaryTreeNode T=root;
    Stack s=new Stack();
    Queue q=new LinkedList();
    s.push(root);
    while(!s.isEmpty())
    {
        T=s.pop();
        q.push(T);
        if(T.rightChild!=null)
            s.push(T.rightChild);
        if(T.leftChild!=null)
            s.push(T.leftChild);
    }
    //用于得到先序遍历的结果
    while(!q.isEmpty())
    {
        System.out.println(((BinaryTreeNode)q.pop()).data);
    }
}

第二种:

??借助一个栈来记载当前被访问节点的右孩子节点，以便在遍历完一个节点的左子树后，能够顺利的进入这个节点的右子树进行遍历。从二叉树的根节点出发，沿着该节点的左子树向下搜索，在搜索过程中遇到一个节点就先访问该节点，并将该节点的非空右孩子节点压入栈中，当左子树访问完成之后,从栈顶弹出一个节点的右孩子节点，然后用上述同样的方法去遍历该节点的右子树，以此类推，直至二叉树中的所有节点都被访问了为止。其过程描述如下:

创建一个栈对象，根节点入栈

当栈为非空时，将栈顶节点弹出栈内并访问该节点

对当前访问节点的非空左孩子节点相继依次访问，并将当前访问节点的非空右孩子节点压入栈内

重复执行步骤2和3，直到栈为空为止

示例代码如下:

package queueandstack;
import java.util.Stack;
/**
 * 用于演示二叉树的遍历的三种方式的代码
 * @author 学徒
 *
 */
public class AroundTree
{
    /**
     * 用于实现二叉树的非递归方式的先序遍历，方式2
     * @param root 二叉树的根节点
     */
    public void PreRootTraverse(BinaryTreeNode root)
    {
        BinaryTreeNode T=root;
        if(T!=null)
        {
            Stack s=new Stack();
            s.push(T);//根节点入栈
            while(!s.isEmpty())
            {
                T=(BinaryTreeNode)s.pop();//移除栈顶节点，并返回其值
                System.out.println(T.data);//访问节点
                while(T!=null)
                {
                    if(T.leftChild!=null)//访问左孩子节点
                        System.out.println(T.leftChild.data);//访问节点
                    if(T.rightChild!=null)//右孩子非空入栈
                        s.push(T.rightChild);
                    T=T.leftChild;
                }
            }
        }
    }
}

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

??进行中序遍历可以借助一个栈来记载遍历过程中所经历的而未被访问过的所有节点，以便遍历完一个节点左子树后能顺利返回到它的父节点。实现中根遍历操作的非递归算法的主要思想是:从二叉树的根节点出发，沿着该节点的左子树向下搜索，在搜索过程中将所遇到的每一个节点依次压栈，直到二叉树中最坐下的的节点压栈为止，然后从栈中弹出栈顶节点并对其进行访问，访问完后再进入该节点的右子树并用上述的同样的方法去遍历该节点的右子树，以此类推，直到二叉树中的所有节点都被访问为止。

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