如何实现二叉树的遍历？-Python教程-PHP中文网

答案是二叉树遍历分为前序、中序、后序和层序四种，分别采用递归或迭代实现，用于系统访问节点，处理空节点需加判断，广泛应用于表达式求值、序列化、LCA查找等场景。

如何实现二叉树的遍历？

二叉树的遍历，说白了，就是按照某种特定的规则，把树上的每一个节点都“走”一遍，访问一遍。最核心的无非是三种深度优先遍历（前序、中序、后序）和一种广度优先遍历（层序遍历）。它们各自有其独特的访问顺序，但目的都是为了系统地处理树中的所有数据。

解决方案

要实现二叉树的遍历，我们主要依靠递归和迭代两种编程范式。每种遍历方式都有其递归和迭代的实现逻辑，理解它们是掌握二叉树操作的关键。

1. 前序遍历（Pre-order Traversal） 顺序：根节点 -> 左子树 -> 右子树这种遍历方式，我通常会先处理当前节点，然后再深入其左侧分支，最后才转向右侧。它就像一个急于汇报的领导，总想先说自己的事，再安排下属的工作。

递归实现

def preorder_recursive(node):
    if node is None:
        return
    print(node.val)  # 访问根节点
    preorder_recursive(node.left) # 递归遍历左子树
    preorder_recursive(node.right) # 递归遍历右子树

登录后复制

迭代实现 迭代实现通常需要一个栈来辅助。

def preorder_iterative(root):
    if root is None:
        return
    stack = [root]
    while stack:
        node = stack.pop()
        print(node.val)
        # 先压右孩子，再压左孩子，确保左孩子先被处理
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

登录后复制

2. 中序遍历（In-order Traversal） 顺序：左子树 -> 根节点 -> 右子树中序遍历在我看来是最“平衡”的遍历方式，它总是先深入左侧，处理完左边的事，再回头看自己（根节点），最后才去处理右侧。对于二叉搜索树（BST），中序遍历能得到一个有序序列，这简直是它的杀手锏。

递归实现

def inorder_recursive(node):
    if node is None:
        return
    inorder_recursive(node.left)
    print(node.val) # 访问根节点
    inorder_recursive(node.right)

登录后复制

迭代实现 中序的迭代实现稍微复杂一些，因为它需要在处理完左子树后才能访问根节点，这需要巧妙地利用栈来“记住”父节点。

def inorder_iterative(root):
    stack = []
    current = root
    while current or stack:
        # 一直向左，直到没有左孩子
        while current:
            stack.append(current)
            current = current.left

        # 弹出栈顶元素，访问它
        current = stack.pop()
        print(current.val)

        # 转向右孩子
        current = current.right

登录后复制

3. 后序遍历（Post-order Traversal） 顺序：左子树 -> 右子树 -> 根节点后序遍历给我的感觉是“先处理好所有子问题，最后再解决自己”。它在删除树节点或者计算表达式树的时候特别有用，因为你得先确保所有依赖都处理完了，才能动根节点。

递归实现

def postorder_recursive(node):
    if node is None:
        return
    postorder_recursive(node.left)
    postorder_recursive(node.right)
    print(node.val) # 访问根节点

登录后复制

迭代实现 后序遍历的迭代实现是最让人头疼的，它通常有两种思路：一种是使用两个栈，另一种是使用一个栈但需要额外标记节点是否已访问右子树。这里给一个相对直观的，通过修改前序遍历思路来实现的方法（根-右-左的逆序）。

def postorder_iterative(root):
    if root is None:
        return
    stack = [root]
    output = [] # 用一个列表暂存结果，最后反转
    while stack:
        node = stack.pop()
        output.append(node.val)
        # 先压左孩子，再压右孩子，确保右孩子先被处理
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

    # 逆序输出，得到左-右-根的顺序
    for val in reversed(output):
        print(val)

登录后复制

4. 层序遍历（Level-order Traversal） 顺序：逐层从左到右层序遍历是一种广度优先搜索（BFS）的体现，它从根节点开始，一层一层地访问节点。这就像你在看一本书，总是先看完当前页，再看下一页，而不是跳到某一章的深处。它通常用队列来实现。

实现

from collections import deque

def levelorder_traversal(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)

登录后复制

