非递归实现二叉树遍历

import java.util.Stack;

import java.util.Stack;

/**
 * 定义二叉树
 * */

class BinaryTreeNode {
int value;
    BinaryTreeNode left;
    BinaryTreeNode right;
public BinaryTreeNode() {
    }

public BinaryTreeNode(int val) {
this.value = val;
    }
}

public class Solution{
/** 非递归实现前序遍历 */
protected void nonRecursivePreorder(BinaryTreeNode root) {
        Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
if (root != null) {
            stack.push(root);
while (!stack.empty()) {
                root = stack.pop();
                visit(root);
if (root.right != null)
                    stack.push(root.right);
if (root.left != null)
                    stack.push(root.left);
            }
        }
    }

//非递归中序遍历
public void nonRecursiveInOrder(BinaryTreeNode root) {
        Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
        BinaryTreeNode current;
        current = root;
while ((current != null) || (!stack.empty())) {
if (current != null) {
                stack.push(current);
                current = current.left;
            } else {
                current = (BinaryTreeNode) stack.pop();
                visit(current);
                current = current.right;
            }
        }
    }

/**
 * 后序遍历递归定义：先左子树，后右子树，再根节点。
 *后序遍历的难点在于：需要判断上次访问的节点是位于左子树，还是右子树。
 *若是位于左子树，则需跳过根节点，先进入右子树，再回头访问根节点；
 *若是位于右子树，则直接访问根节点。
 */

public void nonRecursivePostOrder(BinaryTreeNode root){
if(root==null)
return;
        Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
//当前访问的结点
        BinaryTreeNode curNode;
//上次访问的结点，注意局部变量 需要手动初始化
        BinaryTreeNode  lastVisitNode = null;
        curNode = root;

//把currentNode移到左子树的最下边
while(curNode!=null){
            stack.push(curNode);
            curNode = curNode.left;
        }
while(!stack.empty()){
//弹出栈顶元素
            curNode = stack.pop();
//一个节点被访问的前提是：无右子树或右子树已被访问过
if(curNode.right!=null&&curNode.right!=lastVisitNode){
//当前节点入栈
                stack.push(curNode);
//进入右子树，且可肯定右子树一定不为空
                curNode = curNode.right;
while(curNode!=null){
//再走到右子树的最左边
                    stack.push(curNode);
                    curNode = curNode.left;
                }
            }else{
//访问
                visit(curNode);
//修改最近被访问的节点
                lastVisitNode = curNode;
            }
        } 
    }
/** 访问节点 */
public void visit(BinaryTreeNode node) {
        System.out.print(node.value + " ");
    }

public static void main(String[] args)
    {
        BinaryTreeNode root=new BinaryTreeNode(1);
        BinaryTreeNode left1=new BinaryTreeNode(2);
        BinaryTreeNode left2=new BinaryTreeNode(3);
        BinaryTreeNode right1=new BinaryTreeNode(4);
        BinaryTreeNode right2=new BinaryTreeNode(5);
//创建一棵树
        root.left=left1;
        left1.right=left2;
        root.right=right1;
        right1.right=right2;

        Solution test = new Solution();
        test.nonRecursivePreorder(root);
        System.out.println();
        test.nonRecursiveInOrder(root);
        System.out.println();
        test.nonRecursivePostOrder(root);
    }
}