二叉排序树（BST）

2026 大纲 六（五）1 二叉搜索树（平衡二叉树见《AVL 树》、红黑树见《红黑树》）。

BST 想解决的问题：查得快，还要改得快

先看两种基本的线性结构各自卡在哪：

结构	查找	插入 / 删除	瓶颈
有序数组（折半查找）	$O(\log n)$	$O(n)$	插入要移动后面所有元素
链表	$O(n)$	$O(1)$（已定位时）	查找只能顺序扫描

两者的短板恰好互补：数组"查得快、改得慢"，链表"改得快、查得慢"。根因是同一件事——有序性靠"物理位置相邻"来维持，所以任何插入都要挪位置。

BST 换了个思路：把有序性从"物理位置"改为"树的形状"来维持。 左子树全部小于根、右子树全部大于根，于是查找仍能像折半那样每次排除一半；而插入只需要改一两个指针，不用移动任何已有结点。

代价也很明确：树的形状由插入次序决定，形状不好时"每次排除一半"的保证就没了——这正是后面 AVL 与红黑树要修的问题。

定义与那条推论

二叉排序树（又称二叉查找树 / 二叉搜索树）或为空树，或满足三条：左子树所有结点值小于根、右子树所有结点值大于根、左右子树也分别是二叉排序树。

第三条不是废话——它把约束从"根与直接孩子"扩展到整棵子树，是后面很多判断题的关键。

