扫码获取 VIP 码
添加管理员微信获取 VIP 码
二叉排序树又称二叉查找树、二叉搜索树，英文缩写为BST，是数据结构课程与软考软件设计师、数据库系统工程师等科目中反复出现的核心考点。教材中给出的标准定义可以归纳为一句话：二叉排序树或者是一棵空树，或者是具有如下性质的二叉树——若它的左子树不空，则左子树上所有结点的关键字值均小于根结点的关键字值；若它的右子树不空，则右子树上所有结点的关键字值均大于根结点的关键字值；它的左、右子树也分别为二叉排序树。
这个定义表面简洁，实则包含三个必须同时满足的约束条件。第一个条件是结点关键字的有序性约束，它规定左子树结点一律小于根结点，右子树结点一律大于根结点，这条规则不是针对某一个结点，而是针对整棵子树上每一个结点都成立。第二个条件是递归性约束，左子树和右子树本身也必须各自是一棵二叉排序树，这意味着性质可以层层向下传递，直到叶子结点。第三个条件是隐含的约定，即通常默认各结点的关键字互不相同，考试中若未特别说明，一般认为关键字可以按大小严格区分，从而避免相等的关键字带来的歧义。
需要特别强调的是，二叉排序树的定义完全建立在关键字大小的比较关系之上，而与结点在树中的物理位置无关。一棵树是否为二叉排序树，取决于它是否满足上述有序性规则，而不是取决于它的形状是否规整。因此，一棵完全平衡的二叉树可能不是二叉排序树，而一棵退化成链状的结构反而可能是一棵合法的二叉排序树，只是查找效率极低。理解这一点，是后续辨析众多易错题的基础。
普通二叉树只对结点的形态结构作出约束，即每个结点至多有两棵子树，至于子树中存放什么样的关键字、关键字之间是否有序，普通二叉树一概不管。二叉排序树则在二叉树形态约束的基础上，额外附加了关键字的大小关系约束，使整棵树具有了可用于快速查找的语义信息。
这种语义信息带来的直接后果是：二叉排序树天然支持高效的动态查找。所谓动态查找，是指在查找的过程中还允许插入新结点、删除已有结点，而树的查找性质在操作之后依然得以保持。相比之下，普通二叉树无法提供任何关于关键字位置的线索，只能靠遍历来逐个比较，查找效率等同于顺序扫描。正是这个本质区别，决定了二叉排序树在数据库索引、字典结构、符号表实现等领域的基础地位，也决定了它成为软考命题人年年必考的知识点。
要真正理解二叉排序树的价值，必须把它放回查找结构的演进脉络中审视。静态查找最简单的实现是顺序查找，它的时间复杂度为O(n)，虽然实现简单，但数据量大时效率低下。为了提速，人们发明了二分查找，它要求数据事先存储在顺序表上并排好序，每次比较都能把搜索范围砍掉一半，时间复杂度降到O(logn)。然而二分查找有一个致命缺陷：它只适用于静态数据，一旦需要频繁插入或删除新元素，就必须移动大量元素以维持有序性，维护代价极高。
二叉排序树的出现，正是为了在保持二分查找量级效率的同时，允许高效的动态插入与删除。它把有序序列的逻辑关系通过树的链接结构表达出来，插入和删除只需修改少量指针，无需大规模移动元素。因此，二叉排序树可以理解为一棵把二分查找思想固化到结构中的动态查找树。这一"以空间换动态性、以结构换效率"的设计思想，是软考命题人反复挖掘的底层逻辑，也是考生应当真正吃透而非死记的要点。
二叉排序树最经典的结论之一，是对它进行中序遍历，能够得到关键字按从小到大排列的有序序列。这个结论不是人为规定的巧合，而是由二叉排序树的定义在逻辑上必然推出的结果。中序遍历的顺序是"先访问左子树，再访问根结点，最后访问右子树"。由于左子树上所有结点的关键字都小于根结点，右子树上所有结点的关键字都大于根结点，因此当按照左、根、右的顺序访问时，较小的关键字必然先于根结点被输出，根结点又必然先于较大的关键字被输出。这一顺序关系在递归遍历的过程中被严格保持，最终得到的输出序列必然是从小到大递增的。
反过来理解，这个结论也给出了一个判定二叉排序树的有效方法：给定一棵二叉树，若其中序遍历序列是递增的，并且各关键字互不相同，那么它一定是二叉排序树。考试中常出现的题型是让考生判断某种遍历方式能否得到有序序列，正确答案只有一个，那就是中序遍历。先序遍历访问根结点的时机最早，后序遍历访问根结点的时机最晚，这两种遍历的输出顺序都不受左右子树关键字大小关系的强制约束，因此都不可能保证得到有序序列。这一考点几乎每年都以不同形式出现，考生务必牢牢记住"中序有序"四个字。
二叉排序树的查找算法本质上是一个与根结点逐层比较、逐层下降的过程。查找从根结点开始，将待查关键字与当前结点的关键字进行比较：若相等，则查找成功；若待查关键字小于当前结点关键字，则转入左子树继续查找；若大于，则转入右子树继续查找；若下降到空指针仍未找到，则查找失败。这个过程可以看作是二分查找思想在树结构上的移植，每次比较都能排除一半的搜索范围，区别在于二分查找要求数据存储在顺序表上且事先排好序，而二叉排序树通过树的形态结构天然地实现了这种二分效果。
查找算法的时间复杂度与树的形态密切相关。当二叉排序树接近平衡时，树的高度约为对数级别，查找的时间复杂度为O(logn)，效率与二分查找相当。当二叉排序树退化为一棵只有单边子树的链状结构时，例如按关键字递增顺序依次插入结点，树的高度变为n，查找退化为O(n)的顺序查找。因此，二叉排序树的查找效率完全取决于树的高度，平均查找长度ASL也与树高成正比。这一"形态决定效率"的机制，是命题人设计"构造树、求ASL"类计算题的理论依据。
平均查找长度是衡量查找算法效率的核心量化指标，软考计算题几乎必考。平均查找长度分为查找成功和查找失败两种，考试中以查找成功的平均查找长度为主。它的定义是：在查找成功的前提下，为找到每个关键字所需要进行的比较次数，与该关键字被查找的概率乘积之和。当各关键字被查找的概率相等时，平均查找长度就等于所有关键字比较次数的算术平均值。
在二叉排序树中，查找某个结点所需比较次数恰好等于该结点在树中所处的层数，因为每经过一层就要与一个结点比较一次，根结点在第1层，比较次数为1。因此，求一棵二叉排序树查找成功的平均查找长度，只需统计每个结点的层数，求和后再除以结点总数。以一个由四个结点构成的二叉排序树为例，若根结点在第1层，两个孩子在第2层，再有一个孩子在第3层，则各结点比较次数分别为1、2、2、3，平均查找长度为(1+2+2+3)除以4，结果为2。命题人经常给出关键字序列要求先构造再求ASL，画图与层数统计的准确性直接决定得分。
二叉排序树的插入操作遵循查找的路径：先在树中查找待插入的关键字，若查找成功则说明该关键字已存在，通常不再重复插入；若查找失败，则插入位置正是查找过程中最后停留的那个空指针位置。换句话说，插入操作总是发生在叶子结点的位置上，新结点永远作为某个叶子的左孩子或右孩子挂上去。这个性质保证了插入后整棵树仍然是二叉排序树，因为新结点只是填补了一个本应属于它的空位，没有破坏任何既有的有序关系。
需要特别指出的是，不同的插入顺序会构造出形态完全不同的二叉排序树。对于同一个关键字集合，若按照从小到大或从大到小的顺序插入，每个新结点都只会不断地挂在上一结点的右孩子或左孩子上，最终得到的是一棵彻底退化为链表的树，查找效率降到最低。反之，若按照较为均匀的顺序插入，例如先插入中位数再插入两侧，则能得到一棵接近平衡的树。这一现象是软考的重要命题点，命题人常让考生对比不同插入顺序对树高和ASL的影响，从而检验考生对"形态决定效率"的理解是否到位。
删除操作比插入复杂得多，是软考考查的重点和难点。删除一个结点需要分三种情形处理。第一种情形是待删除结点为叶子结点，直接将其删除即可，不影响其他结点。第二种情形是待删除结点只有一个孩子，此时只需让这个孩子直接顶替被删结点的位置，用其唯一的子树去接替父结点中指向被删结点的指针即可。第三种情形是待删除结点同时拥有左右两个孩子，这是最复杂的一种。常见做法是找到该结点在中序遍
本篇完！