深度遍历树（通常指二叉树或通用树）的算法核心是**深度优先搜索（DFS）**。根据访问根节点的时机不同，可以分为三种主要遍历方式：**前序遍历（根->左->右）、中序遍历（左->根->右）、后序遍历（左->右->根）**[ref_1]。其实现方式主要有递归和非递归（使用栈模拟递归）两种。 下面的Python代码将定义一个简单的二叉树节点类 `TreeNode`，并使用递归与非递归两种方式实现这三种遍历，以及一个通用的树DFS示例[ref_3][ref_4]。 首先，定义二叉树的数据结构： ```python # 定义二叉树节点类 class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right ``` ### 1. 递归实现 递归实现是最直观的方式，直接映射了三种遍历的定义[ref_1][ref_4]。 ```python class RecursiveTraversal: """递归遍历二叉树""" def preorder(self, root): """前序遍历：根 -> 左 -> 右 [ref_1][ref_4]""" res = [] def dfs(node): if not node: return res.append(node.val) # 访问根节点 dfs(node.left) # 递归遍历左子树 dfs(node.right) # 递归遍历右子树 dfs(root) return res def inorder(self, root): """中序遍历：左 -> 根 -> 右 [ref_1][ref_3]""" res = [] def dfs(node): if not node: return dfs(node.left) # 递归遍历左子树 res.append(node.val) # 访问根节点 dfs(node.right) # 递归遍历右子树 dfs(root) return res def postorder(self, root): """后序遍历：左 -> 右 -> 根 [ref_1][ref_3]""" res = [] def dfs(node): if not node: return dfs(node.left) # 递归遍历左子树 dfs(node.right) # 递归遍历右子树 res.append(node.val) # 访问根节点 dfs(root) return res ``` ### 2. 非递归（迭代）实现 非递归实现需要显式地使用**栈（Stack）** 来模拟递归调用栈的过程[ref_1][ref_4]。这是DFS的迭代实现方式[ref_2]。 ```python class IterativeTraversal: """使用栈的非递归（迭代）遍历二叉树""" def preorder(self, root): """迭代前序遍历 [ref_1][ref_4]""" res = [] stack = [] cur = root while stack or cur: # 不断将当前节点及其右、左子节点入栈，实现“根-左-右”顺序 while cur: res.append(cur.val) # 访问根节点 # 先将右孩子入栈，再处理左孩子，因为栈是LIFO if cur.right: stack.append(cur.right) cur = cur.left if stack: cur = stack.pop() # 弹出栈顶节点作为新的当前节点 return res def inorder(self, root): """迭代中序遍历 [ref_1][ref_4]""" res = [] stack = [] cur = root while stack or cur: # 一直向左走到底，将沿途节点入栈 while cur: stack.append(cur) cur = cur.left # 弹出栈顶节点并访问（此时它的左子树已处理完） cur = stack.pop() res.append(cur.val) # 访问根节点 # 转向右子树 cur = cur.right return res def postorder(self, root): """迭代后序遍历 [ref_1][ref_4] 技巧：后序遍历是`左右根`，可以按`根右左`的顺序遍历再反转结果。 """ if not root: return [] res = [] stack = [root] while stack: cur = stack.pop() res.append(cur.val) # 将当前节点值加入结果列表 # 先左后右入栈，出栈顺序就是先右后左，从而实现“根->右->左” if cur.left: stack.append(cur.left) if cur.right: stack.append(cur.right) # 将“根右左”的结果反转，即得到“左右根”的后序遍历 return res[::-1] ``` ### 3. 通用树的深度遍历示例 对于多叉树（非二叉树），其节点结构稍作调整，DFS遍历逻辑类似，通常采用前序遍历或后序遍历。 ```python # 定义通用树（多叉树）的节点 class MultiTreeNode: def __init__(self, val=0, children=None): self.val = val self.children = children if children is not None else [] class MultiTreeDFS: """多叉树的深度优先遍历""" def dfs_preorder(self, root): """多叉树前序遍历：根 -> 子节点1 -> 子节点2 -> ... [ref_6]""" res = [] def dfs(node): if not node: return res.append(node.val) # 访问当前节点 for child in node.children: # 递归遍历所有子节点 dfs(child) dfs(root) return res def dfs_postorder(self, root): """多叉树后序遍历：子节点1 -> 子节点2 -> ... -> 根 [ref_6]""" res = [] def dfs(node): if not node: return for child in node.children: # 递归遍历所有子节点 dfs(child) res.append(node.val) # 最后访问当前节点 dfs(root) return res ``` ### 4. 算法测试与应用 为了验证上述算法的正确性，我们构建一个示例二叉树并运行遍历。 ```python # 构建一个示例二叉树: 1 # / \ # 2 3 # / \ \ # 4 5 6 root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) root.right.right = TreeNode(6) rt = RecursiveTraversal() it = IterativeTraversal() print("=== 递归遍历 ===") print(f"前序: {rt.preorder(root)}") # 预期输出: [1, 2, 4, 5, 3, 6] print(f"中序: {rt.inorder(root)}") # 预期输出: [4, 2, 5, 1, 3, 6] print(f"后序: {rt.postorder(root)}") # 预期输出: [4, 5, 2, 6, 3, 1] print("\n=== 迭代遍历 ===") print(f"前序: {it.preorder(root)}") # 预期输出: [1, 2, 4, 5, 3, 6] print(f"中序: {it.inorder(root)}") # 预期输出: [4, 2, 5, 1, 3, 6] print(f"后序: {it.postorder(root)}") # 预期输出: [4, 5, 2, 6, 3, 1] ``` ### 5. 核心要点与对比 深度优先搜索（DFS）遍历树的核心在于选择何时“处理”（或访问）当前节点。递归方法代码简洁，易于理解，但存在函数调用栈溢出的风险（对于极深的树）；迭代方法使用显式栈，避免了递归深度限制，逻辑上稍复杂[ref_2][ref_6]。 下表总结了三种遍历方式的访问顺序和主要应用场景： | 遍历方式 | 访问顺序 (二叉树) | 核心应用场景举例 | | :--- | :--- | :--- | | **前序遍历** | 根节点 -> 左子树 -> 右子树 | 复制树结构、序列化二叉树、前缀表达式[ref_3][ref_5] | | **中序遍历** | 左子树 -> 根节点 -> 右子树 | **二叉搜索树**得到有序序列、表达式树求值[ref_3][ref_5] | | **后序遍历** | 左子树 -> 右子树 -> 根节点 | 删除树、计算表达式树、求树的高度[ref_3][ref_5] | **复杂度分析**：对于一棵有 `n` 个节点的树，无论递归还是迭代实现，三种遍历方式的**时间复杂度均为 O(n)**，因为每个节点恰好被访问一次。**空间复杂度**在递归版本中取决于递归深度，最坏情况（树退化成链）为 O(n)；迭代版本中，显式栈的最大空间消耗在最坏情况下也为 O(n)[ref_1][ref_2]。