第 6 节 二分搜索树的第 4 个操作：广度优先遍历

• 重点：广度优先遍历区别于深度优先遍历的方式是我们首先将每一层的结点优先遍历完毕。
• 要想完成广度优先遍历，我们要借助队列（先进先出，后进后出）这个数据结构。
• 具体实现方式 ：当队列中的队首出队的时候，要从二叉搜索树中找到它的两个孩子入队（如果有左边孩子的话，左边先入队）。队列出队为空的时候，就将二叉树遍历完成了。
• 我们再归纳一下广度优先遍历的步骤：

1. 将根结点入队（入队的时候不做别的操作）；
2. 队列非空，所以接下来就要出队，规则是：依次出队，只要出队的元素有孩子，左右孩子依次入队，如果没有孩子不做任何操作。

代码实现：

// 二分搜索树的广度优先遍历(层序遍历)
public void levelOrder() {
    Queue<Node> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        Node node = queue.poll();
        System.out.println(node.key);
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

以下的总结是针对深度优先遍历的 3 种方式和广度优先的 1 种方式，总共 4 种遍历方式而言的：整个遍历的复杂度是：。

• 不论是深度优先遍历还是广度优先遍历，对于二分搜索树来说，每一个结点只访问了常数次；
• 归并排序和快速排序的本质其实是二叉树的深度优先遍历的过程；
• 重点把握思想：1、递归调用；2、使用队列实现一个更加复杂的算法的过程（这种按顺序访问的情况，可以使用队列）。

---

作者：liweiwei1419 链接：https://suanfa8.com/binary-search-tree/bfs 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。