python层序遍历二叉树

在Python中，层序遍历（也称为广度优先遍历）二叉树是一种按层次顺序访问节点的方法，从根节点开始，逐层向下遍历。这种遍历方式通常使用队列来辅助实现，因为队列的特点是先进先出（FIFO），非常适合用来处理需要按照顺序访问同一层级节点的情况。

以下是层序遍历二叉树的基本步骤：

1. 如果二叉树为空，则直接结束遍历。
2. 创建一个空的队列，并将根节点（如果存在）入队。
3. 当队列不为空时，执行以下操作：
a. 弹出队首元素（当前层的第一个节点）并访问它。
b. 将该节点的左右子节点（如果存在）分别入队，以便后续访问。
4. 重复步骤3，直到队列为空。

以下是一个简单的Python代码实现：

from collections import deque

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def level_order_traversal(root):
    if root is None:
        return []

    queue = deque([root])  # 使用双端队列存储节点
    result = []

    while queue:
        level_nodes = []  # 用于存放当前层的节点值
        size = len(queue)

        for _ in range(size):
            node = queue.popleft()  # 弹出队首节点
            level_nodes.append(node.value)

            if node.left:  # 如果有左子节点，入队
                queue.append(node.left)
            if node.right:  # 如果有右子节点，入队
                queue.append(node.right)

        result.append(level_nodes)  # 将当前层节点值添加到结果列表

    return result

# 示例
# 假设我们有如下二叉树
#     1
#    / \
#   2   3
#  / \   \
# 4   5   6
root = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6)))

print(level_order_traversal(root))  # 输出: [, [2, 3], [4, 5, 6]]