二叉树的层序遍历（BFS 广度优先算法）

小半 • 2023年2月3日上午10:55 • 技术随笔 • 阅读 79

一.概念

所谓的层序遍历，就是从根节点（第一层）开始，依次向下，获取每一层所有结点的值，即从上到下，每一层从左到右遍历，假设有二叉树如下：

那么层序遍历的结果是：EBGADFHC

二.实现

需求: 使用层序遍历，获取整个树中的所有键
步骤：

创建两个队列，一个nodes存储每一层的结点，另一个que存储树的key ；
使用循环从队列nodes中弹出一个结点：
2.1获取当前结点的key放到que中；
2.2如果当前结点的左子结点不为空，则把左子结点放入到队列nodes中
2.3如果当前结点的右子结点不为空，则把右子结点放入到队列nodes中

例：假设有如下二叉树

从根节点开始，先将④放入nodes
弹出④，将④的key放入que，然后将④的左右结点②⑤放入nodes；（注意队列为尾插头取）
弹出②，将②的key放入que，然后将②的左右结点放入①③放入node；
弹出⑤，将⑤的key放入que，⑤没有子结点，继续下一轮while；
弹出①，将①的key放入que，①没有子结点，继续下一轮while；
弹出③，将③的key放入que，③没有子结点，nodes为空，跳出while
遍历队列que，得到结果。

代码：

   public Queue<Key> layerErgodic(){
    //定义两个队列，一个存储结点，另一个存储key
        Queue<Key> que=new LinkedList<>();
        Queue<Node> nodes=new LinkedList<>();
        //默认先放根节点
        nodes.add(root);
        while(!nodes.isEmpty()){
            //从notes中弹出当前头结点的key放入que
            Node n = nodes.poll(); //弹出头结点（队列为尾插头取）
            que.add(n.key);//将头结点n的key放入que
            //判断当前结点是否有左子节点，如果有则放入nodes中
            if(n.left!=null){
                nodes.add(n.left);
            }
            //判断当前结点是否有右子节点，如果有则放入nodes中
            if(n.right!=null){
                nodes.add(n.right);
            }
        }
        return que;
    }