python 树_python基础笔记

激活谷笔记 • 2025-01-07 18:56 • 阅读 121

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

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

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

递归实现

 def preorder_traversal_recursive（root）: if root is not None: print（root.val） 访问根节点 preorder_traversal_recursive（root.left） 递归访问左子树 preorder_traversal_recursive（root.right） 递归访问右子树

迭代实现

 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）

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

递归实现

 def inorder_traversal_recursive（root）: if root is not None: inorder_traversal_recursive（root.left） 递归访问左子树 print（root.val） 访问根节点 inorder_traversal_recursive（root.right） 递归访问右子树

迭代实现

 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）

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

递归实现

 def postorder_traversal_recursive（root）: if root is not None: postorder_traversal_recursive（root.left） 递归访问左子树 postorder_traversal_recursive（root.right） 递归访问右子树 print（root.val） 访问根节点

迭代实现

 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）

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

迭代实现

 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`。递归和迭代实现

python 树_python基础笔记

相关推荐