Java二叉树的广度优先遍历（BFS）
广度优先遍历（Breadth-First Search, BFS）是二叉树遍历的一种方式，也称为层次遍历，它按照从上到下、从左到右的顺序访问节点。
（图片来源网络，侵删）
实现方法
以下是使用Java实现二叉树广度优先遍历的几种常见方法：
使用队列实现（标准BFS）
import java.util.LinkedList;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class BinaryTreeBFS {
public void bfsTraversal(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);
}
}
}
}
使用队列并记录层次信息
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTreeLevelOrder {
public void levelOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; 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(); // 换行表示新的一层
}
}
}
递归实现（不推荐，因为本质上不是BFS）
虽然递归通常用于深度优先遍历，但也可以模拟BFS,不过效率不高：
import java.util.ArrayList;
import java.util.List;
public class RecursiveBFS {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
helper(result, root, 0);
return result;
}
private void helper(List<List<Integer>> result, TreeNode node, int level) {
if (node == null) return;
// 如果当前层不存在，则创建新层
if (level >= result.size()) {
result.add(new ArrayList<>());
}
// 将当前节点值添加到对应层
result.get(level).add(node.val);
// 递归处理左右子节点
helper(result, node.left, level + 1);
helper(result, node.right, level + 1);
}
}
使用示例
public class Main {
public static void main(String[] args) {
// 构建一个示例二叉树
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
BinaryTreeBFS bfs = new BinaryTreeBFS();
System.out.println("广度优先遍历结果:");
bfs.bfsTraversal(root); // 输出: 1 2 3 4 5 6 7
BinaryTreeLevelOrder levelOrder = new BinaryTreeLevelOrder();
System.out.println("\n层次遍历结果:");
levelOrder.levelOrderTraversal(root);
/*
输出:
1
2 3
4 5 6 7
*/
}
}
复杂度分析
- 时间复杂度: O(n)，其中n是树中节点的数量,因为每个节点只被访问一次。
- 空间复杂度: O(n)，最坏情况下（当树是完全平衡的）队列中需要存储大约n/2个节点。
广度优先遍历常用于寻找最短路径、层次遍历等问题,是二叉树遍历中非常重要的一种方法。
（图片来源网络，侵删）
