扫码获取 VIP 码
添加管理员微信获取 VIP 码
二叉排序树，又称二叉查找树、二叉搜索树，英文全称为 Binary Search Tree，习惯上简写为 BST。它是数据结构课程中"查找"这一章的核心内容，也是软考中级软件设计师、数据库系统工程师以及高级系统分析师等多个科目反复考查的经典考点。理解二叉排序树，首先必须回到教材给出的正式定义：二叉排序树或者是一棵空树，或者是具有如下性质的二叉树——若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；同时，它的左子树和右子树各自也都是一棵二叉排序树。
这段定义有两点需要特别强调。第一，它是一个递归定义，它用"左右子树也分别是二叉排序树"来约束整棵树，这意味着二叉排序树的性质在每一层、每一个子树中都成立，而不仅仅是在根结点处成立一次。第二，定义中说的是"左子树上所有结点的值均小于根结点的值"，是"所有结点"而非"左孩子"，这个措辞极其关键。很多考生误以为只要左孩子比根小、右孩子比根大就够了，实际上即便左孩子的值小于根，如果左孩子的右子树中混入了一个大于根的值，这棵树仍然不满足二叉排序树的定义。命题人正是利用这一细微差别设置陷阱，稍后会在常见误区部分专门展开。
与普通二叉树相比，二叉排序树多了一条"有序"的约束。普通二叉树只要求每个结点至多有两个孩子，对孩子之间的大小关系不做任何规定；而二叉排序树则在存储结构上叠加了关键字的大小关系，正是这条约束使得它能够把"查找"这一操作从顺序扫描的线性复杂度压缩到与树高相关的对数复杂度。从数据结构设计的角度看，二叉排序树本质上是把有序表的思想搬到了链接存储结构上：有序顺序表支持高效的折半查找，但插入和删除需要大量移动元素；单链表插入删除方便，却只能顺序查找；二叉排序树则在这两者之间取得了折中，兼顾了查找、插入、删除三者的效率。
判断一棵给定的二叉树是不是二叉排序树，最可靠的方法不是逐对比较父子结点，而是做一次中序遍历。根据定义可以证明，二叉排序树的中序遍历序列必然是一个按关键字递增的有序序列，反过来，若一棵二叉树的中序遍历结果是有序递增的，那么它必然是一棵二叉排序树。因此，"中序遍历有序"既是二叉排序树的性质，也是它的充要判定条件。这一结论在实际解题中极其好用：与其纠结每个结点与祖先的大小关系，不如直接写出中序序列看它是否递增。
需要强调的是，先序遍历和后序遍历都不具备这一性质。二叉排序树的先序序列和后序序列并不呈现有序性，唯一保证有序的是中序遍历。这一条是命题人设置是非判断题的高频材料。此外，二叉排序树允许关键字相同吗？在经典定义中通常默认各结点的关键字互不相同，即树中不存在值相等的两个结点。若题目中出现了相等关键字的处理，一般会约定相等的值放在右子树或左子树，但软考考试默认各关键字互异，考生按互异处理即可。
二叉排序树的查找过程，本质上是一个"二分决策"的过程。查找一个给定关键字时，从根结点开始，将待查关键字与当前结点的关键字比较：若相等，则查找成功，返回当前结点；若待查关键字小于当前结点的关键字，则进入左子树继续查找；若大于，则进入右子树继续查找；若沿着某条路径走到了空结点（空指针）仍未找到，则说明树中不存在该关键字，查找失败。
这个过程的巧妙之处在于，每做一次比较，问题的规模就被砍掉了一半左右——因为所有比当前结点小的关键字都集中在左子树，所有比当前结点大的都集中在右子树。因此，在最理想的情况下，即这棵二叉排序树是一棵左右高度大致均衡的平衡树时，查找一趟所经过的路径长度与树的高度相当，而平衡二叉树的高度约为以二为底结点个数的对数，于是查找的时间复杂度可以降到对数级别。这正是二叉排序树相比顺序查找的根本优势：顺序查找在 n 个元素中找一个关键字，平均要比较约二分之 n 次；而一棵形态良好的二叉排序树，在同样的 n 个元素中查找，平均只需比较约以二为底 n 的对数次。
然而必须清醒地看到，这个"对数级"的效率是有前提的，前提就是树形必须接近平衡。如果插入关键字的顺序恰好是递增或递减的，那么每次插入都只能挂在最深的叶子上，整棵树会退化成一棵只有单侧孩子的"单支树"，其形状与单链表无异。此时查找的时间复杂度又跌回线性，二叉排序树失去了全部优势。这一"形态决定效率"的特性，是整个二叉排序树知识体系的灵魂，也是后续引入平衡二叉树、红黑树等改进结构的根本动因。
中序遍历得到有序序列的原因，可以追溯到二叉排序树的递归定义本身。中序遍历的顺序是"左子树、根结点、右子树"，而在二叉排序树中，左子树所有结点的值都小于根，右子树所有结点的值都大于根，于是按"先左、再根、后右"的顺序访问，天然就保证了从小到大输出。把这一性质向每一层递归推广：每一个子树内部，也都遵循"左小于根小于右"的次序，因此整棵树中序遍历的结果必然全局有序。
这个性质还有一个重要的副产品，就是"中序前驱"和"中序后继"这两个概念。在二叉排序树中，某个结点的中序前驱，就是它的左子树中值最大的那个结点，也就是沿左子树一路向右走到尽头；某个结点的中序后继，则是它的右子树中值最小的结点，也就是沿右子树一路向左走到尽头。这两个概念在删除操作中扮演着核心角色，因为删除一个具有两棵子树的结点时，正是要用它的中序前驱或中序后继来顶替它，从而在保持有序性不变的前提下完成删除。可以这样理解：中序前驱和中序后继分别是"紧挨着这个结点、比它小一点"和"比它大一点"的两个结点，用它们顶替被删结点，恰好不会破坏全局的有序排列。
二叉排序树的插入有一个鲜明的特征：新插入的结点最终一定会落在一片叶子的位置上，即它一定成为某个叶子结点的孩子，而绝不会出现在树的内部。插入的算法是：从根结点开始，把待插入的关键字与当前结点比较，若小于则转向左子树，若大于则转向右子树，如此反复，直到遇到一个空指针位置，就把新结点挂在那里。整个过程就是一趟查找的过程，只不过查找失败的位置就是新结点的归宿。
这一特性带来了一个重要的实际应用：给定一个关键字的插入序列，可以唯一地构造出一棵二叉排序树。构造方法就是从头到尾依次执行插入操作。反过来，同一组关键字，以不同的顺序插入，会得到不同形态的二叉排序树，尽管它们的中序遍历结果完全相同。例如关键字集合一、二、三这三个值，若按"二、一、三"的顺序插入，得到的是以二为根、一在左、三在右的平衡树；若按"一、二、三"的顺序插入，得到的则是一棵向右倾斜的单支树。这一现象说明，二叉排序树的形态由插入顺序决定，而不是由关键字集合本身决定，这是理解后续"退化问题"的关键。
建树过程还隐含着一个考点：二叉排序树的先序序列其实就是插入序列本身。因为插入时总是先访问根再依次深入，若按插入顺序输出结点，就等价于一次先序遍历。这一对应关系在某些"由先序序列重建二叉排序树"的题目中可以直接使用。此外，还有一个容易混淆的对应关系值得记牢：给定一棵二叉排序树的中序遍历序列，并不能唯一确定这棵树，因为不同插入顺序生成的树中序序列完全相同；但若同时给出先序序列与中序序列，或者给出插入关键字的具体顺序，树的形态便被唯一锁定。这一结论与普通二叉树的"先序加中序可唯一确定"完全一致，但考生需要意识到，对二叉排序树而言，先序序列本身就蕴含了插入顺序这一额外信息。
删除是二叉排序树三大操作中最复杂的一个，原因在于删除一个结点之后，必须维护整棵树仍然满足二叉排序树的有序性质。教材将删除操作统一归纳为三种情形，考生务必一一吃透。
第一种情形，被删结点是叶子结点。这种情况最简单，直接将其父结点中指向它的指针置空即可，不影响任何其他结点，也不破坏有序性。
第二种情形，被删结点只有一棵子树，即它只有左孩子或只有右孩子。此时只需用它的这棵唯一子树去顶替它的位置，让它的父结点直接指向它的这个唯一孩子即可。因为它的左子树（或右子树）所有结点整体都比它的父结点那一侧的所有结点保持原来的大小关系，所以顶替之后有序性依然成立。
第三种情形，被删结点同时拥有左、右
本篇完！