408

数据结构

二叉搜索树（BST）

---

定位信息

项目	内容
章节	第六章 查找 · 6.3
知识单元编号	DS-06-03
核心概念	二叉搜索树（BST）、查找、插入、删除、中序遍历有序性
前置知识	二叉树、递归
考试权重	★★★（基础高频，为 AVL 树和红黑树铺垫）

---

知识点讲解

一、二叉搜索树的定义

二叉搜索树（Binary Search Tree，BST），又称二叉排序树（Binary Sort Tree），是一棵二叉树，满足以下性质：

1. 若左子树非空，则左子树上所有结点的关键字 < 根结点的关键字；
2. 若右子树非空，则右子树上所有结点的关键字 > 根结点的关键字；
3. 左、右子树本身也分别是二叉搜索树。

重要性质： 对 BST 进行中序遍历，得到的关键字序列是递增有序的。这是 BST 最核心的性质。

二、查找操作

BST 的查找从根结点开始，沿左/右子树逐层向下：

• 若 key == 当前结点关键字，查找成功；
• 若 key < 当前结点关键字，进入左子树；
• 若 key > 当前结点关键字，进入右子树；
• 若到达空指针，查找失败。

三、插入操作

插入操作以查找为基础：先从根结点查找待插入关键字应插入的位置（查找失败时的空指针处），然后创建新结点插入。

关键：插入位置一定是叶子结点的某个子位置（即查找失败的位置）。

四、删除操作（重点难点）

删除结点 z 时，分三种情况：

1. z 是叶子结点： 直接删除；
2. z 只有一棵子树： 用 z 的子树替代 z；
3. z 有两棵子树： 用 z 的中序前驱（左子树最大结点）或中序后继（右子树最小结点）替代 z 的关键字，然后删除前驱/后继结点（该结点最多只有一棵子树，转化为情况 1 或 2）。

五、BST 操作伪代码（C 风格）

// BST 结点定义
typedef struct BSTNode {
    KeyType key;              // 关键字
    struct BSTNode *lchild;   // 左孩子
    struct BSTNode *rchild;   // 右孩子
} BSTNode, *BSTree;

// === 查找操作（递归实现）===
BSTNode* BST_Search(BSTree T, KeyType key) {
    if (T == NULL) return NULL;         // 查找失败
    if (key == T->key) return T;        // 查找成功
    else if (key < T->key)
        return BST_Search(T->lchild, key); // 在左子树中查找
    else
        return BST_Search(T->rchild, key); // 在右子树中查找
}

// === 插入操作（递归实现）===
// 返回插入后子树的根指针
BSTree BST_Insert(BSTree T, KeyType key) {
    if (T == NULL) {                    // 找到插入位置
        T = (BSTNode*)malloc(sizeof(BSTNode));
        T->key = key;
        T->lchild = T->rchild = NULL;
        return T;
    }
    if (key < T->key)
        T->lchild = BST_Insert(T->lchild, key);  // 插入左子树
    else if (key > T->key)
        T->rchild = BST_Insert(T->rchild, key);  // 插入右子树
    // key == T->key 时不插入（关键字不重复）
    return T;
}

// === 删除操作 ===
// 找到中序前驱（左子树最右结点）
BSTNode* FindMax(BSTree T) {
    while (T->rchild != NULL)
        T = T->rchild;
    return T;
}

BSTree BST_Delete(BSTree T, KeyType key) {
    if (T == NULL) return NULL;
    if (key < T->key)
        T->lchild = BST_Delete(T->lchild, key);
    else if (key > T->key)
        T->rchild = BST_Delete(T->rchild, key);
    else {  // 找到待删除结点
        if (T->lchild == NULL) {        // 情况1&2：无左子
            BSTNode* temp = T->rchild;
            free(T);
            return temp;
        }
        else if (T->rchild == NULL) {   // 情况2：无右子
            BSTNode* temp = T->lchild;
            free(T);
            return temp;
        }
        else {                          // 情况3：有两棵子树
            BSTNode* pred = FindMax(T->lchild); // 中序前驱
            T->key = pred->key;                   // 替换关键字
            T->lchild = BST_Delete(T->lchild, pred->key); // 删除前驱
        }
    }
    return T;
}

六、BST 性能分析

