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();
    }

    /**
     * 中序：左中右 思路：壓入當(dāng)前節(jié)點(diǎn)尚骄，判斷左孩子是否為空穴肘， 若為空，則彈出該節(jié)點(diǎn)翼雀，并打印践付，并以右孩子為當(dāng)前節(jié)點(diǎn)悄蕾，重復(fù)操作拣凹；
     * 若不為空问词，則以左孩子做當(dāng)前節(jié)點(diǎn)督函，重復(fù)操作
     * 
     * 重復(fù)操作的意思是呢。激挪。辰狡。就是壓入堆棧，判斷左孩子是否為空垄分。搓译。。
     */
    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();
    }

    /**
     * 后序：左右中 思路：前序遍歷是中左右锋喜，那么前序遍歷反一下些己，就是中右左豌鸡，再順序顛倒過來一下，就是左右中段标，就成了后序遍歷涯冠。
     * 所以思路就是，左右顛倒進(jìn)行前序遍歷逼庞，將節(jié)點(diǎn)壓入新的棧里面蛇更，然后再遍歷新的棧的元素，就搞定了
     */
    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 期望結(jié)果： 前序(中左右)：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("-----------遞歸實(shí)現(xiàn)------------");

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

        System.out.println("-----------堆棧實(shí)現(xiàn)------------");

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