二叉树的按层打印－Java

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击http://www.captainbed.net

package live.every.day.ProgrammingDesign.CodingInterviewGuide.BinaryTree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树的按层打印
 *
 * 【题目】
 * 给定一棵二叉树的根节点root，实现按层打印二叉树的函数。
 * 例如：
 *        5
 *      /  \
 *     2    8
 *   / \   / \
 *  1  3  7   6
 * 按层打印时，输出格式必须如下：
 * Level 1 : 5
 * Level 2 : 2 8
 * Level 3 : 1 3 7 6
 *
 * 【难度】
 * 中等
 *
 * 【解答】
 * 按层打印的实现。
 * 按层打印原本是十分基础的内容，对二叉树做简单的宽度优先遍历即可，但本题确有额外的要求，那就是同一层的节点必须打印在一行上，
 * 并且要求输出行号。这就需要我们在原来宽度优先遍历的基础上做一些改进。所以关键问题是如何知道该换行。只需要用两个Node类型的变
 * 量last和nLast就可以解决这个问题，last变量表示正在打印的当前行的最右节点，nLast表示下一行的最右节点。假设我们每一层都做
 * 从左到右的宽度优先遍历，如果发现遍历到的节点等于last，说明该换行了。换行之后只要令last=nLast，就可以继续下一行的打印过
 * 程，此过程重复，直到所有的节点都打印完。那么问题就变成了如何更新nLast？只需要让nLast一直跟踪记录宽度优先队列中的最新加入
 * 的节点即可。这是因为最新加入队列的节点一定是目前已经发现的下一行的最右节点。所以在当前行打印完时，nLast一定是下一行所有节
 * 点中的最右节点。
 * 按层打印的详细过程请参看如下代码中的print方法。
 *
 * @author Created by LiveEveryDay
 */

public class BinaryTreePrinterByLevel {

    private static class Node {
        public int data;
        public Node left;
        public Node right;

        public Node(int data) {
            this.data = data;
        }
    }

    public static void print(Node root) {
        if (root == null) {
            return;
        }
        Queue queue = new LinkedList<>();
        int level = 1;
        Node last = root;
        Node nLast = null;
        queue.offer(root);
        System.out.print("Level " + (level++) + " : ");
        while (!queue.isEmpty()) {
            root = queue.poll();
            System.out.print(root.data + " ");
            if (root.left != null) {
                queue.offer(root.left);
                nLast = root.left;
            }
            if (root.right != null) {
                queue.offer(root.right);
                nLast = root.right;
            }
            if (root == last && !queue.isEmpty()) {
                System.out.print("\nLevel " + (level++) + " : ");
                last = nLast;
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node node1 = new Node(5);
        Node node2 = new Node(2);
        Node node3 = new Node(8);
        Node node4 = new Node(1);
        Node node5 = new Node(3);
        Node node6 = new Node(7);
        Node node7 = new Node(6);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        print(node1);
    }

}

// ------ Output ------
/*
Level 1 : 5
Level 2 : 2 8
Level 3 : 1 3 7 6
*/