/**
 * 二叉树的节点
 */
class BinaryTreeNode {
    int data;
    BinaryTreeNode left;
    BinaryTreeNode right;
}

/**
 * 二叉树
 */
class BinaryTree {
    BinaryTreeNode root;

    public BinaryTreeNode insert(int data) {
        BinaryTreeNode newNode = new BinaryTreeNode();
        newNode.data = data;
        newNode.left = null;
        newNode.right = null;
        return newNode;
    }

    /**
     * 先序遍历，即先访问根节点，再访问左子节点，最后访问右子节点
     * 使用递归实现
     * @param node 二叉树的根节点
     */
    public void preOrder(BinaryTreeNode node) {
        if (node != null) { // 如果节点不为空，就访问这个节点
            System.out.print(node.data + " "); // 访问节点的数据
            preOrder(node.left); // 递归访问左子节点的数据
            preOrder(node.right); // 递归访问右子节点的数据
        }
    }

    /**
     * 中序遍历，即先访问左子节点，再访问根节点，最后访问右子节点
     * 使用递归实现
     * @param node 二叉树的根节点
     */
    public void inOrder(BinaryTreeNode node) {
        if (node != null) { // 如果节点不为空，就访问这个节点
            inOrder(node.left); // 递归访问左子节点的数据
            System.out.print(node.data + " "); // 访问节点的数据
            inOrder(node.right); // 递归访问右子节点的数据
        }
    }

    /**
     * 后序遍历，即先访问左子节点，再访问右子节点，最后访问根节点
     * 使用递归实现
     * @param node 二叉树的根节点
     */
    public void postOrder(BinaryTreeNode node) {
        if (node != null) { // 如果节点不为空，就访问这个节点
            postOrder(node.left); // 递归访问左子节点的数据
            postOrder(node.right); // 递归访问右子节点的数据
            System.out.print(node.data + " "); // 访问节点的数据
        }
    }

    /**
     * 广度优先遍历，即按层次遍历
     * @param root 二叉树的根节点
     */
    public void widthFirst(BinaryTreeNode root) {
        if (root == null) { // 如果根节点为空，直接返回
            return;
        }
        BinaryTreeNode[] queue = new BinaryTreeNode[20]; // 一个队列，用于存储节点
        int rear = 0, front = 0; // rear 是队尾指针，front 是队首指针
        queue[rear++] = root; // 将根节点放入队列，队尾指针加一
        BinaryTreeNode n; // 用于存储从队列中取出的节点
        while (front < rear) { // 如果队首指针小于队尾指针，说明队列中还有节点
            n = queue[front]; // 取出队首的节点
            System.out.print(queue[front++].data + " "); // 输出这个节点的数据，同时队首指针加一，这样下一个被取出的就是下一个节点了
            if (n.left != null) queue[rear++] = n.left; // 如果这个节点有左子节点，将左子节点放入队列，队尾指针加一
            if (n.right != null) queue[rear++] = n.right; // 如果这个节点有右子节点，将右子节点放入队列，队尾指针加一
        }
        // 这样的遍历方式，可以保证每一层的节点都先被访问并被放进队列
        // 在这层被打印之后，这些节点的子节点（下一层）才会被放进队列
        // 这样就可以保证按层次遍历
    }

    /**
     * 广度优先遍历，即按层次遍历，每一层打印一行
     * @param root 二叉树的根节点
     */
    public void widthFirstLn(BinaryTreeNode root) {
        if (root == null) { // 如果根节点为空，直接返回
            return;
        }
        BinaryTreeNode[] queue = new BinaryTreeNode[20]; // 一个队列，用于存储节点
        int rear = 0, front = 0; // rear 是队尾指针，front 是队首指针
        queue[rear++] = root; // 将根节点放入队列，队尾指针加一
        int lvl = rear; // 用于记录当前层的最后一个节点的下标，用于换行
                        // 默认是 1，因为根节点只有 1 个，从 1 开始就是下一层了（正好也是刚将根节点放入队列后队尾指针的值）
        BinaryTreeNode n; // 用于存储从队列中取出的节点
        while (front < rear) { // 如果队首指针小于队尾指针，说明队列中还有节点
            n = queue[front]; // 取出队首的节点
            System.out.print(queue[front++].data + " "); // 输出这个节点的数据，同时队首指针加一，这样下一个被取出的就是下一个节点了
            if (n.left != null) queue[rear++] = n.left; // 如果这个节点有左子节点，将左子节点放入队列，队尾指针加一
            if (n.right != null) queue[rear++] = n.right; // 如果这个节点有右子节点，将右子节点放入队列，队尾指针加一
            if (front == lvl) { // 如果队首指针等于当前层的最后一个节点的下标，说明这一层已经遍历完了
                System.out.println(); // 打印一个换行
                lvl = rear; // 同时，目前的队尾指针的值就是下一层的最后一个节点的下标，因为下一层的节点都已经放入队列了
            }
        }
    }
}

public class TreeExample {
    public static void main(String[] args) {
        /*
         * 构建一个如下图所示的二叉树
         *         2
         *        / \
         *       /   \
         *      7     5
         *     / \     \
         *    2   6     9
         *      / \    /
         *     5   11 4
         */
        BinaryTree tree = new BinaryTree();
        tree.root = tree.insert(2);
        tree.root.left = tree.insert(7);
        tree.root.right = tree.insert(5);
        tree.root.left.left = tree.insert(2);
        tree.root.left.right = tree.insert(6);
        tree.root.left.right.left = tree.insert(5);
        tree.root.left.right.right = tree.insert(11);
        tree.root.right.right = tree.insert(9);
        tree.root.right.right.left = tree.insert(4);

        System.out.println("Pre-order traversal: ");
        tree.preOrder(tree.root);
        System.out.println();

        System.out.println("In-order traversal: ");
        tree.inOrder(tree.root);
        System.out.println();

        System.out.println("Post-order traversal: ");
        tree.postOrder(tree.root);
        System.out.println();

        System.out.println("Width-first traversal: ");
        tree.widthFirst(tree.root);
        System.out.println();

        System.out.println("Width-first traversal with line break: ");
        tree.widthFirstLn(tree.root);
        System.out.println();
    }
}