Python遍历二叉树：递归DFS与迭代BFS实现

"本文主要介绍了在Python中遍历二叉树的两种常见方法，即深度优先搜索（DFS）和广度优先搜索（BFS），并提供了相应的递归和迭代实现代码示例。" 在Python中处理数据结构时，二叉树是一种重要的抽象概念，它由节点组成，每个节点有两个子节点——左子节点和右子节点。遍历二叉树是指按照特定顺序访问树中的所有节点。这里我们将深入探讨如何通过深度优先搜索和广度优先搜索来遍历二叉树。 深度优先搜索（DFS） 是一种遍历策略，它首先访问根节点，然后尽可能深地探索子树。DFS分为前序遍历、中序遍历和后序遍历三种方式。在Python中，通常使用递归实现DFS。以下是使用递归进行前序遍历 的DFS示例： ```python class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None def dfs_recursion(node): if node is None: return print(node.val) # 先访问当前节点 dfs_recursion(node.left) # 递归遍历左子树 dfs_recursion(node.right) # 递归遍历右子树 # 创建一个二叉树 root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) # 进行前序遍历 dfs_recursion(root) ``` 广度优先搜索（BFS） 是另一种遍历策略，它按照从根节点到叶节点的最短路径（层次顺序）访问节点。BFS通常使用队列数据结构实现。以下是一个使用迭代进行BFS 的示例： ```python from collections import deque class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None def bfs_iterative(root): if root is None: return queue = deque() queue.append(root) while queue: node = queue.popleft() # 访问当前节点 print(node.val) # 将左子节点加入队列 if node.left: queue.append(node.left) if node.right: queue.append(node.right) # 创建一个二叉树 root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) # 进行广度优先遍历 bfs_iterative(root) ``` 在实际应用中，DFS和BFS各有优缺点。DFS适合于查找路径或解决回溯问题，而BFS则适用于查找最近的邻居或解决最短路径问题。根据具体问题的需求，选择合适的遍历策略是至关重要的。理解这两种遍历方法的原理和实现，对于处理二叉树和其他树形结构的数据问题具有重要意义。