Python实现二叉树层序遍历（小白也能学会的BFS算法详解）

什么是层序遍历？

想象一棵树：根在最上面，子节点一层一层往下延伸。二叉树层序遍历就是先访问第0层（根节点），再访问第1层（根的左右孩子），接着第2层……直到最后一层。这种“由上到下、由左到右”的访问顺序非常适合用队列（Queue）来实现。

为什么使用队列？

因为队列具有“先进先出”（FIFO）的特性：我们先把根节点放入队列；然后取出它并访问，同时把它的左右孩子按顺序加入队列；重复这个过程，就能自然地实现逐层遍历。这正是BFS算法实现的核心思想。

Python代码实现

下面我们用Python来完整实现一个层序遍历函数。首先定义二叉树节点类，然后编写遍历函数。

class TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = rightfrom collections import dequedef level_order_traversal(root):    """    实现二叉树的层序遍历（广度优先搜索）    :param root: TreeNode - 二叉树的根节点    :return: List[int] - 按层序遍历的结果列表    """    if not root:        return []        result = []    queue = deque([root])  # 初始化队列，放入根节点        while queue:        node = queue.popleft()  # 取出队列头部节点        result.append(node.val)  # 访问该节点                # 将左右子节点加入队列（如果存在）        if node.left:            queue.append(node.left)        if node.right:            queue.append(node.right)        return result

代码解析

• TreeNode类：定义了二叉树的基本结构，每个节点包含值（val）、左子节点（left）和右子节点（right）。
• deque：Python标准库中的双端队列，比普通列表更高效地实现队列操作（popleft 和 append）。
• 主循环：只要队列不为空，就不断取出节点、记录值，并将其子节点加入队列。
• 边界处理：如果根节点为空，直接返回空列表。

测试示例

让我们构建一个简单的二叉树并测试我们的函数：

# 构建如下二叉树：#       1#      / \#     2   3#    / \#   4   5root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.right = TreeNode(5)print(level_order_traversal(root))  # 输出: [1, 2, 3, 4, 5]

总结

通过本教程，你已经掌握了如何用Python层序遍历二叉树。这种广度优先搜索方法不仅适用于二叉树，还可扩展到图等更复杂的数据结构。记住核心思想：用队列管理待访问节点，逐层推进。希望这篇关于BFS算法实现的入门指南对你有所帮助！

掌握二叉树层序遍历，是迈向高级算法的重要一步。动手试试吧！