Hello 算法：二叉树层序遍历（BFS）的实现原理、逐行解析与可视化运行实践

本文基于 hello-algo 仓库中的 Python Tutor 可视化脚本 binary_tree_bfs.md，结合 《二叉树遍历》章节文档 与可运行的 Python 源码 binary_tree_bfs.py，完整讲解二叉树层序遍历（BFS）的算法思想、队列实现细节、数组反序列化为二叉树的下标规则，以及时间/空间复杂度的推导过程。读完后，你将能够独立实现层序遍历、理解其在满二叉树下队列峰值空间达到 (n+1)/2 的原因，并在本地运行代码验证结果。

一、什么是层序遍历：广度优先的"逐层扩展"

从物理结构的角度看，二叉树是一种基于链表的数据结构，遍历需要借助指针逐个访问节点；但树是非线性结构，因此遍历比链表更复杂，需要搜索算法的支撑。

层序遍历（level-order traversal）从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。它本质上属于广度优先遍历（breadth-first traversal），也称广度优先搜索（BFS），体现的是一种"一圈一圈向外扩展"的逐层遍历方式。以文档示例中的完全二叉树 [1, 2, 3, 4, 5, 6, 7] 为例，层序遍历的访问顺序正是 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7，与插入顺序一致——这并非巧合，而是广度优先搜索天然保持的"父节点先于子节点、左子节点先于右子节点"的性质。

广度优先遍历通常借助"队列"来实现。队列遵循"先进先出"（FIFO）的规则，而广度优先遍历遵循"逐层推进"的规则，两者背后的思想是一致的：先入队的节点（更靠近根）一定先被处理，从而保证了访问顺序的层次性。

二、可运行实现：从节点定义到层序遍历

仓库中 binary_tree_bfs.py 是这一主题的可独立运行版本，其核心逻辑与 Python Tutor 可视化脚本 完全对应。下面结合仓库 公共模块 逐项拆解。

2.1 二叉树节点类

仓库的 tree_node.py 中定义了统一的节点类，每个节点保存一个整型值、左右子节点引用：

class TreeNode:
    """二叉树节点类"""

    def __init__(self, val: int = 0):
        self.val: int = val  # 节点值
        self.height: int = 0  # 节点高度
        self.left: TreeNode | None = None  # 左子节点引用
        self.right: TreeNode | None = None  # 右子节点引用

其中 left 与 right 是 TreeNode | None 类型，指向子节点或为空。TreeNode | None 联合类型语法要求 Python 3.10+（模块顶部使用了 from __future__ import annotations 以兼容更低版本的注解求值）。

2.2 层序遍历的核心代码

以下是 binary_tree_bfs.py 中的层序遍历实现，也是 Python Tutor 脚本 的主函数：

from collections import deque

def level_order(root: TreeNode | None) -> list[int]:
    """层序遍历"""
    # 初始化队列，加入根节点
    queue: deque[TreeNode] = deque()
    queue.append(root)
    # 初始化一个列表，用于保存遍历序列
    res = []
    while queue:
        node: TreeNode = queue.popleft()  # 队列出队
        res.append(node.val)  # 保存节点值
        if node.left is not None:
            queue.append(node.left)  # 左子节点入队
        if node.right is not None:
            queue.append(node.right)  # 右子节点入队
    return res

关键实现要点：

1. 使用 collections.deque 作为队列。deque（双端队列）的 popleft() 与 append() 均为均摊 O(1) 操作。这一点非常重要：如果用普通 list 模拟队列并在头部执行 pop(0)，每次出队都会触发 O(n) 的元素搬移，会把整体时间复杂度从 O(n) 劣化为 O(n²)。
2. 初始状态队列中只有根节点。若根为空（root is None），主循环一次都不会执行，直接返回空列表——从源码结构看，该实现对空树是安全的，前提是调用方保证传入合法根引用。
3. "出队-访问-入队子节点"三步循环。每次从队列头部取出一个节点并记录其值，再把它的左、右子节点（若存在）依次加入队尾。队列的 FIFO 特性保证了：第 k 层的所有节点一定先于第 k+1 层出队，从而天然实现了逐层、从左到右的访问顺序。
4. 先左后右入队。左子节点先入队，故同层中左子节点一定先于右子节点被访问，这正是"每一层从左到右"这一语义的来源。

2.3 驱动代码：数组构建二叉树并遍历

binary_tree_bfs.py 的驱动部分演示了完整的调用链：

if __name__ == "__main__":
    # 初始化二叉树
    # 这里借助了一个从数组直接生成二叉树的函数
    root: TreeNode = list_to_tree(arr=[1, 2, 3, 4, 5, 6, 7])
    print("\n初始化二叉树\n")
    print_tree(root)

    # 层序遍历
    res: list[int] = level_order(root)
    print("\n层序遍历的节点打印序列 = ", res)

在仓库中执行 python codes/python/chapter_tree/binary_tree_bfs.py 即可看到先以树形结构打印出的二叉树（print_util.py 中的 print_tree 借助 Trunk 递归绘制竖线与分支），最后输出层序遍历序列 [1, 2, 3, 4, 5, 6, 7]。

三、数组反序列化为二叉树：下标 2i+1 与 2i+2