递归与迭代：哪种遍历方式更适合我？

这问题问得好，因为这不单单是二叉树遍历的问题，更是很多算法选择的通用困境。我的经验是，没有绝对的“更好”，只有更适合特定场景和个人偏好的。

递归实现

优点： 代码通常非常简洁、直观，与树的定义（递归结构）完美契合。你几乎可以把树的定义直接翻译成递归代码，这对于理解算法逻辑非常有帮助。初学时我总觉得递归是黑魔法，但一旦理解了它的“信任”机制（即假设子问题能正确解决），就觉得它优雅得不行。
缺点： 最大的隐患就是栈溢出（Stack Overflow）。如果树的深度非常大，每次函数调用都会在调用栈上开辟新的帧，这可能耗尽系统栈空间。此外，函数调用的开销相对直接的循环会大一些，对性能有极致要求的场景可能需要考虑。

迭代实现

优点： 避免了递归带来的栈溢出风险，尤其是在处理深度未知或可能非常深的树时，迭代是更稳健的选择。通常，迭代的性能会更稳定，没有函数调用栈的额外开销。在生产环境中，尤其面对不确定树深度的场景，它的鲁棒性让我更安心。
缺点： 代码通常比递归版本复杂，特别是中序和后序遍历的迭代实现，需要巧妙地使用栈来模拟递归栈的行为，这需要对算法逻辑有更深的理解。有时候，为了避免递归，迭代的代码会显得有些“不自然”，甚至有点绕。

如何选择？

学习和原型开发： 递归是首选。它能让你更快地理解算法的核心思想，代码也更容易编写和调试。
生产环境和性能敏感场景： 如果树的深度可能很大（比如几十万层），或者对运行性能有严格要求，那么迭代实现会是更安全、更高效的选择。
个人偏好： 最终，选择哪种方式也受个人编程习惯影响。有些人就是喜欢递归的简洁，有些人则偏爱迭代的控制感。我个人在面试时倾向于先给出递归解，再尝试优化为迭代解，以展示对两种方法的掌握。

如何处理二叉树遍历中的空节点或特殊情况？

处理空节点和特殊情况，是编写健壮的二叉树代码的基础。这不仅仅是“避免报错”，更是确保算法逻辑正确性的关键。

1. 空节点（None/null）的处理：

宣小二

宣小二：媒体发稿平台，自媒体发稿平台，短视频矩阵发布平台，基于AI驱动的企业自助式投放平台。

查看详情

递归中的基线条件： 这是最核心的。无论哪种递归遍历，当传入的
```
node
```
登录后复制
为
```
None
```
登录后复制
时，都应该立即返回，不执行任何操作。这构成了递归的终止条件，否则会导致无限递归。
```
def some_recursive_traversal(node):
    if node is None: # 核心判断
        return
    # ... 访问节点或递归调用 ...
```
登录后复制
迭代中的入队/入栈判断： 在迭代遍历中，无论是将子节点入队（层序遍历）还是入栈（深度优先迭代），都必须先判断子节点是否为空。只有非空的节点才应该被加入到辅助数据结构中。
```
# 层序遍历
if node.left:
    queue.append(node.left)
if node.right:
    queue.append(node.right)

# 深度优先迭代
if node.right: # 注意这里是先压右后压左，确保左先处理
    stack.append(node.right)
if node.left:
    stack.append(node.left)
```
登录后复制
如果错误地将
```
None
```
登录后复制
节点入队或入栈，会导致后续处理时出现
```
AttributeError
```
登录后复制
（因为
```
None
```
登录后复制
没有
```
val
```
登录后复制
或
```
left
```
登录后复制
/
```
right
```
登录后复制
属性）。

2. 单节点树的处理： 如果树只包含一个根节点，没有左右子树，所有遍历方法都应该能正确处理。

递归：根节点会被访问，然后左右子树的递归调用会立即遇到
```
None
```
登录后复制
并返回，不会出错。
迭代：根节点会被正确地入栈/入队，然后被访问。其
```
left
```
登录后复制
和
```
right
```
登录后复制
属性为
```
None
```
登录后复制
，不会被加入到辅助结构中，循环自然终止。

3. 空树（根节点为None）的处理： 这是最外层的特殊情况。如果一开始传入的

