［剑指offer学习心得］之：从上往下打印二叉树

题目：从上往下打印出二叉树的每个结点，同一层的结点按照从左向右的顺序打印。

解题思路

其实一想就觉得是宽度优先遍历。当然这样想是不是太粗暴了，循序渐进循序渐进

这道题实质就是考察树的遍历算法，只是这种算法不是我们熟知的那三种，所以呢我们可能一下子也想不清楚遍历的过程，所以可以先好好分析一下下面这棵树：

8
| \
6 10
| \ | \
5 7 9 11

按照层次打印顺序决定应该先打印根结点，所以可以从树的根结点开始分析啦。为了接下来能够打印值为8的左右两个子结点，我们应该在遍历到该结点时把值为6和10的两个结点保存到一个容器里，现在容器内就有两个结点了。按照从左到右的打印要求，所以先取出值为6的结点。打印出值6之后把它的值分别为5和7的两个结点放入数据容器中。此时容器中有三个结点：10、5、7。接下来我们从数据容器中取出值为10的结点。10是比5、7结点先放入的，因此不难看出这个数据容器应该是一个队列。由于值为5、7、9、11的结点都没有子结点，因此只要依次打印即可。

所以我们可以找出这样一条规律：每一次打印一个结点的时候，如果该结点有子结点，则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点，重复前面的打印操作，直到队列中所有的结点都被打印出来为止。

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

public class PrintFromTopToBottom {

/** 
 * 二叉树节点类 
 */  
  public static class BinaryTreeNode {  
      int value; 
      BinaryTreeNode left; 
      BinaryTreeNode right; 
  } 

    public static void printFromTopToBottom(BinaryTreeNode root){
        if(root==null){
            return;
        }

        Queue<BinaryTreeNode> list=new LinkedList<BinaryTreeNode>();
        list.add(root);
        BinaryTreeNode curNode;
        while(!list.isEmpty()){
            curNode=list.remove();
            System.out.print(curNode.value+" ");
            if(curNode.left!=null){
                list.add(curNode.left);
            }
            if(curNode.right!=null){
                list.add(curNode.right);
            }
        }
    }

    public static void main(String[] args){
//      8
       //    /    \
       //   6     10
       //  / \   / \
       // 5   7 9  11
       BinaryTreeNode root = new BinaryTreeNode();
       root.value = 8;
       root.left = new BinaryTreeNode();
       root.left.value = 6;
       root.left.left = new BinaryTreeNode();
       root.left.left.value = 5;
       root.left.right = new BinaryTreeNode();
       root.left.right.value = 7;
       root.right = new BinaryTreeNode();
       root.right.value = 10;
       root.right.left = new BinaryTreeNode();
       root.right.left.value = 9;
       root.right.right = new BinaryTreeNode();
       root.right.right.value = 11;
       printFromTopToBottom(root);
       //         1
       //        /
       //       3
       //      /
       //     5
       //    /
       //   7
       //  /
       // 9
       BinaryTreeNode root2 = new BinaryTreeNode();
       root2.value = 1;
       root2.left = new BinaryTreeNode();
       root2.left.value = 3;
       root2.left.left = new BinaryTreeNode();
       root2.left.left.value = 5;
       root2.left.left.left = new BinaryTreeNode();
       root2.left.left.left.value = 7;
       root2.left.left.left.left = new BinaryTreeNode();
       root2.left.left.left.left.value = 9;
       System.out.println("\n");
       printFromTopToBottom(root2);
       // 0
       //  \
       //   2
       //    \
       //     4
       //      \
       //       6
       //        \
       //         8
       BinaryTreeNode root3 = new BinaryTreeNode();
       root3.value = 0;
       root3.right = new BinaryTreeNode();
       root3.right.value = 2;
       root3.right.right = new BinaryTreeNode();
       root3.right.right.value = 4;
       root3.right.right.right = new BinaryTreeNode();
       root3.right.right.right.value = 6;
       root3.right.right.right.right = new BinaryTreeNode();
       root3.right.right.right.right.value = 8;
       System.out.println("\n");
       printFromTopToBottom(root3);
       // 1
       BinaryTreeNode root4 = new BinaryTreeNode();
       root4.value = 1;
       System.out.println("\n");
       printFromTopToBottom(root4);
       // null
       System.out.println("\n");
       printFromTopToBottom(null);
    }
}