04.从上往下打印二叉树

目录介绍

• 01.题目要求
• 02.问题分析
• 03.实例代码

01.题目要求

• 问题如下所示：
  • 从上往下打印出二叉树的每个结点，同一层的结点按照从左向右的顺序打印。
• 示例 :

  
  /**
   * 从上往下打印出二叉树的每个结点，向一层的结点按照从左往右的顺序打印。
   * 例如下的二叉树，
   *       8
   *    /    \
   *   6     10
   *  /  \   / \
   * 5   7  9  11
   * 则依次打印出8、6、10、5、7 、9、11.
   */

02.问题分析

• 这道题实质是考查树的遍历算法。从上到下打印二叉树的规律：每一次打印一个结点的时候，如果该结点有子结点， 则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点，重复前面的打印操作，直至队列中所有的结点都被打印出来为止。

03.实例代码

• 如下所示

  public class Test {
      /**
       * 二叉树的树结点
       */
      public static class BinaryTreeNode {
          int value;
          BinaryTreeNode left;
          BinaryTreeNode right;
      }
  
      /**
       * 从上往下打印出二叉树的每个结点，向一层的结点按照从左往右的顺序打印。
       * 例如下的二叉树，
       *       8
       *    /    \
       *   6     10
       *  /  \   / \
       * 5   7  9  11
       * 则依次打印出8、6、10、5、7 、9、11.
       *
       * @param root 树的结点
       */
      public static void printFromToBottom(BinaryTreeNode root) {
  
          // 当结点非空时才进行操作
          if (root != null) {
              // 用于存放还未遍历的元素
              Queue<BinaryTreeNode> list = new LinkedList<>();
              // 将根结点入队
              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);
                  }
              }
          }
      }
  }