root

登录后复制

就是

None

登录后复制

，那么无论递归还是迭代，都应该在入口处进行判断，直接返回，不执行任何遍历操作。

def some_traversal_function(root):
    if root is None: # 最外层判断
        return
    # ... 遍历逻辑 ...

登录后复制

忽略这个判断，虽然递归可能因基线条件而安全返回，但迭代实现如果直接尝试对

None

登录后复制

进行操作（如

stack = [root]

登录后复制

），则可能在某些语言或特定实现中引发错误。

个人经验/挑战： 有时候在迭代实现中，尤其是后序遍历，判断何时弹出节点并访问，何时继续向右子树探索，会让人头疼。这需要对栈的LIFO特性和遍历逻辑有深刻理解。我记得有一次，我为了避免使用两个栈实现后序迭代，尝试用一个栈加一个

last_visited

登录后复制

变量来判断，结果因为逻辑判断的微小疏忽，导致了无限循环。这说明对边界条件的思考和测试是多么重要。

除了基础遍历，二叉树遍历还有哪些高级应用场景？

二叉树遍历远不止是把所有节点走一遍那么简单，它更像是一种基础工具，通过选择不同的遍历方式，我们可以揭示树结构中隐藏的特定信息或关系，进而解决更复杂的问题。它不是目的，而是解决问题的手段。

1. 表达式求值与转换：

后缀表达式求值： 计算机在处理数学表达式时，通常会将其转换为后缀表达式（逆波兰表示法）。如果将表达式构建成一棵二叉树（操作符作为根节点，操作数作为叶节点），那么对这棵树进行后序遍历，就能得到后缀表达式，进而进行求值。比如
```
(A + B) * C
```
登录后复制
的树，后序遍历是
```
A B + C *
```
登录后复制
。
中缀转前缀/后缀： 类似地，通过不同的遍历方式，可以将中缀表达式转换为前缀或后缀表达式。

2. 序列化与反序列化：

将一棵二叉树保存到文件或在网络上传输，就需要将其“序列化”成一个线性序列。前序遍历或层序遍历，配合对空节点的特殊标记（比如用
```
#
```
登录后复制
或
```
null
```
登录后复制
），可以唯一地表示一棵树。
反过来，拿到这个序列后，我们也能“反序列化”重建出原始的二叉树。这是数据存储和传输的关键技术。

3. 查找最近公共祖先（LCA）：

给定树中的两个节点，找到它们在树中的最近公共祖先。这可以通过对树进行深度优先遍历（无论是前序、中序还是后序的变种）来完成。在遍历过程中，我们可以记录从根到当前节点的路径，然后找到两条路径的最后一个共同节点。更高效的方法是利用递归的性质，判断当前节点是否是两个目标节点的祖先。

4. 树的深度、高度与平衡性判断：

层序遍历非常自然地就能计算出树的深度或高度，因为它是逐层访问的。每访问完一层，深度就加一。
深度优先遍历也可以计算深度，通常通过递归函数返回子树的高度，然后取最大值加一。
在计算高度的同时，可以顺便判断二叉树是否是平衡二叉树（左右子树的高度差不超过1）。这通常在后序遍历的思路上进行，因为我们需要先知道子树的高度才能判断当前节点是否平衡。

5. 路径查找与路径和问题：

寻找从根节点到任意目标节点的路径，或者寻找所有从根节点到叶节点的路径。这通常通过深度优先遍历来完成，在递归调用时传递当前路径，并在到达目标或叶节点时记录路径。
“路径总和”问题，比如找出所有从根到叶子节点，其路径和等于给定值的路径，也是通过深度优先遍历并在递归过程中累加当前路径和来解决。

个人思考： 遍历，对我来说，不仅仅是简单的“走一遍”。它更像是一个观察者，以不同的视角审视二叉树这个复杂结构。前序遍历是自上而下的俯瞰，中序遍历是左右均衡的审视，后序遍历是先微观再宏观的总结，而层序遍历则是横向的扫描。理解这些视角，并知道何时选择哪种视角，是解决许多复杂树相关问题的钥匙。它让我们能够从数据结构中提取出我们真正需要的信息。

以上就是如何实现二叉树的遍历？的详细内容，更多请关注php中文网其它相关文章！