给定一个二叉树，不使用递归按顺序打印节点。

/* 来自 N o w J a v a . c o m*/

import java.util.Stack;


public class InorderTraversal {

    public static class Node {

        Node left;

        Node right;

        int value;


        public Node(int value) {

            this.value = value;

        }

    }


    // Traverse tree iteratively. We do this by replicating the same process

    // done recursively using an explicit stack

    public static void traverse(Node n) {

        Stack<Node> s = new Stack<Node>();

        // Add the leftmost branch to the stack

        addLeftToStack(s, n);
/** 来自 n o w j a v a . c o m - 时代Java**/

        // While there are elements in the stack, pop and move the minimum

        // possible distance to the right

        while (!s.isEmpty()) {

            Node curr = s.pop();

            System.out.println(curr.value);


            // Add the right child and any of its left children to the stack

            addLeftToStack(s, curr.right);

        }

    }


    // As long as the current node has a left pointer, add it to the stack and 

    // continue

    private static void addLeftToStack(Stack<Node> s, Node n) {

        while (n != null) {

            s.push(n);

            n = n.left;

        }

    }


    /*

     * Sample test case

     * 

     *        8

     *     /     \

     *    4       12

     *   / \     /  \

     *  1   6   9   15

     *     /     \

     *    5      10

     * 

     * Should print:

     * 1

     * 4

     * 5

     * 6

     * 8

     * 9

     * 10

     * 12

     * 15

     */


    public static void main(String[] args) {

        Node n = new Node(8);

        n.left = new Node(4);

        n.left.left =