← 目录 / 算法文档 · 模块十一 树与二叉树 / 11.4 二叉搜索树

11.4　二叉搜索树

给二叉树加一条"左小右大"的规则，查找、插入的效率就能逼近二分查找。

本页目录
① 核心规则：左小右大

回忆一下 7.2 节的二分查找：在一个有序数组里找一个数，每次都能排除一半的可能范围，效率是 O(log n)。二叉搜索树（Binary Search Tree，简称 BST）把这个"每次排除一半"的思路，从数组搬到了树上——只要给普通二叉树加一条规则：

📏
BST 的核心规则：对树上任意一个节点来说，它左子树里所有节点的值都比它小，右子树里所有节点的值都比它大。这条规则不仅对根节点成立，对树上任意一个节点（包括子树的根）都成立。
5 3 8 1 4 7 9
根节点 5：左子树 {3,1,4} 全部小于 5，右子树 {8,7,9} 全部大于 5。再往下看节点 3：它的左子树 {1} 小于 3，右子树 {4} 大于 3——同一条规则在树上任意位置都成立。本节接下来都用这棵树作为例子。
💡
额外的好处：把这棵树按 11.3 节学过的中序遍历（左→根→右）走一遍，会发现访问顺序正好是 1 3 4 5 7 8 9——完全升序排列。这不是巧合：BST 的"左小右大"规则，保证了中序遍历得到的一定是一个有序序列。
② 查找：像二分查找一样，一路排除一半

因为"左小右大"的规则对每个节点都成立，查找一个值时，每到一个节点只需要比较一次，就能确定接下来往左走还是往右走——和二分查找每次排除一半区间的思路完全一致。以在上面的树里查找 7 为例：

当前节点比较下一步
57 > 5往右子树走
87 < 8往左子树走
77 == 7找到，返回
C++ · BST 查找（递归）
1TreeNode* Search(TreeNode* root, int target)
2{
3 if (root == nullptr || root->val == target)
4 {
5 return root; // 没找到（root为空）或正好找到，都直接返回
6 }
7 if (target < root->val)
8 {
9 return Search(root->left, target); // 比根小，只可能在左子树
10 }
11 else
12 {
13 return Search(root->right, target); // 比根大，只可能在右子树
14 }
15}
💡
为什么快：每比较一次，要么直接命中，要么就能整个排除掉另一半子树，完全不用管那半边到底有什么。如果树"长得比较匀称"（左右两边节点数差不多），查找一个值最多只需要比较"树的高度"那么多次，也就是 O(log n)——这就是二分查找思想在树上的体现。
③ 插入：先找位置，再挂上去

插入一个新值，做法和查找几乎一样：按"左小右大"的规则一路往下走，走到某个方向是空（nullptr）的时候，说明找到了该插入的位置，把新节点挂在那里就行。以插入 6 为例：

当前节点比较下一步
56 > 5往右子树走
86 < 8往左子树走
76 < 7，且 7 没有左孩子把 6 挂在 7 的左边
C++ · BST 插入（递归）
1TreeNode* Insert(TreeNode* root, int val)
2{
3 if (root == nullptr)
4 {
5 return new TreeNode(val); // 走到空位置，新建节点挂在这里
6 }
7 if (val < root->val)
8 {
9 root->left = Insert(root->left, val); // 递归结果重新接回 left
10 }
11 else if (val > root->val)
12 {
13 root->right = Insert(root->right, val); // 递归结果重新接回 right
14 }
15 // val == root->val 的情况：值已存在，什么都不做（BST 通常不存重复值）
16 return root; // 把（可能没变化的）root 返回给上一层
17}
📖
为什么要写 root->left = Insert(root->left, val) 而不是直接调用 Insert(root->left, val)？因为当 root->left 原本是 nullptr 时，新建的节点必须真正"接"到父节点上——递归调用本身不会自动修改父节点的指针，必须靠返回值 + 重新赋值把新建的节点接回树里，这是递归修改树结构时的标准写法。
④ 删除：分三种情况讨论

删除是 BST 里最复杂的操作，因为删掉一个节点之后，还要保证"左小右大"的规则不被破坏。按被删节点的孩子个数，分三种情况处理：

