二叉树的层次遍历

二叉树的层次遍历

引用

CSDN

1.

https://blog.csdn.net/weixin_53564801/article/details/125749859

二叉树的层次遍历是数据结构中一个重要的算法，广泛应用于各种场景。本文将从概念、实现思路到具体代码实现，详细讲解如何使用队列实现二叉树的层次遍历。

1. 层次遍历概念

层次遍历就是逐层地，从左到右访问所有节点。如下图所示：

2. 方法实现思路

对于层序遍历，无疑是一层一层结点查找。那我们能不能找一个队列，把每一层的结点依次放入队列中，这样我们就能实现程序遍历啦。

首先创建一个队列，然后把根节点放入队列中。接着就把 queue 的头结点弹出，也就是A，放到 cur中去，并打印。此时 cur 指向 A结点

cur 设置的目的：方便我们把下一层结点结点放到队列当中。

队列特点： 先进先出。

我们判断 cur 的左结点是否为空，如果不为空就把左结点放入队列中。同时我们也要判断cur的右节点，操做相同。

每弹出一个结点，就会把该节点的左右孩子插入到队列中（左右孩子不为空的情况下！），然后弹出队列头结点。

也就是一层一层遍历，比如遍历完B后，把B的左右孩子放到C的后面，直到遍历完C后（第二层）才会遍历B的左右孩子（第三层）。

总结：

1. 定义一个队列，把root根节点放入队列中。
2. 弹出对头节点，并遍历打印。
3. 判断当前节点的左右孩子是否为null，如果不为null，则入队。
4. 检测队列，如果队列为空，则说明层序遍历结束。

层次遍历对于二叉树来说算是比较基础的一种算法，其拓展了许多。例如判断二叉树是否为满二叉树等。

大家还可以去做 leetcode 做一下这道题加以巩固：二叉树的层序遍历

3. 代码实现

import java.util.Queue;//导入队列的包

public class BinaryTree {
    //内部类
    static class TreeNode {
        public char val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用
        public TreeNode(char val) {
            this.val = val;
        }
    }
    /**
     * 创建一棵二叉树 返回这棵树的根节点
     *
     * @return
     */
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }
 
    //层序遍历
    void levelOrder(TreeNode root) {
        if(root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val);
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
    }
    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        TreeNode root = bt.createTree();
        bt.levelOrder(root);
    }
}

代码中树的形状，和代码结果如下：

注：
Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。
在使用时我们要导入 import java.util.Queue ;
Queue中的方法：