第5章 二叉树与二叉搜索树

---

元数据卡

• 前置知识：数组与链表（第2章）、递归思想（第12章前菜）
• 预计时间：120 分钟
• 核心难度：
• 完成标志：能手写 BST 的增删查，用迭代和递归两种方式完成三种遍历，并理解中序遍历为何是有序序列

---

你在哪

森林里的路开始分叉了——每个路口都有两个方向（左和右），而且所有往左的路口都通向更小的数字，所有往右的都通向更大的。这不是巧合——这是二叉搜索树的落叶。

森林的第一道标志不是路牌——是一根树枝。

算法森林的规则跟你在村庄里学的东西完全不同：之前所有的数据结构都是"一条道走到黑"的——数组是一条直线，链表是一条带箭头标记的直线，栈和队列是这条直线上的"只进不出"和"先进先出"。

但树不一样。

"你看这片树林，"向导用登山杖指了指前面的山坡，"树根扎在地下，树干往上涨，到了某个高度就开始分叉——一支朝左，一支朝右。每一根分支到一定程度又继续分叉，直到最末端的树叶。"

他转过身来看着我："这就是你今天要学的数据结构——不止往一个方向走，而是两个方向同时延伸。"

---

你的任务

你要实现一个"二分查找树"（Binary Search Tree, BST）——它是计算机科学里最重要的非线性数据结构的入门钥匙。

本章分层

• 必读：二叉树节点定义（val/left/right）；BST 核心规则（左小右大）；BST 的查找和插入（递归版+迭代版）；四种遍历（前中后层）及其用途
• 选读：BST 删除操作（三种情况分类讨论）；迭代中序遍历（栈模型）
• 深水区：BST 退化为链表的原因及其对工程选型的影响

本章不会要求你掌握

• 手写全部四种遍历的两种版本（递归式学习即可，迭代版了解栈模型）
• 红黑树的着色规则
• B 树的设计细节

具体要求：

1. 理解树的术语：根、叶、深度、高度、子树
2. 掌握四种遍历顺序：前序、中序、后序、层序——能写出递归版本，了解迭代版用栈/队列
3. 实现 BST 的查找、插入，理解删除的三种情况思路
4. 理解 BST 的致命弱点——退化——以及它为什么无法被直接用在工业级代码里

这一章是后面所有"高级树"的基础。AVL、红黑树、B 树……所有它们的祖先，都是你现在要写的这棵二叉树。

---

遭遇战 → 获得技能

① 树的骨架：从节点到树

先别想整棵树长什么样——先问一个问题：树由什么构成？

从编程角度说，树由一个个节点（Node）构成。每个节点存三样东西：它的值、左孩子的指针、右孩子的指针。

这就是"二叉树"名字的来源——每个节点最多有两个孩子。不多不少，允许只有一个，允许为零，但不允许三个。

