什么是二分搜索树层序遍历
在数据结构的世界里，二分搜索树（Binary Search Tree，简称 BST）是一个非常经典且实用的结构。它像一棵有序的树，左子树的所有节点值都小于根节点，右子树的所有节点值都大于根节点。这种特性让查找、插入和删除操作在平均情况下效率极高。
但当你面对一棵结构复杂的二分搜索树时，如何“看清”它的全貌？这时候，遍历就成了关键。常见的遍历方式有前序、中序、后序，它们都是深度优先的策略。而今天我们要讲的，是另一种完全不同的视角——层序遍历。
层序遍历，顾名思义，就是从上到下、从左到右，一层一层地访问树中的节点。你可以把它想象成一个水波纹扩散的过程：从根节点开始，第一圈是它自己，第二圈是它的孩子，第三圈是孙子辈……每圈都按从左到右的顺序来。
这种遍历方式在实际开发中非常有用，比如你要打印一棵树的结构，或实现广度优先搜索（BFS），又或者在图形界面中展示树形结构时，层序遍历就是首选。
为什么层序遍历需要队列
要实现层序遍历，核心在于“按层处理”。我们不能像递归那样自然地进入下一层，因为递归是深度优先的，它会一直走到最深的叶子，而不会“横向”扩展。
这时，队列（Queue）就派上用场了。队列是一种先进先出（FIFO）的数据结构，特别适合这种“先处理当前层，再把下一层的孩子加入”的逻辑。
举个例子：
假设我们有一棵二分搜索树，根节点是 8，左孩子是 3，右孩子是 10。
第一层：我们先处理 8，把它的左右孩子 3 和 10 加入队列。
第二层：从队列中取出 3，处理它，把它的孩子（如果有）加入队列。接着取出 10，处理它。
第三层：继续取出队列中的节点……直到队列为空。
整个过程就像排队打饭：先来的人先打饭，打完饭的人离开，新来的人排到队尾。这就是队列的精髓。
二分搜索树层序遍历的代码实现
下面我们用 Java 实现一个完整的层序遍历函数。这里我们先定义树节点结构，再实现遍历逻辑。
// 定义二分搜索树的节点
class TreeNode {
int val;
TreeNode left;
TreeNode right;
// 构造函数
public TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
接下来是核心的层序遍历方法：
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTreeTraversal {
// 层序遍历方法
public static void levelOrderTraversal(TreeNode root) {
// 如果根节点为空，直接返回，不处理
if (root == null) {
return;
}
// 创建一个队列，用于存储待处理的节点
Queue<TreeNode> queue = new LinkedList<>();
// 将根节点加入队列，作为起点
queue.offer(root);
// 当队列不为空时，持续处理
while (!queue.isEmpty()) {
// 从队列头部取出一个节点（先进先出）
TreeNode node = queue.poll();
// 打印当前节点的值（表示访问该节点）
System.out.print(node.val + " ");
// 如果左孩子存在，将其加入队列
if (node.left != null) {
queue.offer(node.left);
}
// 如果右孩子存在，将其加入队列
if (node.right != null) {
queue.offer(node.right);
}
}
// 遍历结束后，打印换行符，让输出更清晰
System.out.println();
}
}
代码逐行解析
Queue<TreeNode> queue = new LinkedList<>();：创建一个队列，用来存储待处理的节点。LinkedList 实现了 Queue 接口，适合做队列。queue.offer(root);：把根节点加入队列。offer 是添加元素的方法，如果队列满会返回 false，但队列一般不会满，所以这里安全。while (!queue.isEmpty())：只要队列还有节点，就继续处理。TreeNode node = queue.poll();：从队列头取出一个节点。poll 是移除并返回队首元素，是 FIFO 的体现。System.out.print(node.val + " ");：打印当前节点的值，表示“访问”了它。if (node.left != null)：检查左孩子是否存在，存在就加入队列。if (node.right != null)：同理，检查右孩子。
为什么先加左孩子，再加右孩子？
因为我们要从左到右访问每一层。如果先加右孩子，再加左孩子，队列的处理顺序就会变成右 → 左，导致输出顺序错误。所以必须保持“先左后右”的顺序。
实际案例演示
让我们用一个具体的二分搜索树来演示层序遍历。
假设我们构建如下结构的二分搜索树：
8
/ \
3 10
/ \ \
1 6 14
/ \
4 7
我们按插入顺序构建这棵树（这里省略插入代码），然后调用层序遍历：
public class Main {
public static void main(String[] args) {
// 构建树节点
TreeNode root = new TreeNode(8);
root.left = new TreeNode(3);
root.right = new TreeNode(10);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(6);
root.right.right = new TreeNode(14);
root.left.right.left = new TreeNode(4);
root.left.right.right = new TreeNode(7);
// 执行层序遍历
levelOrderTraversal(root);
}
}
运行结果为：
8 3 10 1 6 14 4 7
这个结果完全符合预期：第一层是 8，第二层是 3 和 10，第三层是 1、6、14，第四层是 4 和 7。每一层都从左到右。
层序遍历的变种：按层打印
有时候，我们不仅想输出所有节点，还想知道哪些节点属于哪一层。这时我们可以稍作修改，让程序按层输出。
import java.util.LinkedList;
import java.util.Queue;
public class LevelByLevelTraversal {
public static void levelOrderWithLevel(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int level = 1; // 当前处理的层数
while (!queue.isEmpty()) {
int size = queue.size(); // 当前层的节点数量
System.out.print("第 " + level + " 层: ");
// 处理当前层的所有节点
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
System.out.println(); // 换行，进入下一层
level++; // 层数加一
}
}
}
这段代码的关键在于 int size = queue.size()。在进入每一层前，我们先记录当前队列的大小，这代表了当前层有多少个节点。然后我们只循环这个次数，确保只处理当前层的节点。
运行结果：
第 1 层: 8
第 2 层: 3 10
第 3 层: 1 6 14
第 4 层: 4 7
这样，我们就能清晰地看到每层的结构，对调试和理解树的形态非常有帮助。
常见误区与注意事项
在实现二分搜索树层序遍历时，有几个容易出错的地方：
- 忘记判空：如果根节点为 null，直接调用
queue.offer(root)会抛出空指针异常。一定要先判断。 - 队列使用错误：不能用栈来代替队列，否则会变成深度优先遍历。
- 节点重复加入：确保每个节点只入队一次，避免无限循环。由于二分搜索树中没有环，一般不会出现，但如果是无向图就需要注意。
- 打印顺序混乱：一定要先加左孩子，再加右孩子，否则输出顺序会错乱。
此外，层序遍历的时间复杂度是 O(n)，空间复杂度也是 O(n)，因为最坏情况下队列中会存储整棵树的一半节点（最后一层的节点）。
总结
二分搜索树层序遍历是一种非常实用的遍历方式，它让我们能够从“横向”的视角完整地观察一棵树的结构。通过队列的辅助，我们可以轻松实现从上到下、从左到右的逐层访问。
它不仅在算法面试中常见，也在实际项目中广泛使用，比如构建树形菜单、渲染 UI 树、或实现广度优先搜索的路径查找。
掌握层序遍历，意味着你不仅会“走”树，还会“看”树。这种能力，是每一位开发者迈向进阶的必经之路。
无论你是初学者还是中级开发者，只要多写几遍代码，多调试几次，你就能熟练掌握这一技巧。记住：理解比记忆更重要，动手比看视频更有效。现在，就拿起你的编辑器，自己实现一遍吧。