情况	查找时间复杂度	对应树形
最好	O(log n)	平衡 BST（高度 ≈ log n）
最坏	O(n)	退化为单支树（如插入有序序列）
平均	O(log n)	随机构建的 BST

平衡 BST vs 不平衡 BST 对比表：

对比维度	平衡 BST	退化 BST（单支树）
树高	O(log n)	O(n)
查找	O(log n)	O(n)
插入	O(log n)	O(n)
删除	O(log n)	O(n)
形成条件	随机插入序列	有序序列插入

---

记忆辅助

1. "左小右大中序递增" — BST 的核心性质：左子树 < 根 < 右子树，中序遍历有序。
2. "查找失败的地方就是插入的地方" — 插入位置恰好是查找路径末端的空指针处。
3. "删两子找前驱/后继，替换再删" — 删除有两个孩子的结点时，找中序前驱或后继替代，然后删掉前驱/后继（最多一个孩子）。
4. "有序插就退化，随机插才平衡" — BST 退化的根本原因是插入序列有序。

---

例题精解

例题 1：BST 的构建与中序遍历

依次插入关键字序列 {50, 30, 70, 20, 40, 60, 80}，构造 BST，写出中序遍历结果。

解题四步法：

① 审题： 按给定序列依次插入构造 BST，求中序遍历。

② 分析： 每次从根开始比较，小于往左、大于往右，找到空位插入。

③ 构造过程：

• 插入 50：根结点
• 插入 30：30 < 50，插入 50 的左子
• 插入 70：70 > 50，插入 50 的右子
• 插入 20：20 < 50 → 20 < 30，插入 30 的左子
• 插入 40：40 < 50 → 40 > 30，插入 30 的右子
• 插入 60：60 > 50 → 60 < 70，插入 70 的左子
• 插入 80：80 > 50 → 80 > 70，插入 70 的右子

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

中序遍历（左→根→右）：20, 30, 40, 50, 60, 70, 80

④ 结论： 中序遍历结果为递增序列 {20, 30, 40, 50, 60, 70, 80}，验证了 BST 中序有序的性质。

---

例题 2：BST 删除操作

对上题的 BST，删除关键字 30，画出删除后的 BST。

解题四步法：

① 审题： 删除 BST 中关键字为 30 的结点。

② 分析： 结点 30 有两个孩子（左子 20，右子 40），属于情况 3，需要用中序前驱或后继替代。

③ 删除过程：

• 方法一（用中序前驱）：30 的中序前驱是左子树最大结点 20（无右子，本身就是最大）。
  • 用 20 替换 30 的关键字
  • 删除原 20 结点（叶子结点，直接删除）

         50
        /  \
      20    70
        \   / \
        40 60  80

• 方法二（用中序后继）：30 的中序后继是右子树最小结点 40（无左子，本身就是最小）。
  • 用 40 替换 30 的关键字
  • 删除原 40 结点

         50
        /  \
      40    70
     /     / \
    20    60  80

④ 结论： 两种方法均正确，删除后 BST 仍然满足二叉搜索树性质。中序遍历结果均为 {20, 40, 50, 60, 70, 80}。

---

考情分析

维度	说明
考频	高频基础考点，选择题和综合题均有
题型	选择题（BST 性质判断、查找/插入/删除过程）、综合题（BST 构造与分析）
命题趋势	删除操作的三种情况是高频考点；BST 退化问题引出平衡树
常见陷阱	删除有两个孩子的结点时找前驱/后继的位置；BST 不唯一（插入顺序不同）

---

易错点

1. BST 的中序遍历一定是递增有序的，这是判断一棵树是否为 BST 的最直接方法。
2. 删除有两个孩子的结点时，不能直接用子树替代！ 必须找中序前驱或后继替代关键字，再删前驱/后继。
3. BST 的形态与插入顺序有关。 同一组关键字，不同的插入顺序可能得到不同的 BST，但中序遍历结果相同。
4. BST 不保证平衡。 有序序列插入 BST 会退化为单支树，时间复杂度退化为 O(n)，这是引入 AVL 树的动机。

---

来源标注

来源	说明
王道考研	2026 版数据结构讲义 · 第六章 查找
天勤考研	数据结构高分笔记 · 查找部分
严蔚敏	《数据结构（C 语言版）》第 9 章
教材参考	《数据结构》（第 5 版）李春葆 · 查找章节