当前位置：首页 > article >正文

【数据结构】树的遍历：先序、中序、后序和层序

article 2025/1/11 6:57:40

在数据结构中，树（Tree）作为一种基础的非线性结构，广泛应用于多种场景。树的遍历是树操作中的重要组成部分，它决定了我们如何访问树中的每一个节点。树的遍历方法有多种，每种方法适用于不同的场景，且每种方法的访问顺序不同。

本文将深入探讨四种常见的树的遍历方式：先序遍历、中序遍历、后序遍历和层序遍历。我们将通过图示、符号表示以及清晰的解释，帮助你掌握这些遍历方法，并理解它们的应用场景和区别。

本文需要读者对数的概念有基本认知，若不了解可参考以下博文

【数据结构】树的定义

文章目录

- 树的基本概念
- - 树的定义
  - 深度优先遍历（DFS）
  - 广度优先遍历（BFS）
- 先序遍历（Preorder Traversal）
- - 定义
  - 示例
  - 代码示例
- 中序遍历（Inorder Traversal）
- - 定义
  - 示例
  - 代码示例
- 后序遍历（Postorder Traversal）
- - 定义
  - 示例
  - 代码示例
- 层序遍历（Level Order Traversal）
- - 定义
  - 示例
  - 层序遍历的代码示例
- 总结

树的基本概念

树的定义

树是一种由节点（Node）和边（Edge）组成的层次型数据结构。树中有一个唯一的根节点（Root Node），每个节点可以有多个子节点（Child Node），但只能有一个父节点（Parent Node）。树的节点之间通过边相连，形成一个有序的层级结构。

例如，一棵简单的二叉树（Binary Tree）可能如下所示：

在这棵树中：

根节点是A。
B和C是A的子节点。
D和E是B的子节点，F是C的子节点。
D、E、F都是叶子节点（没有子节点）。

树的遍历方法决定了我们访问节点的顺序。树的遍历可以分为两类：深度优先遍历（DFS）和广度优先遍历（BFS）。

深度优先遍历（DFS）

深度优先遍历是指从树的根节点开始，沿着树的深度遍历尽可能深的节点。深度优先遍历有三种常见的方式：先序遍历、中序遍历和后序遍历。

广度优先遍历（BFS）

广度优先遍历是指从树的根节点开始，先访问根节点的所有子节点，再逐层向下访问其他节点。广度优先遍历又叫层序遍历。

先序遍历（Preorder Traversal）

定义

先序遍历是深度优先遍历的一种方式。其遍历顺序为：

访问根节点。
遍历左子树。
遍历右子树。

在先序遍历中，根节点总是最先被访问，因此这种遍历方法也被称为根-左-右遍历。

示例

我们以下面这棵二叉树为例，来说明先序遍历的过程：

先序遍历的步骤：

访问根节点A。
遍历A的左子树（B）。
- 访问根节点B。
- 遍历B的左子树（D）。
  - 访问节点D。
- 遍历B的右子树（E）。
  - 访问节点E。
遍历A的右子树（C）。
- 访问根节点C。
- 遍历C的右子树（F）。
  - 访问节点F。

先序遍历的顺序为： A → B → D → E → C → F。

代码示例

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

def preorder_traversal(root):
    if root:
        print(root.value, end=' ')  # 访问根节点
        preorder_traversal(root.left)  # 遍历左子树
        preorder_traversal(root.right)  # 遍历右子树

# 构造示例树
root = TreeNode('A')
root.left = TreeNode('B')
root.right = TreeNode('C')
root.left.left = TreeNode('D')
root.left.right = TreeNode('E')
root.right.right = TreeNode('F')

preorder_traversal(root)  # 输出: A B D E C F

中序遍历（Inorder Traversal）

定义

中序遍历是深度优先遍历的另一种方式。其遍历顺序为：

遍历左子树。
访问根节点。
遍历右子树。

在中序遍历中，根节点位于左子树和右子树之间，因此这种遍历方法也被称为左-根-右遍历。

示例

以相同的二叉树为例，说明中序遍历的过程：

中序遍历的步骤：

遍历A的左子树（B）。
- 遍历B的左子树（D）。
  - 访问节点D。
- 访问根节点B。
- 遍历B的右子树（E）。
  - 访问节点E。
访问根节点A。
遍历A的右子树（C）。
- 遍历C的右子树（F）。
  - 访问节点F。
- 访问节点C。

中序遍历的顺序为： D → B → E → A → F → C。

代码示例

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)  # 遍历左子树
        print(root.value, end=' ')  # 访问根节点
        inorder_traversal(root.right)  # 遍历右子树

inorder_traversal(root)  # 输出: D B E A F C

后序遍历（Postorder Traversal）

定义

后序遍历是深度优先遍历的第三种方式。其遍历顺序为：

遍历左子树。
遍历右子树。
访问根节点。

在后序遍历中，根节点最后被访问，因此这种遍历方法也被称为左-右-根遍历。

示例

以相同的二叉树为例，说明后序遍历的过程：

后序遍历的步骤：

遍历A的左子树（B）。
- 遍历B的左子树（D）。
  - 访问节点D。
- 遍历B的右子树（E）。
  - 访问节点E。
- 访问根节点B。
遍历A的右子树（C）。
- 遍历C的右子树（F）。
  - 访问节点F。
- 访问节点C。
访问根节点A。

后序遍历的顺序为： D → E → B → F → C → A。

代码示例

def postorder_traversal(root):
    if root:
        postorder_traversal(root.left)  # 遍历左子树
        postorder_traversal(root.right)  # 遍历右子树
        print(root.value, end=' ')  # 访问根节点

postorder_traversal(root)  # 输出: D E B F C A

层序遍历（Level Order Traversal）

定义

层序遍历是一种广度优先遍历方法。其遍历顺序为：

访问根节点。
按层次从上到下、从左到右依次访问树的其他节点。

层序遍历采用队列（Queue）来实现，因为队列遵循先进先出（FIFO）的特性，能够确保按层次遍历。

示例

以相同的二叉树为例，说明层序遍历的过程：

层序遍历的步骤：

访问根节点A。
访问A的子节点B和C。
访问B的子节点D和E，访问C的子节点F。

层序遍历的顺序为： A → B → C → D → E → F。

层序遍历的代码示例

from collections import deque

def level_order_traversal(root):
    if not root:
        return
    queue = deque([root])  # 初始化队列，先将根节点入队
    while queue:
        node = queue.popleft()  # 出队一个节点
        print(node.value, end=' ')  # 访问节点
        if node.left:
            queue.append(node.left)  # 将左子节点入队
        if node.right:
            queue.append(node.right)  # 将右子节点入队

level_order_traversal(root)  # 输出: A B C D E F