import java.util.Stack;

public class BinaryTree<E> {

    Node<E> root;

    public BinaryTree(E item) {
        super();
        this.root = new Node<>(item);
    }

    /**
     * 前序：中左右
     */
    public void preOrder() {
        System.out.println("前序遍历");
        Stack<Node<E>> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node<E> node = stack.pop();
            System.out.print(node.item + " ");
            if (node.rightChild != null) {
                stack.push(node.rightChild);
            }
            if (node.leftChild != null) {
                stack.push(node.leftChild);
            }
        }
        System.out.println();
    }

    /**
     * 中序：左中右 思路：压入当前节点，判断左孩子是否为空， 若为空，则弹出该节点，并打印，并以右孩子为当前节点，重复操作；
     * 若不为空，则以左孩子做当前节点，重复操作
     * 
     * 重复操作的意思是呢。。。就是压入堆栈，判断左孩子是否为空。。。
     */
    public void middleOrder() {
        System.out.println("中序遍历");
        Stack<Node<E>> stack = new Stack<>();
        Node<E> node = root;
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.leftChild;
            } else {
                node = stack.pop();
                System.out.print(node.item + " ");
                node = node.rightChild;
            }
        }
        System.out.println();
    }

    /**
     * 后序：左右中 思路：前序遍历是中左右，那么前序遍历反一下，就是中右左，再顺序颠倒过来一下，就是左右中，就成了后序遍历。
     * 所以思路就是，左右颠倒进行前序遍历，将节点压入新的栈里面，然后再遍历新的栈的元素，就搞定了
     */
    public void afterOrder() {
        System.out.println("后序遍历");
        Stack<Node<E>> stack = new Stack<>();
        Stack<Node<E>> stack2 = new Stack<>();
        Node<E> node = root;
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                stack2.push(node);
                // System.out.print(node.item + " ");
                node = node.rightChild;
            } else {
                node = stack.pop();
                node = node.leftChild;
            }
        }
        // System.out.println();
        // System.out.println("这才是真的后序遍历");
        while (!stack2.isEmpty()) {
            Node<E> n = stack2.pop();
            System.out.print(n.item + " ");
        }
        System.out.println();
    }

    public void preOrder2() {
        System.out.println("前序遍历");
        preOrder2(root);
        System.out.println();
    }

    public void middleOrder2() {
        System.out.println("中序遍历");
        middleOrder2(root);
        System.out.println();
    }

    public void afterOrder2() {
        System.out.println("后序遍历");
        afterOrder2(root);
        System.out.println();
    }

    private void preOrder2(Node<E> node) {
        if (node == null)
            return;
        System.out.print(node.item + " ");
        preOrder2(node.leftChild);
        preOrder2(node.rightChild);
    }

    private void middleOrder2(Node<E> node) {
        if (node == null)
            return;
        middleOrder2(node.leftChild);
        System.out.print(node.item + " ");
        middleOrder2(node.rightChild);
    }

    private void afterOrder2(Node<E> node) {
        if (node == null)
            return;
        afterOrder2(node.leftChild);
        afterOrder2(node.rightChild);
        System.out.print(node.item + " ");
    }

    private static class Node<E> {
        E item;
        Node<E> leftChild;
        Node<E> rightChild;

        public Node(E item) {
            this.item = item;
        }
    }

    /**
     * A / \ B C / \ / \ D E F G / \ / H I J 期望结果： 前序(中左右)：ABDHEICFGJ
     * 中序(左中右)：HDBEIAFCJG 后序(左右中)：HDIEBFJGCA
     */
    public static void main(String[] args) {
        BinaryTree<String> tree = new BinaryTree<String>("A");
        Node<String> nodeB = new Node<String>("B");
        Node<String> nodeC = new Node<String>("C");
        Node<String> nodeD = new Node<String>("D");
        Node<String> nodeE = new Node<String>("E");
        Node<String> nodeF = new Node<String>("F");
        Node<String> nodeG = new Node<String>("G");
        Node<String> nodeH = new Node<String>("H");
        Node<String> nodeI = new Node<String>("I");
        Node<String> nodeJ = new Node<String>("J");

        tree.root.leftChild = nodeB;
        tree.root.rightChild = nodeC;

        nodeB.leftChild = nodeD;
        nodeB.rightChild = nodeE;

        nodeC.leftChild = nodeF;
        nodeC.rightChild = nodeG;

        nodeD.leftChild = nodeH;
        nodeE.rightChild = nodeI;
        nodeG.leftChild = nodeJ;

        System.out.println("-----------递归实现------------");

        tree.preOrder2();
        tree.middleOrder2();
        tree.afterOrder2();

        System.out.println("-----------堆栈实现------------");

        tree.preOrder();
        tree.middleOrder();
        tree.afterOrder();
    }
}