06. 树、二叉树与搜索树

0. 本章先解决什么问题

数组和链表表达的是线性关系:

a -> b -> c -> d

但很多数据天然是层级关系:

目录和文件
组织结构
表达式
语法结构
分类体系
索引
决策过程

树用来表达层级。

本章要解决:

• 树的基本概念是什么?
• 二叉树为什么重要?
• 前序、中序、后序、层序遍历分别在干什么?
• 二叉搜索树如何支持查找和有序遍历?
• 搜索树为什么可能退化?
• 树在实际系统里解决什么问题?

这张图怎么读

这张图把搜索树的关键风险画出来:BST 的查找成本不是固定 O(log n),而是 O(height)。如果插入顺序让树退化成链,查找会从对数级变成线性级。

1. 树的最小模型

树由节点和边组成。

A
/
B C
/ \
D E F

常见术语:

树的核心特点:

一个节点可以有多个子节点
但除了根节点,每个节点通常只有一个父节点

2. 二叉树

二叉树规定每个节点最多两个孩子:

left
right

节点结构:

value
left
right

二叉树重要,因为它足够简单,又能表达很多递归结构。

典型应用:

• 表达式树。
• 搜索树。
• 堆。
• 决策树。
• 语法树。

3. 树天然适合递归

树的定义本身就是递归的:

一棵树 = 根节点 + 若干子树

处理树常见模式:

处理当前节点
递归处理左子树
递归处理右子树

或者:

先处理子树
再汇总到当前节点

递归写法清晰,但深度太大时可能栈溢出。也可以用显式栈或队列改成迭代。

4. 深度优先遍历

二叉树常见三种深度优先遍历。

前序:

根 -> 左 -> 右

中序:

左 -> 根 -> 右

后序:

左 -> 右 -> 根

它们适合不同场景:

5. 层序遍历

层序遍历按层访问:

A
B C
D E F

通常用队列实现:

root 入队
while 队列不空:
取出队头
访问节点
子节点入队

层序遍历适合:

• 找最短层数。
• 按层输出。
• 广度优先搜索。
• 计算树宽度。
• 序列化完全二叉树。

6. 二叉搜索树

二叉搜索树规定:

左子树所有值 < 当前节点
右子树所有值 > 当前节点

示意:

8
/
3 10
/ \
1 6 14

查找 6:

6 < 8 -> 去左
6 > 3 -> 去右
找到 6

如果树高度是 h,查找成本是 O(h)。

7. 搜索树为什么能有序遍历

二叉搜索树中序遍历:

左 -> 根 -> 右

会得到升序结果。

原因:

左子树都比根小
右子树都比根大

所以搜索树不仅能查找,还能支持:

• 有序输出。
• 找最小/最大。
• 找前驱/后继。
• 范围查询。

这是哈希表不擅长的能力。

8. 插入和删除

插入:

从根开始比较
小就往左,大就往右
走到空位置插入

删除更复杂:

删除的关键是:

删除后仍然满足搜索树不变量。

机制深挖:搜索树排错先查不变量

BST 出 bug 时,不要只看某个节点值是否存在,要检查整棵树的不变量:

对任意节点:
左子树所有值 < 当前节点
右子树所有值 > 当前节点

常见错误:

正确检查方式要带上下界:

check(node, low, high):
node.value 必须在 (low, high) 内
check(node.left, low, node.value)
check(node.right, node.value, high)

这比只看“左孩子小、右孩子大”更严格,因为右子树深处的每个节点都必须大于当前根,而不只是大于它自己的父节点。

9. 搜索树退化

如果按升序插入:

1, 2, 3, 4, 5

普通搜索树可能变成:

1

2

3

4

高度变成 n,查找退化成 O(n)。

搜索树性能依赖高度:

高度越低,查找路径越短。

这就是平衡树存在的原因。

10. 完全二叉树和满二叉树

满二叉树:

每个非叶子节点都有两个孩子
所有叶子在同一层

完全二叉树:

除了最后一层,前面都填满
最后一层从左到右填

完全二叉树很适合用数组存储。

堆就是基于完全二叉树的结构。

数组下标关系:

parent(i) = (i - 1) / 2
left(i) = 2 * i + 1
right(i) = 2 * i + 2

11. 联系实际:树用于表达层级和索引

树适合:

• 文件目录。
• HTML/文档结构。
• 语法分析树。
• 表达式计算。
• 分类和组织结构。
• 有序索引。
• 路由和决策。

如果你面对的数据有明显“父子层级”,树通常是第一候选。

如果你面对的是“按 key 查找且需要顺序能力”,搜索树就是重要候选。

小实验:插入顺序如何改变树高

用同一组值:

1, 2, 3, 4, 5, 6, 7

比较两种插入顺序:

同样的数据,不同插入顺序会造成完全不同的树高。

所以实际使用搜索树时,要问:

输入是否接近有序?
是否需要平衡策略?
是否需要范围查询和有序遍历?
如果只要精确查找,哈希表是否更合适?

这就是从“会写 BST”走向“会选结构”的关键。

手推:BST 删除为什么比插入更容易错

BST 插入通常只要一路比较,找到空位接上。删除复杂得多,因为删除后还要保持搜索树不变量:

左子树所有值 < 当前节点 < 右子树所有值

删除分三种情况:

最容易错的是第三种。假设删除节点 5:

5
/
3 8
/
6

可以用右子树最小值 6 替换 5:

6
/
3 8

为什么选右子树最小值?因为它满足:

比左子树所有节点大;
比右子树其他节点小或相等于边界规则。

删除 bug 常见在:

所以 BST 排错不要只看被删除节点附近,还要检查整棵树的上下界约束。

边界条件:局部左右关系正确,不代表整棵树是 BST

一个常见误判是只检查:

node.left < node
node.right > node

但这不够。看这个树:

10
/
5 15
/
6

节点 15 的左孩子 6 确实小于 15,局部关系正确。但 6 在 10 的右子树里,必须大于 10,所以整棵树不是 BST。

正确检查要带上下界:

检查节点 x 时:
它必须在 (lower, upper) 范围内
左子树范围变成 (lower, x)
右子树范围变成 (x, upper)

这条规则能解释为什么树结构 bug 不容易靠肉眼局部看出来。BST 的不变量是“全局范围约束”,不是只看父子大小。

12. 学完本章你能解决什么问题

学完这一章,你应该能解决或开始分析这些问题:

1. 树和线性结构有什么区别?
2. 二叉树节点结构是什么?
3. 前序、中序、后序、层序遍历分别适合什么?
4. 为什么二叉搜索树能支持有序查找?
5. 为什么搜索树查找成本取决于高度?
6. 普通搜索树为什么可能退化成链表?
7. 完全二叉树为什么适合数组存储?
8. 实际系统中什么时候用树表达层级或索引?

树的核心是层级和递归。搜索树的核心是用结构维护有序关系。

延伸阅读

• TreeMap
• from - zero · data-structures