C#广度优先搜索详解（BFS层级遍历算法从零入门）

什么是 BFS 层级遍历？

想象一棵二叉树，根节点在最上层，子节点在其下方。BFS 会从根节点开始，先访问第一层（根），再访问第二层（根的子节点），然后是第三层……依此类推，一层一层地“横向”遍历。这种遍历方式也被称为层级遍历（Level Order Traversal）。

在 C# 中，我们通常使用 Queue<T>（队列）来实现 BFS，因为队列具有“先进先出”（FIFO）的特性，正好符合 BFS 的访问顺序。

C# 实现 BFS 层级遍历

首先，我们需要定义一个二叉树节点类：

public class TreeNode{    public int Val;    public TreeNode Left;    public TreeNode Right;    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)    {        Val = val;        Left = left;        Right = right;    }}

接下来，我们编写 BFS 层级遍历方法。该方法将返回一个列表，其中每个子列表代表树的一层节点值：

using System;using System.Collections.Generic;public IList<IList<int>> LevelOrder(TreeNode root){    var result = new List<IList<int>>();        // 如果根节点为空，直接返回空列表    if (root == null) return result;    // 创建队列，并将根节点入队    var queue = new Queue<TreeNode>();    queue.Enqueue(root);    // 当队列不为空时，继续处理    while (queue.Count > 0)    {        int levelSize = queue.Count; // 当前层的节点数量        var currentLevel = new List<int>();        // 遍历当前层的所有节点        for (int i = 0; i < levelSize; i++)        {            TreeNode node = queue.Dequeue();            currentLevel.Add(node.Val);            // 将子节点加入队列（为下一层做准备）            if (node.Left != null)                queue.Enqueue(node.Left);            if (node.Right != null)                queue.Enqueue(node.Right);        }        result.Add(currentLevel);    }    return result;}

代码解析

• 队列初始化：我们将根节点放入队列，作为 BFS 的起点。
• 按层处理：每次进入 while 循环时，队列中恰好包含当前层的所有节点。我们通过 levelSize = queue.Count 获取当前层数量，然后用 for 循环处理这一整层。
• 子节点入队：处理完当前节点后，将其非空的左右子节点加入队列，供下一轮循环使用。
• 结果收集：每处理完一层，就将该层的值列表添加到最终结果中。

为什么学习 C# 广度优先搜索很重要？

掌握 C#广度优先搜索 不仅能帮助你解决常见的 二叉树遍历 问题，还是理解更复杂图算法（如最短路径、连通性检测）的基础。在面试中，BFS 也是高频考点之一。

无论你是初学者还是有一定经验的开发者，理解 BFS层级遍历 都是提升算法能力的关键一步。通过本篇 算法入门教程，希望你已经能够独立写出清晰、高效的 BFS 代码！

小结

本文详细讲解了如何在 C# 中实现广度优先搜索（BFS）进行二叉树的层级遍历。我们使用队列数据结构，逐层处理节点，并将结果按层组织。这种方法时间复杂度为 O(n)，空间复杂度也为 O(n)，非常高效。

现在，你可以尝试自己构建一棵树并运行上述代码，观察输出结果。动手实践是掌握 C#广度优先搜索 和 BFS层级遍历 的最佳方式！