从上到下打印二叉树

略

题目：从上到下打印二叉树的每一个节点,同层的节点按照从左到右的顺序打印.例如:

    8   

  6   10 

5  7  9  11


输出为:8, 6, 10, 5, 7, 9, 11

分析

一眼看上去可能有点复杂,首先打印第一个节点8,然后打印8的左右节点6和10,最后需要打印6的左右子树和10的左右子树,那么问题就来了.打印10的时候需要记录6的左右子树以便10输出完毕后回到6的左子树5的上面.这个问题要如何解决呢?

我们可以用到一个队列,队列拥有先进先出的特性,当我们输入8时,我们让它的左右子树一次入队,然后出队操作,出队的结点进行打印并且出队的结点的左右子树进行入队.具体如下:

步骤	操作	队列
1	打印结点8	结点6,结点10
2	打印结点6	结点10,结点5,结点7
3	打印结点10	结点5,结点7,结点9,结点11
4	打印结点5	结点7,结点9,结点11
5	打印结点7	结点9,结点11
6	打印结点9	结点11
7	打印结点11

代码实现

public class Test {

    static Queue<BinaryTreeNode> queue = new LinkedList<>();

    public static void main(String[] args) {
        BinaryTreeNode node7 = new BinaryTreeNode(5,null,null);
        BinaryTreeNode node6 = new BinaryTreeNode(7,null,null);
        BinaryTreeNode node5 = new BinaryTreeNode(9,null,null);
        BinaryTreeNode node4 = new BinaryTreeNode(11,null,null);
        BinaryTreeNode node3 = new BinaryTreeNode(6,node7,node6);
        BinaryTreeNode node2 = new BinaryTreeNode(10,node5,node4);
        BinaryTreeNode node1 = new BinaryTreeNode(8,node3,node2);

        printFromTopToBottom(node1);

    }

    private static  void printFromTopToBottom(BinaryTreeNode node){
        if (node==null) return;
        queue.offer(node);
        while (queue.size()>0){
            System.out.print(queue.poll().getmValue()+"\t");
            if (node.getmLeftNode() != null){
                printFromTopToBottom(node.getmLeftNode());
            }
            if (node.getmRightNode() != null){
                printFromTopToBottom(node.getmRightNode());
            }
        }
    }
}

总结

要善于使用辅助型的工具,比如队列,栈等等.