数据结构与算法 / 系统课时

二叉树的深度优先遍历

二叉树的深度优先遍历

深度优先遍历沿一条分支尽可能向下,再回退处理其他分支。本课用一个统一递归函数实现前序、中序和后序遍历,重点理解“访问根节点”在递归流程中的不同位置。

学习目标

  • 说清前序、中序和后序遍历的访问规则
  • 使用递归实现三种深度优先遍历
  • 分析遍历的时间复杂度与递归空间

三种顺序的本质

递归处理二叉树时始终包含三个动作:处理当前根节点、遍历左子树、遍历右子树。三种遍历只改变“处理根节点”的时机:

  • 前序:根、左、右
  • 中序:左、根、右
  • 后序:左、右、根

空节点是递归终止条件。前序适合先记录结构,中序遍历二叉搜索树可得到升序序列,后序适合先得到子树结果再汇总当前节点。

二叉树三种深度优先遍历顺序

统一递归框架

与其维护三份高度重复的代码,可以把遍历顺序作为参数。递归函数进入节点、完成左子树、完成右子树三个时点,正好对应前序、中序和后序的访问位置。

主示例:一个函数完成三种遍历

python
class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def traverse(node, order):
    if order not in {"pre", "in", "post"}:
        raise ValueError("order 必须是 pre、in 或 post")

    result = []

    def dfs(current):
        if current is None:
            return

        # 根节点的记录位置决定遍历类型
        if order == "pre":
            result.append(current.value)

        dfs(current.left)

        if order == "in":
            result.append(current.value)

        dfs(current.right)

        if order == "post":
            result.append(current.value)

    dfs(node)
    return result

root = Node(
    "A",
    Node("B", Node("D"), Node("E")),
    Node("C", None, Node("F")),
)

print("前序:", traverse(root, "pre"))
print("中序:", traverse(root, "in"))
print("后序:", traverse(root, "post"))

预期输出

text
前序: ['A', 'B', 'D', 'E', 'C', 'F']
中序: ['D', 'B', 'E', 'A', 'C', 'F']
后序: ['D', 'E', 'B', 'F', 'C', 'A']

复杂度与使用边界

无论采用哪种顺序,每个节点都恰好访问一次,因此时间复杂度为 O(n)O(n)。递归栈深度等于当前根到叶子的路径长度,空间复杂度为 O(h)O(h);平衡树中通常为 O(log⁡n)O(\log n),退化成链表时为 O(n)O(n)。

中序结果只有在二叉搜索树满足左子树值小于根、右子树值大于根等排序约束时才天然有序。普通二叉树使用中序遍历,并不能保证输出有序。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

二叉树的深度优先遍历

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通