📖 引入故事：字典里的“二分查找”
你查字典时，不会从第 1 页翻到最后一页——而是先翻到中间，看是大了还是小了，再决定往前还是往后翻。这种“每次砍掉一半”的做法让查找飞快。问题来了：能不能把一堆数字排成一棵树，让“往左一定更小、往右一定更大”，从而一插一查都自动有序？
这正是二叉搜索树（Binary Search Tree，BST）的思想：它的每个结点都满足“左子树全比它小、右子树全比它大”，所以中序遍历一遍就是排好序的序列。
掌握二叉搜索树“左<根<右”的定义、插入/查找/删除三大操作，以及“中序遍历必升序”这条核心性质。
从“怎样把一堆数存起来、查起来又快又能自动有序”出发，理解二叉搜索树为什么是既能插入又能排序的神奇结构。
你查字典时，不会从第 1 页翻到最后一页——而是先翻到中间，看是大了还是小了，再决定往前还是往后翻。这种“每次砍掉一半”的做法让查找飞快。问题来了：能不能把一堆数字排成一棵树，让“往左一定更小、往右一定更大”，从而一插一查都自动有序？
这正是二叉搜索树（Binary Search Tree，BST）的思想：它的每个结点都满足“左子树全比它小、右子树全比它大”，所以中序遍历一遍就是排好序的序列。
想象一群人排队领号：新来一个人先和队首比，比队首小就站到队首左边那一队、比队首大就站右边那一队；每队内部又各自继续比。最后从最左一直走到最右，人就是按身高从小到大排好的。二叉搜索树就是把这种“比大小分流”固定成一棵树，任何时刻中序遍历都升序。
关键约束：左 < 根 < 右（严格不等，一般不存重复值）。一旦破坏，就不再是 BST。
二叉搜索树（BST）：一棵二叉树，满足对任意结点，其左子树所有结点的值 < 该结点的值 < 右子树所有结点的值。
直接推论：对 BST 做中序遍历（左—根—右），得到的序列一定严格递增。这是 BST 最重要的性质，也是验证“它还是不是 BST”的利器。
基本操作：插入（insert）、查找（find）、求最值、删除（erase）。平均时间复杂度 O(log n)（理想平衡时），最坏 O(n)（退化成链）。
“左小右大是铁律，中序遍历必有序；插入就比大小分流，查找顺着大小走；删点三种情况记，平衡与否定快慢。”
| 知识点 | 你要掌握 | 难度 |
|---|---|---|
| 定义与性质 | 左 < 根 < 右；中序必升序 | ★ |
| 插入（构建） | 从根比大小，落到空位 | ★★ |
| 查找与最值 | 顺着大小走；最左最小、最右最大 | ★★ |
| 删除（三种情况） | 无子/一子/两子（后继替身） | ★★★ |
| 中序验证 | 中序升序 ⇔ 仍是 BST | ★★ |
| 拓展 | 平衡树（AVL/红黑树）避免退化 | ★★★ |
先确认“中序有序”这条性质，再看插入怎样“比大小分流”、查找怎样顺大小走、删除怎样分三种情况处理。
因为对每个结点都满足“左 < 根 < 右”，中序遍历（左—根—右）自然把“比根小的全放在前面、比根大的全放在后面”，整条序列必然严格递增。
反过来，只要一棵树中序遍历是升序的，它就是 BST。所以“中序遍历 + 检查是否递增”是判断 BST 的标准方法。
插入 v：从根开始，v 比当前结点小就往左走、大就往右走；走到空指针时，就把 v 作为新结点挂上去。因为每次都“按大小分流”，建好的树自动满足左 < 根 < 右。
上图就是把 5 3 7 1 4 6 8 2 9 依次插入得到的 BST。注意：相同输入顺序固定，树形就固定；顺序不同，树形不同。
查找 v：从根出发，等于就找到；比当前小往左、比当前大往右；走到空还没找到就是不存在。最小值在最左下的叶子、最大值在最右下的叶子。
#include <iostream>
using namespace std;
struct Node { int val; Node *l, *r; Node(int v) : val(v), l(nullptr), r(nullptr) {} };
Node* insert(Node* u, int v) {
if (!u) return new Node(v);
if (v < u->val) u->l = insert(u->l, v);
else if (v > u->val) u->r = insert(u->r, v);
return u;
}
Node* find(Node* u, int v) {
while (u) { if (v == u->val) return u; u = (v < u->val) ? u->l : u->r; }
return nullptr;
}
int main() {
int a[] = {5, 3, 7, 1, 4, 6, 8, 2, 9};
Node* root = nullptr;
for (int v : a) root = insert(root, v);
for (int q : {4, 10}) {
Node* p = find(root, q);
cout << "查找 " << q << "：" << (p ? "找到" : "未找到") << endl;
}
Node* mn = root; while (mn->l) mn = mn->l;
Node* mx = root; while (mx->r) mx = mx->r;
cout << "最小值 = " << mn->val << " 最大值 = " << mx->val << endl;
return 0;
}查找 4：找到
查找 10：未找到
最小值 = 1 最大值 = 9查找本质就是“在树上做二分”，每次排除一半子树，理想情况下很快。
删除值 v 的结点，分三种情况：
#include <iostream>
using namespace std;
struct Node { int val; Node *l, *r; Node(int v) : val(v), l(nullptr), r(nullptr) {} };
Node* insert(Node* u, int v) {
if (!u) return new Node(v);
if (v < u->val) u->l = insert(u->l, v);
else if (v > u->val) u->r = insert(u->r, v);
return u;
}
void inorder(Node* u) { if (!u) return; inorder(u->l); cout << u->val << " "; inorder(u->r); }
Node* minNode(Node* u) { while (u->l) u = u->l; return u; }
Node* erase(Node* u, int v) {
if (!u) return nullptr;
if (v < u->val) u->l = erase(u->l, v);
else if (v > u->val) u->r = erase(u->r, v);
else { // 找到要删的结点
if (!u->l) { Node* t = u->r; delete u; return t; } // 无左孩子
if (!u->r) { Node* t = u->l; delete u; return t; } // 无右孩子
Node* s = minNode(u->r); // 有两孩子：用右子树最小者（中序后继）替身
u->val = s->val;
u->r = erase(u->r, s->val);
}
return u;
}
int main() {
int a[] = {5, 3, 7, 1, 4, 6, 8, 2, 9};
Node* root = nullptr;
for (int v : a) root = insert(root, v);
cout << "删除前中序："; inorder(root); cout << endl;
root = erase(root, 3); // 删除有两个孩子的结点 3
cout << "删除 3 后中序："; inorder(root); cout << endl;
root = erase(root, 5); // 删除根 5
cout << "删除 5 后中序："; inorder(root); cout << endl;
return 0;
}删除前中序：1 2 3 4 5 6 7 8 9
删除 3 后中序：1 2 4 5 6 7 8 9
删除 5 后中序：1 2 4 6 7 8 9删除 3（两孩子）时用右子树最小者 4 替身；删除根 5 时同理。删除后中序仍然有序，证明还是 BST。
每次插入或删除后，只要中序遍历得到升序序列，就说明结构仍然满足左 < 根 < 右。下面把构建出的树中序打印出来，肉眼可见它有序。
#include <iostream>
using namespace std;
struct Node { int val; Node *l, *r; Node(int v) : val(v), l(nullptr), r(nullptr) {} };
Node* insert(Node* u, int v) {
if (!u) return new Node(v);
if (v < u->val) u->l = insert(u->l, v);
else if (v > u->val) u->r = insert(u->r, v); // 相等一般不插入（去重）
return u;
}
void inorder(Node* u) { if (!u) return; inorder(u->l); cout << u->val << " "; inorder(u->r); }
int main() {
int a[] = {5, 3, 7, 1, 4, 6, 8, 2, 9};
Node* root = nullptr;
for (int v : a) root = insert(root, v);
cout << "插入序列：5 3 7 1 4 6 8 2 9" << endl;
cout << "中序遍历（应升序）：";
inorder(root);
cout << endl;
return 0;
}插入序列：5 3 7 1 4 6 8 2 9
中序遍历（应升序）：1 2 3 4 5 6 7 8 9 输出 1 2 3 4 5 6 7 8 9 严格升序——这正是 BST 性质成立的铁证。
三道分析编程题：换一组数构建并验证有序、查找最值、删除结点。均给出可编译运行的参考实现。
直接套用“从根比大小、落到空位”的插入逻辑，最后中序打印。
#include <iostream>
using namespace std;
struct Node { int val; Node *l, *r; Node(int v) : val(v), l(nullptr), r(nullptr) {} };
Node* insert(Node* u, int v) {
if (!u) return new Node(v);
if (v < u->val) u->l = insert(u->l, v);
else if (v > u->val) u->r = insert(u->r, v);
return u;
}
void inorder(Node* u) { if (!u) return; inorder(u->l); cout << u->val << " "; inorder(u->r); }
int main() {
int a[] = {9, 4, 15, 2, 7, 12, 20, 1, 3, 6, 8};
Node* root = nullptr;
for (int v : a) root = insert(root, v);
cout << "插入序列：9 4 15 2 7 12 20 1 3 6 8" << endl;
cout << "中序遍历（应升序）：";
inorder(root);
cout << endl;
return 0;
}插入序列：9 4 15 2 7 12 20 1 3 6 8
中序遍历（应升序）：1 2 3 4 6 7 8 9 12 15 20中序得到 1 2 3 4 6 7 8 9 12 15 20，升序成立。
复用查找函数与“最左最小、最右最大”的结论。
#include <iostream>
using namespace std;
struct Node { int val; Node *l, *r; Node(int v) : val(v), l(nullptr), r(nullptr) {} };
Node* insert(Node* u, int v) {
if (!u) return new Node(v);
if (v < u->val) u->l = insert(u->l, v);
else if (v > u->val) u->r = insert(u->r, v);
return u;
}
Node* find(Node* u, int v) { while (u) { if (v == u->val) return u; u = (v < u->val) ? u->l : u->r; } return nullptr; }
int main() {
int a[] = {9, 4, 15, 2, 7, 12, 20, 1, 3, 6, 8};
Node* root = nullptr;
for (int v : a) root = insert(root, v);
for (int q : {7, 5}) {
Node* p = find(root, q);
cout << "查找 " << q << "：" << (p ? "找到" : "未找到") << endl;
}
Node* mn = root; while (mn->l) mn = mn->l;
Node* mx = root; while (mx->r) mx = mx->r;
cout << "最小值 = " << mn->val << " 最大值 = " << mx->val << endl;
return 0;
}查找 7：找到
查找 5：未找到
最小值 = 1 最大值 = 207 存在、5 不存在；最小值 1、最大值 20。
4 有两孩子，用右子树最小者 6 替身，再中序验证。
#include <iostream>
using namespace std;
struct Node { int val; Node *l, *r; Node(int v) : val(v), l(nullptr), r(nullptr) {} };
Node* insert(Node* u, int v) {
if (!u) return new Node(v);
if (v < u->val) u->l = insert(u->l, v);
else if (v > u->val) u->r = insert(u->r, v);
return u;
}
void inorder(Node* u) { if (!u) return; inorder(u->l); cout << u->val << " "; inorder(u->r); }
Node* minNode(Node* u) { while (u->l) u = u->l; return u; }
Node* erase(Node* u, int v) {
if (!u) return nullptr;
if (v < u->val) u->l = erase(u->l, v);
else if (v > u->val) u->r = erase(u->r, v);
else {
if (!u->l) { Node* t = u->r; delete u; return t; }
if (!u->r) { Node* t = u->l; delete u; return t; }
Node* s = minNode(u->r); u->val = s->val; u->r = erase(u->r, s->val);
}
return u;
}
int main() {
int a[] = {9, 4, 15, 2, 7, 12, 20, 1, 3, 6, 8};
Node* root = nullptr;
for (int v : a) root = insert(root, v);
cout << "删除前中序："; inorder(root); cout << endl;
root = erase(root, 4); // 删除有两个孩子的结点 4
cout << "删除 4 后中序："; inorder(root); cout << endl;
return 0;
}删除前中序：1 2 3 4 6 7 8 9 12 15 20
删除 4 后中序：1 2 3 6 7 8 9 12 15 20删除 4 后中序为 1 2 3 6 7 8 9 12 15 20，依然升序，删除正确。
把定义、性质、三种操作与“退化风险”一次性理清。
| 结论 | 说明 |
|---|---|
| 定义 | 左 < 根 < 右（任意结点） |
| 性质 | 中序遍历必升序 |
| 插入 | 从根比大小，落到空位 |
| 查找 | 顺着大小走；最左最小、最右最大 |
| 删除 | 无子/一子直接替；两子用后继替身 |
| 复杂度 | 平均 O(log n)，退化链 O(n) |
⚠️ BST 的“定义、插入、查找、删除”属 CSP-J 应知；平衡树的旋转属提高，初赛可能考概念、复赛一般不要求手写。
5 大易错点 + 速查表 + 笔记卡，考前一眼回顾。
把定义记成“左 ≤ 根 ≤ 右”。BST 一般要求严格不等（左 < 根 < 右），重复值通常不入树。
插入时“比大小”写反，把小的往右放。必须小往左、大往右，否则中序不再有序。
删除“两孩子”结点时直接删掉，导致子树丢失。正确做法：用中序后继（右子树最小）替身。
求最小值时写成“根就是最小”。最小在最左下的叶子，要一直往左走到底。
以为 BST 查找永远 O(log n)。退化成链时是 O(n)，只有平衡树才能保证 O(log n)。
| 概念 | 要点 |
|---|---|
| 定义 | 左 < 根 < 右 |
| 性质 | 中序遍历必升序 |
| 插入 | 比大小，落到空位 |
| 查找 | 顺大小走；最左最小、最右最大 |
| 删除 | 两子→后继替身 |
| 复杂度 | 平均 O(log n)，退化 O(n) |
二叉搜索树 BST
① 定义：左 < 根 < 右（严格）。
② 性质：中序遍历必升序。
③ 插入：从根比大小，空位挂新点。
④ 查找：顺大小走；最左最小、最右最大。
⑤ 删除：两孩子用中序后继替身。
⑥ 退化成链时查找退化为 O(n)。
A基础 / B提高 / C挑战，难度递增，点击展开答案与解析。
强调有序约束。
BST 是“左子树所有值 < 根 < 右子树所有值”的二叉树；普通二叉树没有这个值的大小关系约束。
思路：BST 的约束是“左子树所有值 < 根 < 右子树所有值”，并且对每个结点都递归成立；普通二叉树只有“至多两个孩子”的结构约束，没有值的大小关系。
易错：只要求“左孩子 < 根 < 右孩子”，忽略了整棵子树的约束——这正是判断 BST 的经典陷阱。
从“左<根<右”推导。
因为左<根<右，中序（左—根—右）自然把小的放前大的放后，故升序。反过来也成立：中序升序 ⇒ 任意结点左<根<右 ⇒ 是 BST。
思路：中序的访问顺序是左—根—右，配合“左 < 根 < 右”，自然把小的排在前面、大的排在后面；反过来若中序升序，则任意结点都满足左 < 根 < 右，也是 BST。
易错：认为“中序升序”只是 BST 的必要条件，忽略它同时也是充分条件。
最小在左端。
最小值：从根一直往左走到叶子。最大值：从根一直往右走到叶子。
思路：由“左子树的值都更小”，最小值一定在最左端；由“右子树的值都更大”，最大值一定在最右端，一路走到叶子即得。
易错：把 min 与 max 的方向弄反，找最小值时往右走。
逐个比大小分流。
根 4；左 2（其左 1、右 3），右 6（其左 5、右 7）。中序：1 2 3 4 5 6 7。
思路：每个数都从根出发比较大小：比当前结点小就往左、大就往右，走到空位就放进去；插入顺序决定树形，而中序必为 1 2 3 4 5 6 7。
易错：画树时把 1、3 挂错位置（例如直接挂到 4 左子树下但顺序颠倒），中序就无法得到升序。
构建后中序。
中序：1 3 4 6 7 8 10 14，严格升序，符合 BST 性质。
思路：按 8 3 10 1 6 14 4 7 的顺序，每个数从根开始逐层比较大小、落到空位；插完后做一次中序遍历应得严格升序，可用来检验树建得对不对。
易错：插入 4、7 时误挂到 3 或 8 下面（正确是分别成为 6 的左、右孩子），中序就不再升序。
用右子树最小者替身。
3 的右子树最小者是 4，替身后中序：1 4 6 7 8 10 14，仍升序。
思路：删除有两个孩子的结点，取它的中序后继（右子树中的最小值）的值覆盖到该结点上，再递归删除那个后继结点，整棵树的中序仍保持升序。
易错：随便挑一个孩子顶上来（如直接用左孩子替换），会破坏左 < 根 < 右的性质。
中序升序里没有 5。
5 不在中序序列里，故该 BST 不含 5（中序恰为所有结点的值）。
思路：BST 的中序序列恰好就是所有结点值的升序排列，所以只要检查 5 是否出现在该序列中即可判定。
易错：试图先把中序序列还原成树形再查找，其实完全没必要。
后继 = 右子树最小。
找到要删结点 u（两孩子）；s = 右子树最左结点（中序后继）；u->val = s->val；递归删除 s（s 至多一个右孩子，退化为无子/一子情况）。
思路：定位到要删的结点 u（有两个孩子）后，在它的右子树里一路向左找到最小结点 s（中序后继），用 s 的值覆盖 u，再递归删除 s——s 至多带一个孩子，退化成了简单情形。
易错：用后继的值覆盖后，忘记把后继原位置的结点真正删掉，树里会出现两个相同的值。
局部检查不够。
不够。反例：根 10，左孩子 5（其右孩子 15），右孩子 20。每个结点自身左右孩子都满足，但 15 在 10 左子树却 > 10，不是 BST。必须保证“整棵左子树都小于根”。
思路：不够。反例：根为 10，左孩子 5 且 5 的右孩子为 15，右孩子为 20——每对直接父子都满足大小关系，但 15 位于 10 的左子树里却比 10 大，不是 BST。必须约束整棵子树的取值范围。
易错：只递归检查“当前结点与其左右孩子”，漏掉了来自祖先的跨层约束。
数学归纳/递归。
对任意结点，左子树全<它<右子树全；中序先排左子树（升序且都<根），再根，再右子树（升序且都>根），故整体升序。重复值则非严格。
思路：对任意结点，中序先完整遍历左子树（其中所有值都小于根），再访问根，再遍历右子树（都大于根）；左右两部分各自递归升序，拼起来整棵升序。
易错：只说明根与直接孩子的大小关系，没有用到“整棵左子树都小于根”这一递归前提。
复用本讲插入+中序。
定义 Node 结构；insert 递归比大小落空位；inorder 递归左—根—右打印；main 读入 n 个数依次 insert 后 inorder。
思路：定义含 val、left、right 的结点结构；insert 按大小关系递归落到空位；inorder 按左—根—右递归打印；main 读入 n 个数依次 insert 后输出中序即验证升序。
易错：忘记给新结点分配内存，或没把新结点挂回父结点的左/右指针，插入后树没有任何变化。
三种情况 + 后继替身。
在 insert/inorder 基础上加 erase：无子/一子直接替父指针；两子取右子树最小者值覆盖，再递归删后继；main 输出删除前后中序。
思路：在 insert / inorder 的基础上加 erase：无孩子或只有一个孩子时，直接让父指针跳过它；有两个孩子时取右子树最小值的值覆盖后递归删除后继；最后输出删除前后的中序序列做对比。
易错：删除时忘记更新父结点的指针，导致整棵子树被丢掉，树结构被写坏。