二叉树遍历

为了理解二叉树的遍历，我们可以把它想象成对一个 “树状结构” 的节点进行有序访问。二叉树是一种特殊的树形结构，每个节点最多有两个子节点，分别是 “左子节点” 和 “右子节点”。“遍历” 指的是按照某种规则依次访问树中的每一个节点。

我们定义一个简单的二叉树结构，接着实现各种遍历。

创建一个简单的二叉树

1
2
3
4
5
    A
   / \
  B   C
 / \
D   E

用代码表示：

1
2
3
4
5
6
# 创建节点
root = TreeNode("A")
root.left = TreeNode("B")
root.right = TreeNode("C")
root.left.left = TreeNode("D")
root.left.right = TreeNode("E")

二叉树的 BFS

BFS 需要借助 队列 来实现。队列的作用是按层次遍历节点，先访问根节点，再访问它的子节点，再访问子节点的子节点，直到所有节点都被访问。

实践

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from collections import deque

def bfs(root):
    if root is None:
        return []
    
    result = []  # 用于存储遍历结果
    queue = deque([root])  # 使用队列来存储节点，初始时加入根节点
    
    while queue:
        node = queue.popleft()  # 从队列中取出一个节点
        result.append(node.value)  # 访问当前节点
        
        # 如果左子节点存在，将左子节点加入队列
        if node.left:
            queue.append(node.left)
        
        # 如果右子节点存在，将右子节点加入队列
        if node.right:
            queue.append(node.right)
    
    return result

print("BFS遍历结果：", bfs(root))

二叉树的 DFS

二叉树的 DFS 方式主要分为以下三种：

  1. 前序遍历 (Preorder Traversal)
  2. 中序遍历 (Inorder Traversal)
  3. 后序遍历 (Postorder Traversal)

什么是前序、中序、后序遍历？

这些遍历方式的核心区别在于访问节点的顺序。假设我们从根节点（最顶端）开始，分别按以下规则访问：

1. 前序遍历：

按顺序访问 “根节点 → 左子树 → 右子树”。

2. 中序遍历：

按顺序访问 “左子树 → 根节点 → 右子树”。

3. 后序遍历：

按顺序访问 “左子树 → 右子树 → 根节点”。

实践

实现前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
def preorder_traversal(node):
    result = []  # 用于存储遍历结果
    def helper(n):
        if n is None:
            return
        result.append(n.value)  # 访问当前节点，加入到结果列表
        helper(n.left)  # 遍历左子树
        helper(n.right)  # 遍历右子树
    helper(node)
    return result

print("前序遍历结果：", preorder_traversal(root))

实现中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
def inorder_traversal(node):
    result = []  # 用于存储遍历结果
    def helper(n):
        if n is None:
            return
        helper(n.left)  # 遍历左子树
        result.append(n.value)  # 访问当前节点，加入到结果列表
        helper(n.right)  # 遍历右子树
    helper(node)
    return result

print("中序遍历结果：", inorder_traversal(root))

实现后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
def postorder_traversal(node):
    result = []  # 用于存储遍历结果
    def helper(n):
        if n is None:
            return
        helper(n.left)  # 遍历左子树
        helper(n.right)  # 遍历右子树
        result.append(n.value)  # 访问当前节点，加入到结果列表
    helper(node)
    return result

print("后序遍历结果：", postorder_traversal(root))

总结

假设树的结构如下：

1
2
3
4
5
    A
   / \
  B   C
 / \
D   E
遍历方式 顺序 输出结果
前序遍历 根 → 左 → 右 A B D E C
中序遍历 左 → 根 → 右 D B E A C
后序遍历 左 → 右 → 根 D E B C A