情况处理方式
叶子节点（没有孩子）直接删除，把父节点对应的指针设为 nullptr
只有一个孩子让这个孩子"补位"，直接顶替被删节点的位置
有两个孩子找到右子树里最小的节点（它的"中序后继"），用这个值覆盖被删节点，再去右子树里删除那个后继节点（后继节点必然属于前两种简单情况）
💡
为什么找"右子树里最小的节点"能保住规则？右子树里所有值都比被删节点大，而右子树里最小的那个值，恰好是"比被删节点大的所有值里最小的一个"——用它顶替被删节点的位置，左边（都更小）和右边（除了它自己都更大）的大小关系依然成立。同理，用"左子树里最大的节点"顶替也是可以的，两种做法都正确。
C++ · BST 删除（递归）
1TreeNode* FindMin(TreeNode* root)
2{
3 while (root->left != nullptr) // 一路往左，走到底就是最小值
4 {
5 root = root->left;
6 }
7 return root;
8}
9
10TreeNode* Delete(TreeNode* root, int val)
11{
12 if (root == nullptr) return root; // 没找到要删的值，什么都不做
13
14 if (val < root->val)
15 {
16 root->left = Delete(root->left, val); // 要删的值更小，去左子树删
17 }
18 else if (val > root->val)
19 {
20 root->right = Delete(root->right, val); // 要删的值更大，去右子树删
21 }
22 else // val == root->val，找到了要删的节点
23 {
24 if (root->left == nullptr) // 情况一/二：没有左孩子（含叶子）
25 {
26 TreeNode* temp = root->right; // 右孩子（可能是 nullptr）直接补位
27 delete root;
28 return temp;
29 }
30 else if (root->right == nullptr) // 情况二：只有左孩子
31 {
32 TreeNode* temp = root->left; // 左孩子直接补位
33 delete root;
34 return temp;
35 }
36 else // 情况三：左右孩子都有
37 {
38 TreeNode* successor = FindMin(root->right); // 右子树里最小的节点
39 root->val = successor->val; // 用后继的值覆盖当前节点
40 root->right = Delete(root->right, successor->val); // 再去右子树删掉那个后继（一定是简单情况）
41 }
42 }
43 return root;
44}
🎓
拓展：BST 也可能"退化"成一条链。如果插入的值本身就是有序的（比如依次插入 1、2、3、4、5），每个新节点都只能挂在上一个节点的右边，整棵树会变成一条链，查找、插入的效率从 O(log n) 退化成 O(n)，二分的优势完全消失。解决这个问题需要"自平衡"的树结构（比如 AVL 树、红黑树），这部分内容比较深入，作为拓展了解即可，本节不展开。
⑤ 完整代码实现

把查找、插入、删除三个操作和 11.2 节的节点定义放在一起，就是一份完整可用的 BST 实现。建议自己动手敲一遍，用本节的示例数据（依次插入 5,3,8,1,4,7,9）验证查找和删除是否符合预期：

C++ · 二叉搜索树完整实现
1struct TreeNode
2{
3 int val;
4 TreeNode* left;
5 TreeNode* right;
6 TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
7};
8
9TreeNode* Insert(TreeNode* root, int val)
10{
11 if (root == nullptr) return new TreeNode(val);
12 if (val < root->val) root->left = Insert(root->left, val);
13 else if (val > root->val) root->right = Insert(root->right, val);
14 return root;
15}
16
17TreeNode* Search(TreeNode* root, int target)
18{
19 if (root == nullptr || root->val == target) return root;
20 return target < root->val ? Search(root->left, target) : Search(root->right, target);
21}
22
23// Delete 与 FindMin 见上文，此处省略（结构相同，直接拼接即可）
✏️
动手试一试：把上面查找、插入、删除三段代码和结构体定义拼成一个完整程序，依次插入 5,3,8,1,4,7,9，然后：① 查找 7 和 6，验证一个能找到一个找不到；② 删除叶子节点 1，再删除只有一个孩子的节点（插入 6 后的节点 7），最后删除有两个孩子的根节点 5，每次删除后用中序遍历打印一遍，检查结果是否仍然有序。
⑥ 常见陷阱

把本节内容汇总成几条最容易踩坑的规则：

⚠
插入、删除时忘记用返回值重新赋值：递归修改树结构时，必须写成 root->left = Insert(root->left, val) 这种"重新接回去"的形式，而不能只写 Insert(root->left, val)——否则新建或修改的节点根本没有真正连接到树上，函数看似执行了，树的结构却完全没变。
⚠
删除"有两个孩子"的节点时，忘记处理"覆盖值之后还要删掉原来的后继节点"：只把后继节点的值复制过来是不够的——右子树里原来那个后继节点还存在，必须再递归调用一次 Delete 把它删掉，否则同一个值会在树里出现两次。
⚠
误以为 BST 一定是"平衡"的，查找一定是 O(log n)：BST 只保证"左小右大"，不保证树的形状匀称。如果插入顺序恰好是有序的，树会退化成一条链，查找效率退化到 O(n)。写代码时如果对复杂度有严格要求，需要考虑用平衡树（AVL、红黑树等）代替普通 BST。
🏆
本模块小结：从认识"节点、深度、高度"这些基本概念开始，到用数组或链表存下一棵树，再到四种不同的遍历顺序，最后落到 BST 这个把"二分"思想搬到树上的经典应用——树是后面学习堆、线段树、字典树、乃至各种树形 DP 的共同基础，值得反复回顾这四节的内容。