typedef struct BSTNode {
    int key;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

由定义直接得到 BST 最重要的一条推论：

中序遍历一棵 BST，得到的一定是严格递增的有序序列。

证明对结点数归纳一句即可：整棵树的中序序列是「左子树序列，根，右子树序列」的拼接，而左子树全部 $<$ 根 $<$ 右子树全部。

这条推论是本篇几乎所有结论的源头——判定 BST、求第 $k$ 小、选删除的替身，全从它推出来。

先看一眼

加载可视化中...

判定：只有两种正确方法

中序法：遍历一遍看是否严格递增（见 中序遍历）。

区间法：递归下传取值范围，进左子树把上界收紧为根、进右子树把下界收紧为根。

// 检查以 T 为根的子树，所有关键字是否落在 (low, high) 开区间内
int Check(BSTree T, int low, int high) {
    if (T == NULL) return 1;
    if (T->key <= low || T->key >= high) return 0;   // 违反祖先带下来的约束
    return Check(T->lchild, low, T->key)             // 左子树的上界收紧为当前结点
        && Check(T->rchild, T->key, high);           // 右子树的下界收紧为当前结点
}
// 调用：Check(T, INT_MIN, INT_MAX)

"每个结点大于左孩子、小于右孩子"这种逐点检查是错的：

      5
     / \
    3   8
       / \
      2   9      ← 逐点检查：8 > 5 ✓、2 < 8 ✓、9 > 8 ✓、3 < 5 ✓，全过

它不是 BST：结点 2 虽然是 8 的合法左孩子，却位于根 5 的右子树里，违反了"右子树全部 $>$ 根"。逐点检查漏掉的正是跨层约束，而这恰恰是定义第三条管的事。用区间法：进入 8 的左子树时区间是 $(5,8)$，$2\notin (5,8)$，一步就判出来。

区间法还有一个更常用的变形：算某棵子树里关键字的合法范围。 做法是沿着这棵子树的祖先链一路往上收：祖先 $a$ 若把这棵子树放在自己的左边，则子树所有键 $<a$；放在右边则 $>a$。 把所有约束求交即可。

查找与插入

// 查找（迭代版：无递归栈开销）
BSTNode *BST_Search(BSTree T, int key) {
    while (T != NULL && key != T->key) {
        if (key < T->key)
            T = T->lchild;   // 目标比当前小，只可能在左子树
        else
            T = T->rchild;   // 目标比当前大，只可能在右子树
    }
    return T;                // 找到则返回结点指针，失败则返回 NULL
}

比较次数 $=$ 该结点所在的层次（根算 1 次；与哈夫曼树的 WPL 数边的口径差 1），这是算 ASL 的依据。

插入的规则是：先查 key 是否存在；不存在就在"查找失败停下的那个空位置"插入。

int BST_Insert(BSTree *T, int key) {
    if (*T == NULL) {          // 查找失败的位置，就是插入位置
        *T = (BSTree)malloc(sizeof(BSTNode));
        (*T)->key = key;
        (*T)->lchild = (*T)->rchild = NULL;
        return 1;              // 插入成功
    }
    if (key == (*T)->key)
        return 0;              // 已存在，不插入（BST 不允许重复关键字）
    else if (key < (*T)->key)
        return BST_Insert(&((*T)->lchild), key);   // 递归插入左子树
    else
        return BST_Insert(&((*T)->rchild), key);   // 递归插入右子树
}

参数用二级指针 BSTree *T，是因为插入可能要修改双亲的孩子指针（把原来的 NULL 改成新结点地址）。传一级指针只能改指针指向的内容，改不了指针本身。

新插入的结点一定是叶结点——插入位置是"查找失败停下的空位"，那里本来就没有子树。所以插入不需要移动任何已有结点，只需修改一个指针，这正是 BST 相对有序数组的核心优势。

插入次序决定形态，但不决定中序序列

以关键字集合 $\{45,24,53,12,37,93\}$ 为例：

插入序 (45, 24, 53, 12, 37, 93)          插入序 (12, 24, 37, 45, 53, 93)

          45                                    12
        /    \                                    \
      24      53                                   24
     /  \       \                                    \
   12    37      93                                   37
                                                        \
                                                         45
                                                           \
                                                            53
                                                              \
                                                               93
   高度 3                                        高度 6（退化成单支链）

两棵树的中序序列完全相同（都是 12, 24, 37, 45, 53, 93——由集合唯一决定），但形态与查找效率天差地别。

由此得到一条要紧的结论：关键字有序（或逆序）输入时，BST 退化成单支链，$h=n$，$ASL=(n+1)/2$，与顺序查找相同。这就是引入自平衡机制的直接动机。

反过来，同一棵 BST 也可以由多个不同的插入序生成。判据是插入规则本身：先插入的结点更靠近根，而且一旦根确定，左右子树里结点的相对插入次序互不影响。所以判断"某个序列能不能生成这棵树"，逐个模拟插入最稳；快速判法是看每个结点是否都在它的双亲之后出现，且不出现"某个结点插进来时会被更早的同侧结点截住"的情况。

删除：三种情形

设待删结点为 $z$，摘掉后必须重新接好且不破坏 BST 性质：

情形	做法	为什么合法
$z$ 是叶结点	直接删，双亲的对应指针置空	不影响其他结点的相对位置
$z$ 只有一棵子树	那棵子树顶替 $z$ 的位置接到 $z$ 的双亲上	子树关键字与 $z$ 处在同一区间，整体上移不改变与祖先的大小关系
$z$ 有两棵子树	用 $z$ 的中序前驱（左子树最大者）或中序后继（右子树最小者）的值替换 $z$，再转而删除那个替身	只有中序相邻者换上来才不破坏中序递增；前驱无右子树、后继无左子树，替身必落入前两种情形

void BST_Delete(BSTree *T, int key) {
    if (*T == NULL) return;      // 没找到，什么也不做
    if (key < (*T)->key) {
        BST_Delete(&((*T)->lchild), key);
    } else if (key > (*T)->key) {
        BST_Delete(&((*T)->rchild), key);
    } else {                     // 找到待删结点
        if ((*T)->lchild == NULL) {
            // 覆盖情形一（叶子：rchild 也为 NULL）与情形二（只有右子树）
            BSTNode *temp = *T;
            *T = (*T)->rchild;
            free(temp);
        } else if ((*T)->rchild == NULL) {
            BSTNode *temp = *T;      // 情形二：只有左子树
            *T = (*T)->lchild;
            free(temp);
        } else {
            // 情形三：左右子树都在，取中序后继 = 右子树中最左下的结点
            BSTNode *s = (*T)->rchild;
            while (s->lchild != NULL)
                s = s->lchild;
            (*T)->key = s->key;                  // 用后继的值覆盖待删结点
            BST_Delete(&((*T)->rchild), s->key); // 转而删除后继（它没有左子树）
        }
    }
}

lchild == NULL 这个分支同时覆盖了叶结点和"只有右子树"两种情形——叶结点的 rchild 也是 NULL，赋值后 *T 变成 NULL，正是要的效果。读代码时别以为漏了情形一。

情形三用前驱还是后继，两种都合法，但得到的树不同。 教材默认用中序前驱，理由是"以被删结点左子树中关键字最大的结点替代，此结点一定没有右子树，这样不会增加树的高度"。题目指定就听题目。

三种情形的示意图与边界核对表（逐条核边界时展开）

情形一与情形二：

     45              45                45              45
    /  \    删 12   /  \              /  \    删 24   /  \
  24    53   ──→  24    53          24    53   ──→  12    53
  /                                 /
12                                12

情形三的两种替换：

原树                    删除 45（用中序前驱 37 替换）   删除 45（用中序后继 53 替换）

     45                        37                            53
    /  \                      /  \                          /  \
  24    53                  24    53                      24    93
 /  \     \                /        \                    /  \
12   37    93            12          93                12    37

中序前驱版（只改情形三）：

        } else {
            BSTNode *s = (*T)->lchild;       // 取中序前驱 = 左子树中最右下的结点
            while (s->rchild != NULL)
                s = s->rchild;
            (*T)->key = s->key;
            BST_Delete(&((*T)->lchild), s->key);
        }

