python中如何实现树的遍历

在Python中，遍历树通常指的是访问二叉树的所有节点，并按照一定的顺序打印出节点的值。以下是几种常见的二叉树遍历方法及其实现：

1. 前序遍历（Pre-order Traversal）

前序遍历的顺序是：根节点 -> 左子树 -> 右子树。

递归实现

```python

def preorder_traversal_recursive（root）:

if root is not None:

print（root.val） 访问根节点

preorder_traversal_recursive（root.left） 递归访问左子树

preorder_traversal_recursive（root.right） 递归访问右子树

迭代实现```python
def preorder_traversal_iterative（root）:
 if root is None:
 return
 stack = [root]
 while stack:
 node = stack.pop（）
 if node is not None:
 print（node.val） 访问根节点
 stack.append（node.right） 先右后左，保证左子树先被访问
 stack.append（node.left）

2. 中序遍历（In-order Traversal）

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

递归实现

```python

def inorder_traversal_recursive（root）:

if root is not None:

inorder_traversal_recursive（root.left） 递归访问左子树

print（root.val） 访问根节点

inorder_traversal_recursive（root.right） 递归访问右子树

迭代实现```python
def inorder_traversal_iterative（root）:
 stack = []
 current = root
 while current is not None or stack:
 while current is not None:
 stack.append（current）
 current = current.left
 current = stack.pop（）
 print（current.val） 访问根节点
 current = current.right

3. 后序遍历（Post-order Traversal）

后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

递归实现

```python

def postorder_traversal_recursive（root）:

if root is not None:

postorder_traversal_recursive（root.left） 递归访问左子树

postorder_traversal_recursive（root.right） 递归访问右子树

print（root.val） 访问根节点

迭代实现```python
def postorder_traversal_iterative（root）:
 if root is None:
 return
 stack = [root]
 last_visited = None
 while stack:
 node = stack[-1]
 if （node.left is None and node.right is None） or \
 （last_visited and （last_visited == node.left or last_visited == node.right））:
 print（node.val） 访问根节点
 last_visited = stack.pop（）
 else:
 if node.right:
 stack.append（node.right）
 if node.left:
 stack.append（node.left）

4. 层序遍历（Breadth-first Traversal）

层序遍历的顺序是从根节点开始，按层次顺序访问所有节点。

迭代实现

```python

from collections import deque

def level_order_traversal_iterative（root）:

if root is None:

return

queue = deque（[root]）

while queue:

node = queue.popleft（）

print（node.val） 访问当前节点

if node.left:

queue.append（node.left）

if node.right:

queue.append（node.right）

以上代码示例中，`TreeNode` 类代表树的节点，每个节点包含一个值 `val` 和指向左右子节点的指针 `left` 和 `right`。递归和迭代实现