本文将详细讲解如何使用 Java 实现二叉树的广度优先搜索（BFS）算法。我们将避免直接获取节点的兄弟节点，而是通过将当前节点的子节点按顺序加入队列，确保按照兄弟节点的顺序访问它们。此外，强调在节点从队列中取出时进行访问，而非加入队列时，以保证算法的正确性。
广度优先搜索（BFS）是一种用于遍历或搜索树或图数据结构的算法。它从树的根节点开始，沿着树的宽度遍历节点。如果所有节点都已被访问，则算法终止。在二叉树的场景下，BFS 通常用于按层级顺序访问节点。
BFS 算法实现
以下是如何在 Java 中实现二叉树 BFS 的详细步骤和代码示例。
1. 节点定义
立即学习“Java免费学习笔记（深入）”；
首先，定义一个 Node 类来表示二叉树的节点。这个类包含数据域、左右子节点以及一个 visited 标志（虽然在改进后的代码中不再直接使用 visited 标志，但了解其作用有助于理解算法思路）。
public class Node {
int data;
Node left;
Node right;
boolean visited;
Node(int data) {
this.data = data;
this.left = null;
this.right = null;
this.visited = false;
}
// Getter 和 Setter 方法（省略）
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
}2. 构建二叉树
创建一个二叉树实例，用于测试 BFS 算法。
Node node1 = new Node(1); Node node7 = new Node(7); Node node9 = new Node(9); Node node8 = new Node(8); Node node2 = new Node(2); Node node3 = new Node(3); node1.left = node7; node1.right = node9; node7.right = node8; node9.right = node3; node9.left = node2;
3. BFS 算法实现
以下是 BFS 算法的核心实现。关键在于使用队列 Queue 来存储待访问的节点，并确保按照层级顺序访问它们。
import java.util.LinkedList;
import java.util.Queue;
import java.util.ArrayList;
import java.util.List;
public class BFS {
public static List<Node> bfs(Node root) {
Queue<Node> queue = new LinkedList<>();
List<Node> result = new ArrayList<>();
if (root == null) {
return result;
}
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.poll(); // 取出队列中的第一个节点
result.add(node); // 访问节点，将其添加到结果列表中
// 将当前节点的子节点加入队列
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
return result;
}
public static void main(String[] args) {
Node node1 = new Node(1);
Node node7 = new Node(7);
Node node9 = new Node(9);
Node node8 = new Node(8);
Node node2 = new Node(2);
Node node3 = new Node(3);
node1.left = node7;
node1.right = node9;
node7.right = node8;
node9.right = node3;
node9.left = node2;
List<Node> bfsResult = bfs(node1);
for (Node node : bfsResult) {
System.out.println(node.data);
}
}
}代码解释：
-
bfs(Node root) 函数：
- 创建一个 LinkedList 作为队列 queue，用于存储待访问的节点。
- 创建一个 ArrayList 作为 result，用于存储BFS遍历的结果。
- 如果根节点为空，则返回空列表。
- 将根节点加入队列。
- 当队列不为空时，循环执行以下操作：
- 从队列中取出一个节点 node。
- 将该节点添加到结果列表 result中，表示访问该节点。
- 将该节点的左子节点和右子节点（如果存在）加入队列。
-
main 函数：
- 创建二叉树。
- 调用 bfs 函数进行广度优先搜索。
- 遍历结果列表，并打印每个节点的数据。
4. 使用示例
以下是如何使用 bfs 函数的示例：
for (Node node : BFS.bfs(node1)) {
System.out.println(node.data);
}这段代码会按层级顺序打印二叉树的节点数据。
注意事项
- 避免直接获取兄弟节点： BFS 的关键在于按层级顺序访问节点。通过将当前节点的子节点加入队列，并按队列的顺序取出节点，可以保证按照兄弟节点的顺序访问。
- 访问时机： 在节点从队列中取出时进行访问，而不是在加入队列时。这确保了在访问节点时，其所有父节点都已被访问。
- 空节点处理： 在将子节点加入队列之前，需要检查子节点是否为空，以避免空指针异常。
总结
本文详细介绍了如何在 Java 中实现二叉树的广度优先搜索（BFS）算法。通过使用队列和按层级顺序访问节点，可以有效地遍历二叉树。该算法在许多应用中都非常有用，例如在社交网络中查找朋友的朋友，或者在游戏中查找最短路径。
