package arithmetic;

import java.util.Stack;

/**
 * 二叉树的 前中后 序遍历
 */
public class PrintNode {


    public static void main(String[] args) {
        Node n1 = new Node(1 + "");
        Node n2 = new Node(2 + "");
        Node n3 = new Node(3 + "");
        Node n4 = new Node(4 + "");
        Node n5 = new Node(5 + "");
        Node n6 = new Node(6 + "");
        Node n7 = new Node(7 + "");
        n1.left = n2;
        n1.right = n3;

        n2.left = n4;
        n2.right = n5;

        n3.left = n6;
        n3.right = n7;

        //先序遍历
        printFirst(n1);
        System.out.println();
        //后序遍历
        printEnd(n1);
        System.out.println();
        //中序遍历
        printMid(n1);

    }

    private static void printMid(Node n1) {
        if (n1 == null) return;
        Stack<Node> stack = new Stack<>();
        Node head = n1;
        while (!stack.isEmpty() || head != null) {
            if (head != null) {//head一直往左走，将左节点都压栈
                stack.push(head);
                head = head.left;
            } else {  //head==null，栈中取值打印，并往右走，进入下一个轮询
                head = stack.pop();
                head.print();
                head = head.right;
            }
        }
    }

    private static void printEnd(Node n1) {
        if (n1 == null) return;
        Stack<Node> stack = new Stack<>();
        Stack<Node> stack2 = new Stack<>();
        stack.push(n1);
        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            stack2.push(pop);
            if (pop.left != null) {
                stack.push(pop.left);
            }
            if (pop.right != null) {
                stack.push(pop.right);
            }
        }
        while (!stack2.isEmpty()) {
            stack2.pop().print();
        }
    }

    private static void printFirst(Node n1) {
        if (n1 == null) return;
        Stack<Node> stack = new Stack<>();
        stack.push(n1);
        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            pop.print();
            if (pop.right != null) {
                stack.push(pop.right);
            }
            if (pop.left != null) {
                stack.push(pop.left);
            }
        }
    }


    static class Node {
        Node left;
        Node right;
        String name;
        Node(String name) {
            this.name = name;
        }
        void print() {
            System.out.print(name + " ");
        }
    }
}