输入	走到哪个分支	结果
空树	第一行 return	无操作 ✓
删不存在的关键字	递归到 *T == NULL	无操作 ✓
删叶结点	lchild == NULL 分支，*T = rchild = NULL	双亲对应指针置空 ✓
删只有左子树的结点	rchild == NULL 分支	左子树顶上来 ✓
删根结点	同上三种之一，*T 就是根指针本身	根被正确更新 ✓
情形三的递归	后继无左子树 → 必落入 lchild == NULL	至多再递归一层 ✓

这三种情形还带出一条常被考的对照：删除一个结点再把它插回去，树未必变回原样。

• 删的是叶结点：直接断开，其他结点的位置与父子关系全部不变；再插入时"小走左、大走右"的路径由沿途结点决定，而沿途结点没变，于是一字不差地走回原来那个空位——树复原。
• 删的是非叶结点：替身抢占了它的位置，拓扑已经改写；再把它插回去时它只能落在某个空位上成为叶结点，与原来"顶在内部位置"的形态不同。

查找长度（ASL）

成功与失败两套都要会。 以上面那两棵树（$n=6$）为例：

$$AS{L}_{\text{成功}}=\frac{1}{n}\sum _{i=1}^n{c}_i,c_i=\text{结点 }i\text{ 所在的层次}$$

树 (a) 各层分别有 1、2、3 个结点：$AS{L}_{\text{成功}}(a)=\frac{1\times 1+2\times 2+3\times 3}{6}=\frac{14}{6}\approx 2.33$。树 (b) 是单支链，各结点在第 $1\sim 6$ 层：$AS{L}_{\text{成功}}(b)=\frac{21}{6}=3.5$。单支树的一般公式是 $\frac{n+1}{2}$，与顺序查找完全相同。

失败的分析要先补上失败结点（外部结点）：把树中每一个空指针位置画成一个方框。

失败结点恰有 $n+1$ 个——等于二叉链表的空指针数（见基本概念）。一个失败结点的比较次数 $=$ 它所在层次 $-1$，即从根走到它经过的真实结点个数（走到空指针时才发现失败，那一步不算比较）。

              45
            /    \
          24      53
         /  \    /  \
       12    37 □    93        ← 53 的左空位在第 3 层 → 2 次比较
      /  \  / \     /  \
     □   □ □   □   □    □      ← 其余 6 个空位都在第 4 层 → 各 3 次比较

$$AS{L}_{\text{失败}}(a)=\frac{1\times 2+6\times 3}{7}=\frac{20}{7}\approx 2.86$$

三个计算要点：失败结点有 $n+1$ 个（数漏一个分母就错）；失败的比较次数是层次减 1；失败的 ASL 分母是 $n+1$ 而不是 $n$。

复杂度与横向对比

操作	最好	平均	最坏
查找 / 插入 / 删除	$O({\log }_{2}n)$	$O({\log }_{2}n)$	$O(n)$
中序遍历（输出有序序列）	$O(n)$	$O(n)$	$O(n)$

三种情形的准确含义：最好是树的形态接近完全二叉树（也就是"和折半查找的判定树相似"），$h\approx {\log }_{2}n$；最坏是有序或逆序插入，退化成单支链；平均——把 $n$ 个关键字按各种可能次序插入，可以证明平均查找长度仍与 ${\log }_{2}n$ 同数量级。

和折半查找摆在一起看：

对比项	二叉排序树	折半查找（有序表）
存储	链式，动态	顺序表，必须随机存取
查找	平均 $O(\log n)$，最坏 $O(n)$	恒 $O(\log n)$
插入 / 删除	只改指针，$O(h)$	要移动元素，$O(n)$
适用	需要频繁插入删除的动态查找表	建好后基本不变的静态查找表

这张表最要紧的是一条没写进去的观察：折半查找的判定树本身就是一棵 BST，而且是"尽可能平衡"的那一棵。 所以

BST 的最好情形，恰好就是折半查找。 BST 付出的额外代价（指针空间、形态可能退化）换来的是"插入删除不用移动元素"。

BST 的全部风险集中在一句话：树高不可控。修补方向也只有一个——在插入 / 删除后主动把树"掰平"：AVL 树要求任意结点左右子树高度差 $\le 1$（严格平衡，树高 $\le 1.44{\log }_{2}n$）；红黑树只要求任意路径上黑结点数相同（弱平衡，树高 $\le 2{\log }_2(n+1)$，换来更低的维护代价）。

考点速记

三条会被反复调用的结论：

