이 진 트 리 의 자바 옮 겨 다 니 기 구현

1）      S.
2） root         
3）        S，   current = current-> left，  current NULL
4）  current NULL，      
     a）          。
     b）       ，  current = popped_item-> right 
     c）    3。
5）  current NULL，    ，    。

           1
          / \
        2    3
       / \
     4     5

  1        ：S = NULL

  2             ：current  - > 1

  3        ，   current = current-> left，  current NULL
     current - > 1
     Push 1：  S  - > 1
     current - > 2
     push 2：Stack S  - > 2，1
     current - > 4
     push 4：Stack S  - > 4，2，1
     current = NULL

  4  4 S   
     a）Pop 4：Stack S  - > 2，1
     b）  “4”
     c）current = NULL / *   4 * /     3
  current NULL， 3       。 

  4     。
     a）Pop 2：Stack S  - > 1
     b）  “2”
     c）current - > 5 / *   2 * /     3

  3 Push 5      NULL
       S  - > 5，1
     current = NULL

  4 S   
     a）Pop 5：Stack S  - > 1
     b）  “5”
     c）current = NULL / *  5 * /     3
  current NULL， 3       

  4    。
     a）Pop 1： S  - > NULL
     b）  “1”
     c）current - > 3 / *  5 * /  

  3 Push 3   ，     NULL
       S  - > 3
     current = NULL

  4 S   
     a）Pop 3： S  - > NULL
     b）  “3”
     c）current = NULL / *   3 * /  

      ，    S      NULL。 

// non-recursive java program for inorder traversal

/* importing the necessary class */
import java.util.Stack;

/* Class containing left and right child of current 
 node and key value*/
class Node {

    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

/* Class to print the inorder traversal */
class BinaryTree {

    Node root;

    void inorder() {
        if (root == null) {
            return;
        }

        //keep the nodes in the path that are waiting to be visited
        Stack stack = new Stack();
        Node node = root;

        //first node to be visited will be the left one
        while (node != null) {
            stack.push(node);
            node = node.left;
        }

        // traverse the tree
        while (stack.size() > 0) {

            // visit the top node
            node = stack.pop();
            System.out.print(node.data + " ");
            if (node.right != null) {
                node = node.right;

                // the next node to be visited is the leftmost
                while (node != null) {
                    stack.push(node);
                    node = node.left;
                }
            }
        }
    }

    public static void main(String args[]) {

        /* creating a binary tree and entering 
         the nodes */
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.inorder();
    }
}