树与二叉树：遍历与递归

FreeGuideOnline 最新 2026-06-18

树与二叉树：从结构到遍历的深度指南

你是否曾在文件夹系统中迷失方向，或对网页的 DOM 树感到好奇？这一切的背后，都是一种名为“树”的数据结构。本教程将带你从零开始，理解树的本质，掌握最核心的二叉树，并最终用清晰的递归思维完成所有遍历操作。无需畏惧理论，我们将通过大量类比与可运行的代码，将其内化为你的本能。

1. 为什么我们需要树？告别线性思维

到目前为止，你可能熟悉数组、链表这类“一对一”的线性结构。但现实世界充满了层次关系：操作系统中的文件目录、公司的组织架构、文章的标题层级。树，就是用来表达这种 “一对多”层次关系 的数据结构。

与数组不同，树中的元素并非按顺序排列，而是按“父子”关系连接。理解这个区别，是你数据结构思维升级的第一步。

2. 树的基本概念：像一本倒置的书

想象一棵倒置的树，根在上，叶子在下。我们从最基础的术语开始：

节点：树中的每一个数据元素。例如，文件系统中的一个文件夹。
根节点：整棵树最顶层的唯一节点，没有父节点。操作系统的 C:\ 或 / 根目录就是根。
父节点与子节点：若节点 A 直接连接到节点 B 并处于上层，则 A 是 B 的父节点，B 是 A 的子节点。
叶子节点：没有子节点的节点。也就是树的末端。
兄弟节点：拥有同一个父节点的多个节点。
子树：树中任一节点及其所有后代构成的集合，它本身也是一棵树。
深度与高度：常被混淆。某节点的深度是从根到该节点的路径长度（根深度为0）；某节点的高度是从该节点到最远叶子节点的路径长度。整棵树的高度即为根节点的高度。

树的定义是递归的：一棵树由根节点和若干棵子树构成，而子树本身也是树。这奠定了递归遍历的天然基础。

3. 二叉树：最重要的树

在众多树的变体中，二叉树 是应用最广、最高效的一种。它的定义极其严格：

每个节点最多只能有两个子节点，分别称为左子节点和右子节点。

请注意，二叉树不是普通的“二度树”。它严格区分左右，即使只有一个孩子，也必须明确是左孩子还是右孩子。这为搜索和排序带来了巨大优势。

3.1 二叉树的常见形态

满二叉树：除叶子节点外，每个节点都有两个子节点。所有叶子都在同一层。形态极为对称。
完全二叉树：除去最底层，其余层全部填满，且最底层的叶子节点都向左对齐。这种特性使其可以高效地用数组存储，例如堆结构。
二叉搜索树：一种有序二叉树，左子树上所有节点的值 < 根节点的值 < 右子树上所有节点的值。它让查找像玩猜数字游戏一样高效。

3.2 链式存储：像构造链表那样构造树

二叉树最直观的存储方式是链式结构。每个节点包含三部分：数据域、指向左子节点的指针、指向右子节点的指针。

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

你可以用这段简单的代码，手动搭建任意一棵二叉树：

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')

4. 二叉树的遍历：访问的艺术

遍历，就是按照某种规则，无重复、无遗漏地访问树中所有节点。对于二叉树，我们有四种基础遍历策略，其中前三种均基于深度优先思想，需要递归的完美配合。

4.1 前序遍历 —— 根 → 左 → 右

访问顺序：先访问根节点，然后递归遍历左子树，最后递归遍历右子树。

当你需要复制一棵树，或在序列化时保留树的结构，前序遍历是你的首选。

递归实现：

def preorder_traversal(node):
    if node is None:
        return
    print(node.val, end=' ')     # 1. 访问根
    preorder_traversal(node.left)  # 2. 遍历左子树
    preorder_traversal(node.right) # 3. 遍历右子树

对于上述示例树，输出结果为：A B D E C F。这正是深度优先搜索的典型路径。

4.2 中序遍历 —— 左 → 根 → 右

访问顺序：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。

对于二叉搜索树，中序遍历会得到一个递增的有序序列。这是它最关键的应用。

递归实现：

def inorder_traversal(node):
    if node is None:
        return
    inorder_traversal(node.left)  # 1. 遍历左子树
    print(node.val, end=' ')      # 2. 访问根
    inorder_traversal(node.right) # 3. 遍历右子树

输出：D B E A C F。观察发现，根节点 A 恰好位于输出的中间。

4.3 后序遍历 —— 左 → 右 → 根

访问顺序：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。

当你需要删除一棵树或进行某些自底向上的计算（如统计目录大小）时，后序遍历最合适。因为你只有先处理完孩子，才能安全地处理父节点。

递归实现：

def postorder_traversal(node):
    if node is None:
        return
    postorder_traversal(node.left)  # 1. 遍历左子树
    postorder_traversal(node.right) # 2. 遍历右子树
    print(node.val, end=' ')        # 3. 访问根

输出：D E B F C A。节点 A 最后一个被访问，因为它在递归的归程中被处理。

4.4 层序遍历 —— 广度优先的视野

摆脱递归，使用队列来实现。从根节点开始，逐层从左到右访问。

from collections import deque

def level_order_traversal(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.val, end=' ')
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

输出：A B C D E F。这是人类最直观的阅读顺序，常用于查找最短路径或图形渲染。

5. 递归的本质：相信函数已经实现

很多初学者卡在递归上，是因为总试图在脑中一层层展开。更高效的方法是塑造“递归信念”：

定义明确的功能：我的 order(node) 函数能够完美遍历以 node 为根的树。
处理最小问题：如果 node 是 None，回退。
使用已定义好的功能：在实现中，直接假设 order(node.left) 已经完成了左子树的全部工作，我无需关心细节，只需要组合结果。

这种“信任自己的函数”的思维，是征服递归及所有分治算法的核心心法。

6. 从代码到实践：你能做什么？

熟记遍历序列本身就是一种技能。给你两个序列，能否还原二叉树？

前序 + 中序 可以唯一确定一棵二叉树（前序确定根，中序划左右）。
后序 + 中序 同样可以唯一确定。
前序 + 后序 无法唯一确定（除非是满二叉树），因为无法区分单子树的左右位置。

试着用递归完成这道题：给定前序 ['A','B','D','E','C','F'] 和中序 ['D','B','E','A','C','F']，重建二叉树。你会发现，这正是遍历的逆过程。

7. 总结与下一步

树与二叉树是算法世界的基础语言。我们不仅理解了树的层次语义，更通过递归这把钥匙，打开了三种深度优先遍历的大门。牢记：

前序：根左右，用于拷贝。
中序：左根右，用于二叉搜索树排序。
后序：左右根，用于安全删除。
层序：用队列，广度优先。

当你对遍历的时空复杂度（均为 O(n)）了然于胸，并能随手写出递归边界条件时，你就已经为学习更高级的平衡树、堆、图等结构打下了最坚实的根基。接下来，试着去实现一个二叉搜索树，并运用中序遍历验证你的插入操作，让知识在指尖流动起来。