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

创建一个栈对象，根节点进栈，p赋初始化值为null

若栈非空，则栈顶节点的非空左孩子相继进栈

若栈非空，查看栈顶节点，若栈顶节点的右孩子为空，或者与p相等，则将栈顶节点弹出栈并访问它，同时使p指向该节点，并置flag为true，否则，将栈顶节点的右孩子压入栈，并置flag的值为false

若flag值为true，则重复执行步骤3。否则，重复执行步骤2和3，直到栈为空为止。

示例代码如下:

package queueandstack;
import java.util.Stack;
/**
 * 用于演示二叉树的遍历的三种方式的代码
 * @author 学徒
 *
 */
public class AroundTree
{
    /**
     * 用于实现二叉树的非递归方式的后序遍历，方式2
     * @param root 二叉树的根节点
     */
    public void PostRootTraverse(BinaryTreeNode root)
    {
        BinaryTreeNode T=root;
        if(T!=null)
        {
            Stack s=new Stack();
            s.push(T);//根节点进栈
            boolean flag;//访问标记
            BinaryTreeNode p=null;//p指向刚被访问的节点
            while(!s.isEmpty())
            {
                while(s.peek()!=null)//将栈顶节点的左孩子相继入栈
                {
                    s.push(((BinaryTreeNode)s.peek()).leftChild);
                }
                s.pop();//空节点退栈
            }
            while(!s.isEmpty())
            {
                T=(BinaryTreeNode)s.peek();//查看栈顶元素
                if(T.rightChild==null||T.rightChild==p)
                {
                    System.out.println(T.data);//访问节点
                    s.pop();//移除栈顶元素
                    p=T;//p指向刚被访问过的节点
                    flag=true;//设置访问标记
                }
                else
                {
                    s.push(T.rightChild);//右孩子节点入栈
                    flag=false;//设置未被访问标记
                }
                if(!flag)
                    break;
            }
        }
    }
}

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