1. 中序遍历递增是 BST 一切性质的源头：判定、求第 $k$ 小、选删除替身全由它推出。
2. 删除度为 2 的结点必须用中序前驱或后继替换，替身缺一侧子树，必落入前两种简单情形。
3. BST 的效率完全写在树高里，有序输入会让它退化成顺序查找——这正是 AVL 与红黑树存在的理由。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 判断某个序列能不能是一条查找路径。 通法是区间收缩：根的初始范围是 $(-\mathrm{\infty },+\mathrm{\infty })$，往左走则新范围为 $(lo,\text{当前值})$、往右走则为 $(\text{当前值},hi)$，路径上每个结点必须落在前一步划出的区间内。出现越界的那个选项就是答案。这比"画出树来看"快得多。
• 判断某个输入序列能不能生成给定的 BST。 逐个模拟插入，看得到的形态是否一致。抓手是先插入的更靠近根——比如根的左孩子是谁，取决于左半边哪个数先出现。
• 给出 BST 的形状（结点用符号表示），问某棵子树里的关键字满足什么不等式。 沿这棵子树的祖先链逐个收约束再求交：在祖先左边就 $<$ 它，在右边就 $>$ 它。注意最后还要用 BST 性质化简——比如已知 $K_3$ 在 $K_1$ 的右子树里，那么 $max(K_1,K_3)=K_3$，答案取最紧的那个界。
• 删除一个结点再插回去，树变不变。 记住上面那条对照：删的是叶结点则复原，删的是非叶结点则形态改变。
• 判定 BST 的代码大题。 中序遍历 + 维护 prev，一旦当前值 $\le$ prev 立即判否；顺序存储时左右孩子换成下标 $2i+1$、$2i+2$。
• ASL 的计算。 成功的分母是 $n$、比较次数按层次数；失败的分母是 $n+1$、比较次数按层次减 1。

易错：用"每个结点大于左孩子、小于右孩子"判定 BST。 漏掉跨层约束。

易错：失败 ASL 的分母写成 $n$。 失败结点有 $n+1$ 个。

易错：以为同一组关键字只能建出一棵 BST。 形态由插入次序决定，但中序序列相同。

易错：删除后重插一定复原。 只有删叶结点时成立。

教材出处

• 二叉排序树的定义（三条性质）与"由定义可以得出二叉排序树的一个重要性质：中序遍历一棵二叉排序树时可以得到一个结点值递增的有序序列"：严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p198（7.3.1 节）
• 二叉排序树的查找性能分析：以关键字序列 $(45,24,53,12,37,93)$ 与 $(12,24,37,45,53,93)$ 建出的两棵树为例，给出 $ASL(a)=14/6$、$ASL(b)=21/6$；以及"当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树，树的深度为 $n$，其平均查找长度为 $(n+1)/2$（和顺序查找相同），这是最差的情况""可以证明，综合所有可能的情况，就平均而言，二叉排序树的平均查找长度仍然和 ${\log }_{2}n$ 是同数量级的""二叉排序树上的查找和折半查找相差不大。但就维护表的有序性而言，二叉排序树更加有效，因为无需移动记录，只需修改指针即可完成对结点的插入和删除操作"：印刷 p200
• 二叉排序树的插入与创建（算法 7.5、7.6），"每次插入的新结点都是二叉排序树上新的叶子结点，则在进行插入操作时，不必移动其他结点，仅需改动某个结点的指针，由空变为非空即可"：印刷 p202
• 二叉排序树删除的三种情形，以及情形三的两种处理方法及其取舍："令 $\ast p$ 的直接前驱（或直接后继）替代 $\ast p$，然后再从二叉排序树中删去它的直接前驱（或直接后继）……前一种处理方法可能增加树的深度，而后一种方法是以被删结点左子树中关键字最大的结点替代被删结点……此结点一定没有右子树，这样不会增加树的高度，所以常采用这种处理方案"：印刷 p203
• 删除算法 DeleteBST 的完整实现与三种删除情形的图示：印刷 p204–p205

相关知识

平衡二叉树（AVL）｜红黑树｜折半查找（判定树就是平衡 BST，即 BST 的最好情形）｜查找的基本概念｜B 树｜堆（只保证双亲优于孩子，查任意元素 $O(n)$）｜中序遍历

相关文章

• 树与二叉树基本概念
• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历
• 由遍历序列构造二叉树
• 线索二叉树
• 平衡二叉树（AVL）
• 红黑树
• 哈夫曼树
• 堆（大根堆/小根堆）
• 并查集
• 树与森林
• 树与森林的转换

交互体验

前往完整可视化页面 →

真题练习

相关真题（8题）

2026Q4113分2024Q72分2022Q4113分2020Q52分2018Q62分2013Q62分2013Q4210分2011Q72分