在数据结构的世界里，树是一种非常重要的非线性结构。遍历树的方法有很多，其中广度优先搜索（Breadth-First Search，简称BFS）是一种经典的方法。顾名思义，BFS会按照“广度”优先的原则访问节点——也就是说，先访问距离根节点最近的所有节点（同一层的节点），再访问下一层的节点。这种按层次遍历的方式，也常被称为“层次遍历”。
为什么要学BFS？¶
在树的问题中，很多场景需要按层次处理节点。比如，计算树的高度时，BFS能逐层累加层数；判断一棵树是否是完全二叉树，也需要按层次检查节点的存在性；甚至一些路径问题，比如求从根到叶子的最短路径，BFS也能高效解决。掌握BFS，能帮我们更清晰地处理树中的层次关系问题。
BFS的实现步骤（以二叉树为例）¶
BFS的核心是使用“队列”（Queue）这种数据结构来辅助遍历。队列的特点是“先进先出”（FIFO），正好符合BFS按层次处理节点的需求。具体步骤如下：
- 初始化队列：首先将根节点入队。如果树为空（根节点不存在），则直接结束遍历。
- 循环处理队列：只要队列不为空，就执行以下操作：
- 取出队首节点（队首元素），访问该节点（例如打印节点值）。
- 将该节点的子节点（通常按“左子节点优先，再右子节点”的顺序）依次入队。 - 终止条件：当队列为空时，所有节点都已访问完毕，遍历结束。
举个例子理解BFS过程¶
为了更直观，我们用一个具体的二叉树来模拟BFS的遍历过程。假设我们有这样一棵二叉树：
1
/ \
2 3
/ \
4 5
节点值分别是：根节点1，左子节点2、右子节点3；节点2的左子节点4、右子节点5；其他节点无子女。
模拟BFS过程：
- 初始状态：队列中只有根节点1，即 [1]。
- 第一次循环：取出队首节点1，访问1。将1的子节点（先左后右）2、3入队，队列变为 [2, 3]。
- 第二次循环：取出队首节点2，访问2。将2的子节点4、5入队，队列变为 [3, 4, 5]。
- 第三次循环：取出队首节点3，访问3。3无子女，队列入队操作无变化，队列变为 [4, 5]。
- 第四次循环：取出队首节点4，访问4。4无子女，队列变为 [5]。
- 第五次循环：取出队首节点5，访问5。5无子女，队列变为空。
此时遍历结束，访问顺序为：1 → 2 → 3 → 4 → 5，这正是按层次遍历的结果。
关键点总结¶
- 队列的作用：队列是BFS的“导航器”，确保按顺序处理每一层节点。每次取出队首节点后，必须将其子节点入队，才能保证下一层节点被依次处理。
- 子节点入队顺序：通常二叉树按“左子节点优先，再右子节点”入队，其他类型树（如多叉树）则按子节点自然顺序入队。
- 时间复杂度：每个节点仅入队和出队一次，因此为O(n)（n为节点总数）。
- 空间复杂度：最坏情况下（如完全二叉树最后一层），队列最多存储n/2个节点，因此为O(n)。
通过队列实现的BFS，能清晰地按层次遍历树中的所有节点。掌握这一方法，能帮助你高效解决树的层次相关问题，为后续更复杂的算法学习打下基础。