import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Stac

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

/*
  Created by Flynnon on 17-2-25.
  对二叉树的递归定义、前序、后序、中序、层序遍历方法的归纳
 */

/**
 * 定义节点类
 * 为了简单就不定义getter/setter方法了
 */
class Node {
    public int value;
    public Node left;
    public Node right;

    public Node() {
        this(0);
    }

    public Node(int v) {
        this.value = v;
        this.left = null;
        this.right = null;
    }
}

/**
 * 对二叉树进行操作的工具类
 */
class PrintBinaryTree {

    //私有化构造函数
    private PrintBinaryTree(){
        throw new RuntimeException("该工具类不应该被实例化");
    }

    /**
     * 层序遍历二叉树（每一行从左到右，整体上从上到下）
     * 主要思路：利用队列先进先出的性质保存顺序
     * @param root 要遍历的二叉树的根节点
     */
    public static void levelTraversal(Node root) {
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            Node temp = q.poll();
            if (temp != null) {
                System.out.print(temp.value + "  ");
                q.add(temp.left);
                q.add(temp.right);
            }
        }
    }

    /**
     * 前序遍历二叉树（递归） root->left->right
     * @param root 要遍历的二叉树的根节点
     */
    public static void preOrderRec(Node root) {
        if (root == null) {
            return;
        }
        System.out.print(root.value + "  ");
        preOrderRec(root.left);
        preOrderRec(root.right);
    }

    /**
     * 前序遍历二叉树（非递归） root->left->right
     * 主要思路：利用栈保存未打印的节点，然后逐个出栈处理，在此过程中更新栈
     * @param root 要遍历的二叉树的根节点
     */
    public static void preOrderUnRec(Node root) {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        Node temp;
        while (!stack.empty()) {            //root==null时，只会空转一个循环，因此无需判断
            temp = stack.pop();
            if (temp != null) {
                System.out.print(temp.value + "  ");
                stack.push(temp.right);     //注意：这里的入栈顺序是先right后left
                stack.push(temp.left);      //     以保证从栈中取出时为先left后right
            }
        }
    }

    /**
     * 后序遍历二叉树（递归）
     * @param root 要遍历的二叉树的根节点
     */
    public static void postOrderRec(Node root) {
        if (root == null) {
            return;
        }
        postOrderRec(root.left);
        postOrderRec(root.right);
        System.out.print(root.value + "  ");
    }

    /**
     * 后序遍历二叉树（非递归） left->right->root
     * 主要思路：利用栈保存未打印的节点，然后逐个出栈，进行判断，并根据需要更新栈
     *         因为是处理完左右子树后，再处理根(回溯)，所以需要一个记录上一个被打印的节点的引用
     * @param root 要遍历的二叉树的根节点
     */
    public static void postOrderUnRec(Node root) {
        if (root == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        //cur:当前节点  pre:上一个被打印的节点
        Node cur, pre = null;
        while (!stack.empty()) {
            //查看（不是取出）栈顶的结点
            cur = stack.peek();
            //如果当前结点没有孩子结点（叶子节点）
            //或者孩子节点都已被打印过（这里不可能出现有两个子节点却只打印了其中一个的情况）
            //说明该打印当前节点了
            if ((cur.left == null && cur.right == null) ||
                    (pre != null && (pre == cur.left || pre == cur.right))) {
                System.out.print(cur.value + "  ");  //打印当前结点
                stack.pop();                         //被打印的节点（当前节点）出栈
                pre = cur;                           //更新pre的值
            } else {
                if (cur.right != null)          //若未轮到当前节点，将当前节点的右节子点、左子节点入栈
                    stack.push(cur.right);      //注意：这里的入栈顺序是先right后left
                if (cur.left != null)           //     以保证从栈中取出时为先left后right
                    stack.push(cur.left);
            }
        }
    }

    /**
     * 中序遍历二叉树（递归）
     * @param root 要遍历的二叉树的根节点
     */
    public static void inOrderRec(Node root) {
        if (root == null) {
            return;
        }
        inOrderRec(root.left);
        System.out.print(root.value + "  ");
        inOrderRec(root.right);
    }

    /**
     * 中序遍历二叉树（非递归） left->root->right
     * 主要思路：模拟递归的过程，将左子树节点不断的压入栈，直到左叶子，然后处理栈顶节点的右子树
     * @param root 要遍历的二叉树的根节点
     */
    public static void inOrderUnRec(Node root) {
        Stack<Node> stack = new Stack<>();
        Node cur = root;                    //纯粹是为了好看...JVM会优化
        while (cur != null || !stack.isEmpty()) {  //当root==null时，不会进入循环，因此无需判断
            while (cur != null) {           //从当前节点开始，从上到下将最左边的那一列节点入栈
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();              //取出栈顶的节点（该节点左节点为null，因此现在该打印它）
            System.out.print(cur.value + "  ");
            cur = cur.right;                //定位到已打印的节点的右子节点
        }
    }

    /**
     * 前序递归构造二叉树 root->left->right
     * @param scanner 输入流，用于读取节点值
     * @return 构造完成的二叉树的根节点
     */
    public static Node createTreeNode(Scanner scanner) {
        assert scanner!=null;
        Node root = null;                 //声明当前根节点
        int data = scanner.nextInt();
        if (data > 0) {                             //若当前节点存在（这里为了简单以负数为占位符）
            root = new Node(data);                  //使用其它顺序构造二叉树，只需更改这三句即可
            root.left = createTreeNode(scanner);
            root.right = createTreeNode(scanner);
        }
        return root;
    }
}

/**
 * 测试类
 */
public class BinaryTree{
    // 这里以节点值分别为1-7的满二叉树为例
    // 1 2 4 -1 -1 5 -1 -1 3 6 -1 -1 7 -1 -1
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Node root = PrintBinaryTree.createTreeNode(sc);
        sc.close();
        System.out.print("层序遍历:");
        PrintBinaryTree.levelTraversal(root);
        System.out.print("\n中序递归遍历:");
        PrintBinaryTree.inOrderRec(root);
        System.out.print("\n中序非递归遍历:");
        PrintBinaryTree.inOrderUnRec(root);
        System.out.print("\n前序递归遍历:");
        PrintBinaryTree.preOrderRec(root);
        System.out.print("\n前序非递归遍历:");
        PrintBinaryTree.preOrderUnRec(root);
        System.out.print("\n后序递归遍历:");
        PrintBinaryTree.postOrderRec(root);
        System.out.print("\n后序非递归遍历:");
        PrintBinaryTree.postOrderUnRec(root);
    }
}