按层打印二叉树

秒速五厘米 2021-09-22 06:20 293阅读 0赞

二叉树是一种常见的数据结构，由n（你>=0）个节点构成，每个节点最多有两个子二叉树。  
由二叉树的定义可知，一棵二叉树由三部分组成：根节点、左子树和右子树。二叉树的遍历方式有先序遍历、中序遍历和后序遍历。  
![这里写图片描述][SouthEast]  
先序遍历：首先访问根节点，然后访问根节点左孩子，再访问根节点的右孩子。

中序遍历：首先访问根节点左孩子，然后访问根节点，在访问根节点的右孩子。

后序遍历：首先访问根节点左孩子，然后访问根节点的右孩子，再访问根节点。

上述三种遍历方式原理相同，可以采用递归的方式实现遍历。

这里要说的是二叉树的另一种遍历方法：按层遍历。

按层遍历即从二叉树的根节点开始从上至下从左至右依次访问节点。  
在介绍按层遍历的实现前先定义一下二叉树的结构。

class TreeNode { 
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }

上述代码即定义了二叉树中每个节点的结构。节点的数据 val、该节点的左孩子 left和该节点的有孩子right。

下面以一个实例问题实现二叉树的按层遍历。  
按层遍历算法如下：  
1、初始化设置一个队列；  
2、把根节点先入队列；  
3、当队列非空时：  
①、出队列取得当前队头结点，访问该节点；  
②、若该结点的左孩子结点非空，则将该结点的左孩子结点放入队列。  
③、若该结点的右孩子结点非空，则将该结点的右孩子结点放入队列。  
4、结束

> 问题  
> 给定二叉树的根结点root，请返回打印结果，结果按照每一层一个数组进行储存，所有数组的顺序按照层数从上往下，且每一层的数组内元素按照从左往右排列。

--------------------

/** * 二叉树的按层遍历 * * @param root * 二叉树的根节点 * @return 返回一个二维数组表示每一层由哪些数据构成 */
        public static int[][] printTree(TreeNode root) {
            // 如果二叉树为空立即结束
            if (root == null) {
                return null;
            }
    
            // 作用1：存储每一层的数据集合
            // 作用2：转化为数组返回
            ArrayList<ArrayList<Integer>> array = new ArrayList<>();
            // 临时存放每层结点
            ArrayList<Integer> temp;
            int last = 0;
            int nlast = 0;
            // 当前结点
            TreeNode curr;
            Queue<TreeNode> queue = new LinkedList<>();
            // 步骤1 ：根节点入队列
            curr = root;
            queue.offer(curr);
            nlast = curr.val;
            last = nlast;
            temp = new ArrayList<>();
            // 步骤二 ： 循环遍历二叉树
            while (!queue.isEmpty()) {
                curr = queue.poll();
                temp.add(curr.val);
                // 左孩子非空，将左孩子如队列
                if (curr.left != null) {
                    queue.offer(curr.left);
                    nlast = curr.left.val;
                }
                // 右孩子非空，将右孩子入队列
                if (curr.right != null) {
                    queue.offer(curr.right);
                    nlast = curr.right.val;
                }
                if (curr.val == last) {
                    last = nlast;
                    array.add(temp);
                    temp = new ArrayList<>();
                }
            }
            // 将array中的结点数据转换为二维数组返回
            int[][] result = new int[array.size()][];
            for (int i = 0; i < result.length; i++) {
                ArrayList<Integer> tempArray = array.get(i);
                result[i] = new int[tempArray.size()];
                int n = result[i].length;
                for (int j = 0; j < n; j++) {
                    result[i][j] = tempArray.get(j);
                }
            }
            return result;
        }

[SouthEast]: /images/20210920/16a507181bf8446385bb38d2b28a83ae.png