import java.util.Stack;

public class PreOrder {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    //前序遍历
    public static void preOrder(Node node) {
        Stack<Node> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            node = stack.pop();
            System.out.print(node.value + " ");

            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    //中序遍历
    public static void inOrder(Node node) {
        Stack<Node> stack = new Stack<>();
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                node = stack.pop();
                System.out.print(node.value + " ");
                node = node.right;
            }
        }
    }

    //后序遍历
    public static void postOrder(Node node) {
    	// 辅助栈，类似于前序遍历压入节点，最后反转即可
        Stack<Node> help = new Stack<>();
        Stack<Node> stack = new Stack<>();
        stack.push(node);

        while (!stack.isEmpty()) {
            node = stack.pop();
            help.push(node);
            //这里和前序遍历不同，先将左节点压入栈，再压右节点
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        //将栈反转即得到后序遍历的结果
        while (!help.isEmpty()) {
            System.out.print(help.pop().value + " ");
        }
    }


    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(5);
        head.left.left = new Node(3);
        head.left.right = new Node(4);
        head.right.left = new Node(6);
        head.right.right = new Node(7);

//        preOrder(head);//1 2 3 4 5 6 7
        inOrder(head);//3 2 4 1 6 5 7
//        postOrder(head);//3 4 2 6 7 5 1
    }
}