class TreeNode:
    """二叉树节点——三合一套餐：值 + 左孩子 + 右孩子"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

** Java 差异：**

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

Java 里的节点必须用 new 来创建——TreeNode node = new TreeNode(5);。Python 的 __init__ 就是构造器，但 Python 不需要显式地写类型声明。

** C++ 差异：**

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

C++ 最显著的区别是指针——TreeNode* 而不是对象的引用。nullptr 表示"没有孩子"（Python 用 None，Java 用 null）。而且 C++ 里用 struct 就够了——所有成员默认 public，不用写那么多 public 关键词。

好，有了节点，那树本身呢？

实际上在大多数实现里，你不需要一个"树"类——你只需要一个根节点，通过根节点就能访问整棵树。但为了组织代码方便，我们通常会把操作封装起来。

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def is_empty(self):
        return self.root is None

注意：这是一个空壳。真正的本领在后面。

② 树的词库：五分钟搞懂术语

在动手写代码之前，我们需要统一一套语言。算法森林里的树，有一套自己的术语系统，跟现实世界沾边但不完全一样。

        深度 0         50         ← 根节点 (Root)
                      /  \
        深度 1      30    70      ← 内部节点 (Internal Node)
                   / \   / \
        深度 2   20  40 60  80    ← 叶节点 (Leaf，没有孩子)

根（Root）： 整棵树的起点——只有一个。在树里"往深处走"必须经过根。没有根的树不叫树。

叶节点（Leaf）： 没有孩子的节点——就是树的末端。在二叉树上，如果一个节点的 left 和 right 都是 None，它就是叶。

内部节点（Internal Node）： 既不是根也不是叶——就是中间的那些节点。

深度（Depth）： 从根到某个节点的"路径长度"。根自己深度为 0（有些教材定义深度从 1 开始，但编程领域从 0 开始更常见——跟数组下标一致）。

高度（Height）： 从某个节点到最远叶节点的"路径长度"。叶节点的高度为 0。根的高度等于整棵树的高度。

子树（Subtree）： 任何一个节点连同它的所有后代，就是一个子树。BST 里所有的子树本身也是 BST。

好，有了这套词，我们可以开始写代码了。

③ BST 核心规则——"左小右大"

二叉搜索树的生命只有一条规则，但这一条规则能推导出所有行为：

对于任意节点：左子树的所有节点 ≤ 当前节点 < 右子树的所有节点

这就是 BST 里 Search 这个单词的来源——搜索靠的就是这个规则。

举个例子，你在下面这棵 BST 里找 40：

        50
       /  \
     30    70
    / \   / \
  20  40 60  80

从根开始：40 < 50 → 往左。40 > 30 → 往右。找到了。

每次都排除掉一半的树——这就是"二分搜索"名字的由来。

④ BST 查找——就是三行游戏

查找的逻辑极其简单：从根开始，比当前节点大就往右，比当前节点小就往左，直到找到或者遇到 None。

递归版本看起来就像在自言自语：

def search_recursive(node, target):
    """在 BST 中查找目标值——递归版本"""
    if node is None or node.val == target:
        return node
    if target < node.val:
        return search_recursive(node.left, target)
    else:
        return search_recursive(node.right, target)

让我们运行一下：

# 假设已经有上面那棵树，root 指向 50
result = search_recursive(root, 40)
print(result.val if result else "没找到")
# 输出：40

result = search_recursive(root, 99)
print(result.val if result else "没找到")
# 输出：没找到

迭代版本不用递归调用，只用循环，在面试里更常见：

def search_iterative(root, target):
    """在 BST 中查找目标值——迭代版本"""
    current = root
    while current is not None and current.val != target:
        if target < current.val:
            current = current.left
        else:
            current = current.right
    return current

两种方式的时间复杂度完全一样：平均 O(log n)，最坏 O(n)（退化的情况下——我们后面会说这个）。

空间复杂度不一样：递归版 O(log n) 的平均调用栈深度（最坏 O(n)），迭代版永远是 O(1)。

** Java 差异：** Java 没有 None，用 null。迭代写法用 while (current != null)。递归写法同上，Java 的方法签名是 TreeNode search(TreeNode node, int target)。另外 Java 里 return null 表示"没找到"。

** C++ 差异：** C++ 用指针，判空用 node == nullptr。迭代版本：

TreeNode* search(TreeNode* root, int target) {
    TreeNode* cur = root;
    while (cur && cur->val != target) {
        cur = (target < cur->val) ? cur->left : cur->right;
    }
    return cur;
}

三目运算符在 C++ 里用得很频繁——上面的代码一行实现了递归版的 if-else 逻辑。

⑤ BST 插入——找到该放的位置

插入跟查找几乎一样：先找到"应该放哪"，然后接上去。

唯一要注意的地方：找到正确的空位。

def insert(root, val):
    """在 BST 中插入一个新值——递归版本"""
    if root is None:
        return TreeNode(val)

    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    # 如果相等——很多实现里直接忽略重复值

    return root

运行一下看看效果：

root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)
# 现在 root 是一棵完整的有 7 个节点的 BST

注意这段代码的精妙之处：root.left = insert(root.left, val)——这一行既向下递归，又在返回时把结果"接"回来。如果你没有把 insert 函数的返回值赋给孩子，那子树的变化就白做了。

** Java 差异：** 在 Java 里，递归插入几乎一样，但要处理一个语言细节：Java 的方法参数是值传递（对于对象来说是引用值的副本），所以不能直接写成 root = insert(root, val) 并期望调用者的 root 变量被更新——你必须写 root = insert(root, val) 来接收返回值。这一点跟 Python 表面看起来不同，实际底层行为是一样的。

迭代版本也不难——只是需要父亲节点来"接线"：

def insert_iterative(root, val):
    """在 BST 中插入一个新值——迭代版本"""
    new_node = TreeNode(val)

    if root is None:
        return new_node

    current = root
    while True:
        if val < current.val:
            if current.left is None:
                current.left = new_node
                break
            current = current.left
        else:
            if current.right is None:
                current.right = new_node
                break
            current = current.right

    return root

⑥ BST 删除——最难的一步（后半部分/进阶）

删除是 BST 中最复杂的操作。 主线先掌握查找、插入和遍历即可。删除分三种情况，理解思路即可实现阶段回头看。

如果说 BST 的插入是走进森林放个路标，那删除就是……施工拆除。你得考虑三种情况，每种情况的处理方式完全不同。

情况 1：目标节点是叶节点——直接拔掉

这个最简单。没有孩子需要照顾——直接把父节点指向它的指针设成 None 就行。

    50                50
   /  \              /  \
  30   70    ==>    30   70
 / \   /          / \
20 40 60         20 40
        ↑
      删除 60

情况 2：目标节点只有一个孩子——让孩子顶上来

像高速公路上的并道——被删节点的孩子直接接到它的父节点。

        50                50
       /  \              /  \
     30    70    ==>   20    70
    /     /
  20    40
   ↑
删除 30（左子树顶上来）

情况 3：目标节点有两个孩子——找"中序后继"来替代

这一个稍微棘手。你不能简单地删掉——因为两只手都持有子树，你没法让两个孩子同时接上去。

解决方案：找一个替身来顶替被删节点的位置。

找谁？根据 BST 的性质，被删节点的"中序后继"（Inorder Successor）——也就是右子树里最小的那个节点——是唯一合适的替代者。为什么？因为它一定大于左子树所有节点，同时小于右子树中除自己外的所有节点。

def delete(root, val):
    """删除 BST 中的一个值——分类讨论三种情况"""
    if root is None:
        return None

    # 第一步：找到要删除的节点
    if val < root.val:
        root.left = delete(root.left, val)
    elif val > root.val:
        root.right = delete(root.right, val)
    else:
        # 找到了！开始分类讨论

        # 情况 1 & 2：0 或 1 个孩子——直接返回孩子即可
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left

        # 情况 3：两个孩子
        # 找到右子树的最小节点（中序后继）
        successor = _find_min(root.right)
        root.val = successor.val          # 替换值
        root.right = delete(root.right, successor.val)  # 删除那个替身节点

    return root


def _find_min(node):
    """找到以 node 为根的子树中的最小值"""
    current = node
    while current.left is not None:
        current = current.left
    return current

运行测试：

root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)

# 删除叶节点 20
root = delete(root, 20)
# 删除只有一个孩子的节点 30
root = delete(root, 30)
# 删除有两个孩子的节点 50
root = delete(root, 50)

这段代码有另一个精妙的地方：delete 函数的"找→删→接"三步在递归过程中一次性完成了。当你走到 val == root.val 那一步时，根据三种情况决定"返回什么"——这个返回值通过递归一层一层接回去，最终更新整棵树的结构。

** Java 差异：** Java 版跟 Python 版结构一致。唯一容易踩的坑：Java 没有 Python 的元组赋值，所以不能在一行里交换节点——你需要临时变量保存 successor：

TreeNode successor = findMin(root.right);
root.val = successor.val;
root.right = delete(root.right, successor.val);

⑦ 树的遍历——四种方式

遍历就是把树里的所有节点"走一遍"。不同的顺序服务于不同的需求。

前序遍历（Preorder）：根 → 左 → 右

用途：复制整棵树（先复制根，再递归复制左右子树）。

def preorder(node, result=None):
    """前序遍历：根 -> 左 -> 右"""
    if result is None:
        result = []
    if node is None:
        return result
    result.append(node.val)      # 先访问根
    preorder(node.left, result)
    preorder(node.right, result)
    return result

# 输出：[50, 30, 20, 40, 70, 60, 80]

中序遍历（Inorder）：左 → 根 → 右

用途：BST 中最重要的遍历——得到有序序列。

def inorder(node, result=None):
    """中序遍历：左 -> 根 -> 右"""
    if result is None:
        result = []
    if node is None:
        return result
    inorder(node.left, result)
    result.append(node.val)      # 中间访问根
    inorder(node.right, result)
    return result

# 输出：[20, 30, 40, 50, 60, 70, 80]
# 注意：这是升序排列！

一句话记住： BST 的中序遍历 = 升序序列。这个等价关系是所有"用 BST 做排序"的基础。

后序遍历（Postorder）：左 → 右 → 根

用途：删除整棵树（先删孩子，再删自己）。也是许多"从底向上"计算问题的关键。

def postorder(node, result=None):
    """后序遍历：左 -> 右 -> 根"""
    if result is None:
        result = []
    if node is None:
        return result
    postorder(node.left, result)
    postorder(node.right, result)
    result.append(node.val)      # 最后访问根
    return result

# 输出：[20, 40, 30, 60, 80, 70, 50]

层序遍历（Level Order / BFS）：一层一层走

用途：查找最短路径、树的"广度优先"探索。

层序遍历不能用简单的递归实现——它需要借助一个队列（Queue）来暂时存放"待处理的节点"。

from collections import deque

def level_order(root):
    """层序遍历：用队列逐层处理"""
    if root is None:
        return []

    result = []
    queue = deque([root])

    while queue:
        node = queue.popleft()
        result.append(node.val)

        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

    return result

# 输出：[50, 30, 70, 20, 40, 60, 80]
# 一层一层从左到右输出

四序遍历的递归写法，核心差异只有一行代码的位置：

• result.append(root.val) 放在前 → 前序
• 放在左递归和右递归之间 → 中序
• 放在两个递归之后 → 后序
• 不用递归，用队列 → 层序

** Java 差异：** Java 实现层序遍历用 Queue<TreeNode> queue = new LinkedList<>();。LinkedList 实现了 Queue 接口。用 queue.offer(root) 入队、queue.poll() 出队。

** C++ 差异：** C++ 用 std::queue<TreeNode*> q;。入队用 q.push(root)，出队用 q.pop()（注意 pop 不返回指向的元素，你需要先 q.front() 拿到值，再 q.pop() 弹出）。

递归 vs 迭代遍历——了解栈模型即可

迭代遍历是进阶内容。 主线只需要会用递归遍历，了解迭代遍历的核心思路——用栈/队列模拟。不要求手写全部版本。

上面的递归代码非常简洁，但面试官经常问："你能不用递归实现中序遍历吗？"

为什么？因为递归虽然好写，但有栈溢出风险——如果树有 100 万层，递归调用栈就堆了 100 万层。现实中这种情况很少见（退化的链状树才会这么深），但既然被问了，你得会。

迭代中序遍历核心思路：手动模拟递归栈。

def inorder_iterative(root):
    """非递归中序遍历——手动维护栈"""
    result = []
    stack = []
    current = root

    while current or stack:
        # 一路往左走到黑
        while current:
            stack.append(current)
            current = current.left

        # 弹出栈顶——这就是当前要访问的节点
        current = stack.pop()
        result.append(current.val)

        # 切换到右子树继续
        current = current.right

    return result

这个模式叫"教科书级别的栈模拟递归"——几乎所有二叉树迭代遍历的题目都能用这个框架改出来。前序和后序的迭代版稍微调整一下入栈顺序就行。

---

常见陷阱

场景 1：忘记把递归结果接回去

def insert_buggy(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        insert_buggy(root.left, val)   # ← 没把结果赋给 root.left！
    ...

这里 insert_buggy(root.left, val) 确实把新节点插进去了，但这个新节点没跟父节点连上——因为返回的 TreeNode(val) 丢失了。你的代码不会报错，但 BST 里就是没有这个节点。

场景 2：遍历到的值乱序了

假设你这么写"中序"遍历：

def fake_inorder(node, result):
    if node is None:
        return
    result.append(node.val)      # ← 这是前序！
    fake_inorder(node.left, result)
    fake_inorder(node.right, result)

人最容易犯的错误也是三行递归里搞混了顺序。上面这段实际上是前序遍历——你把它叫做"中序"，但结果不是升序的。

场景 3：BST 退化成了链表

这是 BST 最大的"暗坑"。

你在 BST 中依次插入 [1, 2, 3, 4, 5]——每次都插在右子树——你得到的树是这样的：

1
 \
  2
   \
    3
     \
      4
       \
        5

这哪还是树？这是一条链表！查找要 O(n) 而不是 O(log n)。

问题出在哪里？BST 本身不要求"平衡"——它只要求"左小右大"。如果数据是有序的，插入就变成了"永远往右"，BST 就退化成了链表。

这个坑是第6章所有平衡树的起点——它们就是为了解决这个问题而生的。

---

通关挑战

🗡 热身（15 分钟必做）

1. 用 Python 实现 BinarySearchTree 类，包含 insert、search、delete 方法
2. 插入序列 [5, 3, 7, 2, 4, 6, 8]，分别用四种遍历方式打印结果
3. 删除 5（根节点），确认删除后的中序结果仍然是 [2, 3, 4, 6, 7, 8]
4. 用迭代方式实现上述四种遍历中的两种

** 挑战（45 分钟选做）**

1. 验证 BST： 写一个函数 is_valid_bst(root)，判断一棵二叉树是不是合法的 BST。注意：仅检查左<根<右是不够的——你还需要保证左子树的所有节点都小于根，右子树所有节点都大于根。做法：传一个上下界范围。
2. 最近公共祖先： 在 BST 中找到两个节点的最近公共祖先（LCA）。利用 BST 性质能做到 O(log n) 和 O(1)。
3. 第 K 小元素： 利用中序遍历在 O(n) 时间内找到 BST 中第 K 小的元素。
4. 序列化反序列化： 实现 serialize（树→字符串）和 deserialize（字符串→树）。前序遍历配合空标记就行。

** 排障（写在挑战旁边）**

问题	最常见原因
插入了元素但树里没有	递归插入忘把结果赋给 root.left/right
删除后树结构错乱	情况3（两个孩子）的替身选择或删除逻辑不对
中序遍历结果不是升序	BST 插入时大小写/方向判断反了
递归过深报 RecursionError	树太深（BST 退化成了链表）——Python 默认递归深度约 1000

---

验收标准

• [ ] 能口述 BST 的核心规则：左小右大，以及为什么中序就是升序
• [ ] 能手写 BST 插入，区分递归版和迭代版的差异
• [ ] 能手写 BST 删除，说清楚三种情况的处理方式
• [ ] 能写出四种遍历（前中后层），并能指出它们的典型用途
• [ ] 能写出迭代中序遍历（栈实现）
• [ ] 能说出 BST 的一个致命弱点——退化——以及会导致什么后果
• [ ] 已完成热身环节的 4 道题目

---

常见卡点

1. 树的高度 vs 深度——晕了吧？

深度是从根往某节点数，高度是从某节点往最远叶节点数。一个从上往下，一个从下往上。大多数时候你不需要区分它们——但如果你在一个需要"平衡因子"的数据结构里搞混了，结果就是整棵树出问题。

简单记忆：根深度为 0，叶高度为 0。

2. 递归写起来很顺，但一画图就乱了

递归处理二叉树有一种"信不信由你"的美感。新手常常看着第三行的递归调用，脑子就开始打结。正确的做法：别跟踪递归。只关注当前节点做什么，剩下的相信递归函数会帮你做好。前序遍历：我当前节点先被访问 → 然后左子树整个按前序遍历 → 然后右子树整个按前序遍历。你可以把 preorder(root.left) 理解成"帮我按前序处理好整棵左子树"。

换人话：递归函数是一个对你承诺——"你给我一棵树，我帮你按这个顺序处理完"。

3. 删除操作——情况 3 最难，最容易出错

两个孩子的删除，最容易出的错是：找完替身之后，递归删除替身的时候没有排除替身自身。看上面代码的最后三行：先把替身的值拷过来，然后把原来的替身节点从右子树中删掉。顺序不能搞反，也不能直接删 root——因为你正在 root 上。

---

现在不需要理解

• 红黑树的着色规则 — 那是 BST 的"救火队员"，第6章会深入讲
• 如何把 BST 持久化到磁盘 — 涉及序列化和文件系统课程
• B 树为什么叶子节点可以存多个值 — 第6章会简单提及
• 伸展树（Splay Tree）的自适应性 — 高级话题，不在本卷范围内

---

旅人笔记

二叉树大概是计算机科学里最"优雅"的数据结构之一。

说它优雅，不是因为它能多高效地查找数据——实际上 BST 在最坏情况下链化成链表，效率还不如直接上哈希表。真正让二叉树伟大的，是它的遍历能力。

数组是平的。链表是直的。哈希表是无序的。但树——你可以在它上面按任意顺序行走。前序让你先看清根再往下探；中序让你得到全有序序列；后序让你从叶子往上构建；层序让你逐层平推。

这种"能给数据排序的灵活性"是其他线性结构求之不得的。

另一件有意思的事情：我们写的那几行递归代码，背后有三个计算机科学的基石概念同时发挥作用——递归（函数调用自身）、分治（把大问题拆成两个子问题）、栈（函数调用栈自动管理上下文）。BST 的递归遍历之所以看起来"毫不费力"，是因为这三样东西在你写的瞬间就配合好了。

最后，记住一个事实：你在这里学到的 BST 节点结构——val, left, right——是所有你以后会遇到的更复杂的树（红黑树、AVL、B树、线段树、Trie……）的最基本模板。学会了它，你已经拿到了算法森林里一把万能的钥匙。

---

→ 下一站预告

BST 有一个天生的缺陷——数据有序插入时退化成链表，查找效率从 O(log n) 直降到 O(n)。这不是 BST 本身的问题，而是它没有"自我修复"机制。

下一章，我们会给树加上"自平衡"的能力。你会看到 AVL 树在插入后如何通过旋转恢复平衡，红黑树又为什么用 5 条简单的规则就管住了整棵树的结构。这些"平衡树"才是 Java 的 TreeMap 和 TreeSet 背后真正用的数据结构。

第6章：平衡树与红黑树。