Python Tutor 脚本 的一个显著特点是完全自包含：它内联了 TreeNode、list_to_tree 与 level_order，不依赖外部模块，便于在在线可视化工具中逐指令执行。其中"列表转二叉树"的实现如下（与 tree_node.py 一致）：

def list_to_tree_dfs(arr: list[int], i: int) -> TreeNode | None:
    """将列表反序列化为二叉树：递归"""
    # 如果索引超出数组长度，或者对应的元素为 None，则返回 None
    if i < 0 or i >= len(arr) or arr[i] is None:
        return None
    # 构建当前节点
    root = TreeNode(arr[i])
    # 递归构建左右子树
    root.left = list_to_tree_dfs(arr, 2 * i + 1)
    root.right = list_to_tree_dfs(arr, 2 * i + 2)
    return root


def list_to_tree(arr: list[int]) -> TreeNode | None:
    """将列表反序列化为二叉树"""
    return list_to_tree_dfs(arr, 0)

这里采用的是完全二叉树的数组表示法：对于下标为 i 的节点，其左子节点位于下标 2*i+1，右子节点位于下标 2*i+2。以 arr = [1, 2, 3, 4, 5, 6, 7] 为例，下标 0 的节点 1 生成左右子节点（下标 1 的节点 2、下标 2 的节点 3），下标 1 的节点 2 生成（下标 3 的节点 4、下标 4 的节点 5），依此类推。递归在三种情况下终止并返回 None：下标越界、下标为负、或该位置的元素显式为 None——因此序列化列表中也允许用 None 表示"该位置无节点"，例如 tree_node.py 注释中给出的 [1, 2, 3, 4, None, 6, 7, 8, 9, None, None, 12, None, None, 15] 就是一个含空位的稀疏表示。

需要说明的是，这种"按下标计算子节点"的方式只对完全二叉树（或按完全二叉树编号的稀疏树） 语义正确；它本质上是一次深度优先的递归构建（函数名 list_to_tree_dfs 也表明了这一点），与外层 BFS 遍历形成"DFS 建树、BFS 遍历"的组合。仓库还提供了反向的 tree_to_list 序列化函数，可将其与 list_to_tree 互相印证。

四、复杂度分析

依据 《二叉树遍历》章节 的结论，并结合上面的实现来理解其推导：

• 时间复杂度 O(n)：每个节点恰好入队一次、出队一次，每次出入队与访问都是 O(1) 操作（使用 deque 时），总耗时为 O(n)，其中 n 为节点数量。
• 空间复杂度 O(n)：额外空间主要是队列。在最差情况下，即满二叉树时，遍历到最底层之前，队列中最多同时存在 (n+1)/2 个节点——可以这样理解：满二叉树在处理完倒数第二层最后一个节点时，队列中恰好积压了整个最后一层的全部节点（(n+1)/2 个），这是队列长度的峰值，因此空间为 O(n)。

五、仓库中的调用关系与延伸阅读

从源码结构看，本章涉及的文件组织如下，便于按图索骥：

• codes/python/chapter_tree/binary_tree_bfs.py：层序遍历的可运行示例（level_order 函数 + 驱动代码）；
• codes/pythontutor/chapter_tree/binary_tree_bfs.md：同一算法的自包含脚本（内联节点类与建树函数），文件头部标注了对应的可视化入口（[file]{binary_tree_bfs}-[class]{}-[func]{level_order}），文件主体是可直接在 Python Tutor 中逐指令执行的完整代码及其在线渲染链接参数，适合观察队列中元素的逐步变化；
• codes/python/modules/tree_node.py：TreeNode 类、list_to_tree / tree_to_list 序列化与反序列化实现；
• codes/python/modules/print_util.py：print_tree 等调试打印工具；
• codes/python/chapter_tree/binary_tree_dfs.py：前序、中序、后序遍历的对应实现，与本篇的 BFS 形成广度优先与深度优先的对照；
• codes/python/chapter_tree/array_binary_tree.py：完全二叉树的数组表示，可加深对 2*i+1 / 2*i+2 下标规则的理解。

与深度优先遍历（DFS，前序/中序/后序，体现"先走到尽头，再回溯继续"的方式）相比，BFS 的两大特征是必须借助队列维护访问顺序和空间开销随树的宽度增长：满二叉树下队列峰值达 (n+1)/2，而 DFS 递归实现的最坏空间则来自树退化为链表时深度为 n 的递归栈。两种遍历时间复杂度同为 O(n)，选型上取决于问题需求——凡是涉及"最短层数""逐层处理"的场景（如求二叉树的最小深度、按层输出、最近祖先等问题），层序遍历都是最自然的工具。

六、本地运行指南

适用前提：Python 3.10+（代码使用了 X | None 联合类型语法）。在仓库根目录下执行：

python codes/python/chapter_tree/binary_tree_bfs.py

预期输出为先以树形结构打印的完全二叉树（根为 1，7 个节点），最后一行为：

层序遍历的节点打印序列 =  [1, 2, 3, 4, 5, 6, 7]

若希望逐条语句观察队列 queue 与结果列表 res 的演变过程，可将 binary_tree_bfs.py 的代码直接粘贴到 Python Tutor 一类的在线可视化工具中执行——Python Tutor 脚本文件 提供的正是这样一份不依赖仓库模块的自包含版本，这也是该文件在仓库中独立存在的意义。