扫码获取 VIP 码
添加管理员微信获取 VIP 码
二叉排序树，又称二叉查找树、二叉搜索树，英文缩写BST。在软考官方教材《数据结构》中，其定义表述为：二叉排序树或者是一棵空树，或者是具有如下性质的二叉树——若它的左子树非空，则左子树上所有结点的关键字值均小于根结点的关键字值；若它的右子树非空，则右子树上所有结点的关键字值均大于根结点的关键字值；它的左、右子树本身也分别是二叉排序树。
这一定义值得逐字拆解。第一层含义是递归性：定义本身用自身来定义，左子树和右子树都必须再次满足二叉排序树的全部性质。这意味着性质约束不只在根结点处成立，而是贯通整棵树的每一层、每一个结点。很多考生只记住了"左小右大"四个字，却忽略了"所有结点"与"本身也是二叉排序树"这两个限定语，一旦遇到"某结点的左孩子小于它，但左孩子的右孩子大于它"这类情况，就无法判断该树是否仍是二叉排序树。第二层含义是全序约束：约束施加在整棵子树上，而不是单个孩子结点上。左子树上的每一个结点都必须小于根，右子树上的每一个结点都必须大于根。第三层含义是关键字唯一性假设：软考教材默认各结点关键字互不相同，因此定义中采用严格的"小于""大于"，而不出现"小于等于"。这一假设贯穿了查找、插入、删除的全部分析，一旦允许重复关键字，平均查找长度的计算与删除算法都需要另行约定。
从查找表技术演进的视角看，二叉排序树的定位更加清晰。查找表的物理实现有三种基本形态：顺序表支持顺序查找，查找效率与表长成正比；有序顺序表支持二分查找，查找效率高，但插入删除需要大量移动元素；树表则以链式结构支持动态查找，兼顾了查找效率与插入删除效率。二叉排序树正是树表中最基础的形态，其核心价值在于把二分查找的折半思想移植到支持动态修改的链式结构上。软考常以查找表实现对比为背景出题，考生需要记住一句话：顺序查找适合小表与链表，二分查找适合静态有序表，二叉排序树适合频繁插入删除的动态场景。
与普通二叉树相比，二叉排序树多了排序约束这一条限制；与堆相比，二叉排序树的约束规则又完全不同。堆要求父结点与孩子结点之间满足大顶或小顶关系，但左右孩子之间没有次序要求；二叉排序树则要求左子树整体小于右子树整体，是一种全序结构。这一区别是软考辨析题的常见素材，考题经常给出一个满足堆性质却不满足排序树性质的树形，让考生辨析约束条件的差异。
二叉排序树最重要的派生性质是中序遍历有序性：对一棵二叉排序树进行中序遍历，得到的结点关键字序列必然是一个严格递增的有序序列。这一性质具有充分必要性，也就是说，一棵二叉树是二叉排序树，当且仅当其中序遍历序列严格递增。这一性质的价值体现在三个方面。
其一，它是判断题的快速解法。给定一棵画好的二叉树，让考生判断是否为二叉排序树时，不必逐结点验证定义，只需写出中序序列看是否递增即可。其二，它是构造题的检验手段。手工构造二叉排序树后，用中序序列是否递增来检查构造是否正确，比逐个结点核对高效得多。其三，它是多个考点之间的桥梁。二叉排序树的中序序列有序性，直接连接了"二叉树的遍历"与"有序序列的二分查找"两个知识模块，理解这一纽带后，二叉排序树的查找性能分析就顺理成章：查找本质上是把有序序列的二分查找映射到树形结构上，树的形态决定了查找路径的长度。
二叉排序树的查找过程是典型的递归比较过程。从根结点开始，将待查关键字与当前结点比较：相等则查找成功；小于则转入左子树继续查找；大于则转入右子树继续查找；若走到空指针仍未命中，则查找失败。查找成功时经过的结点序列称为查找路径，比较次数等于查找路径上的结点数，也就是命中结点所在的层数。
这一过程与有序数组的二分查找在逻辑上完全同构：根结点扮演了中间元素的角色，左子树对应左半区间，右子树对应右半区间。但树形结构引入了形态差异：二分查找的区间划分总是严格对半，而二叉排序树的左右子树规模完全取决于构造时关键字的插入顺序。这一差异直接导致了二叉排序树查找性能的不确定性，也为平衡二叉树的出现埋下了伏笔。理想形态下，二叉排序树接近一棵满二叉树，查找时间复杂度为以二为底n的对数级别；最坏形态下，插入序列本身有序，树退化成一条单链，查找退化为顺序查找，时间复杂度线性增长。查找的时间复杂度只与树的高度有关，与结点总数无直接函数关系，这一结论在软考选择题中反复出现。举一个具体实例加深理解：在由五十、三十、七十、二十、四十、六十、八十构成的二叉排序树中查找四十，先与五十比较，四十小于五十进入左子树；再与三十比较，四十大于三十进入右子树；与四十比较相等，查找成功，共比较三次。查找六十则需先与五十比较，再与七十比较，再与六十比较，同样三次。本例中各叶结点均位于第三层，查找比较次数与层号一一对应，这就是ASL按层统计的直观来源。
平均查找长度（ASL）是衡量查找效率的定量指标，其定义为：在等概率假设下，查找每个结点的比较次数的期望值。计算公式为ASL等于各层结点数乘以层号再求和，除以结点总数。层号从根结点所在的第一层算起。以一棵包含七个结点的满二叉排序树为例，根结点在第一层，第二层两个结点，第三层四个结点，则ASL等于一乘以一加上二乘以二加上四乘以三，再除以七，结果约为二点四三。
ASL计算的三个易错细节需要特别强调。第一，层号必须从一层起算，若按零层起算则结果偏小，软考选择题的干扰项往往正是按零层起算的错误结果。第二，ASL只统计查找成功的情形，查找失败结点的比较次数属于另一指标，除非题目明确要求。查找失败的平均查找长度计算需要先构造扩充二叉树，将空指针位置补上外部结点，再分层统计，软考中此问法较少但偶有出现，遇到时务必先补外部结点再计算。第三，等概率假设不可忘记，若题目给出非等概率的访问频率，ASL公式需要加权，此时构造顺序还涉及最优二叉排序树问题，该问题超出软考常规范围，但命题人会以此作为干扰项迷惑考生。
二叉排序树的插入操作遵循查找路径复制原则：先执行一次查找，确定插入位置。由于插入前的树不存在该关键字，查找必然以落到某个空指针位置而结束，新结点就挂载在这个空指针位置上。因此，插入后的新结点必然是叶子结点。这一结论在软考中至少有三个用途：判断给定插入序列构造结果的唯一性、快速绘制构造过程图、排除选择题中"新结点带子树"的错误选项。
值得深入辨析的是，插入序列决定了树的最终形态，而同一组关键字的插入顺序不同，构造出的二叉排序树形态可能完全不同。例如关键字集合相同，按递增顺序插入得到的是右斜单链，按均衡的顺序插入得到的是接近满二叉树的形态。软考构造题的标准解法就是严格按照给定序列逐个插入，每次插入都从根开始比较，最终画出完整形态。解题时切不可先排序再"贴"到树上，那会得到错误的形态。以一个七元素序列为例演示构造全过程：依次插入五十、三十、七十、二十、四十、六十、八十，第一步插入五十成为根；第二步三十小于五十，成为根的左孩子；第三步七十大于五十，成为根的右孩子；第四步二十小于五十再小于三十，成为三十的左孩子；第五步四十落在三十的右孩子位置；第六步六十落在七十的左孩子位置；第七步八十落在七十的右孩子位置。最终得到一棵满二叉树，中序序列为二十、三十、四十、五十、六十、七十、八十，严格递增，验证构造正确。这个例子同时展示了均衡插入序列带来的理想形态，为理解后续的平衡概念做了铺垫。
删除操作是二叉排序树三大操作中最复杂的一个，必须分三种情形处理。第一种情形，被删结点是叶子结点，直接删除即可，其父结点对应的指针置空。第二种情形，被删结点只有一棵子树，则用其唯一的子树根结点顶替被删结点的位置。第三种情形，被删结点左右子树均非空，这是难点所在，不能简单删除，也不能随意指定一个孩子顶替，否则会破坏排序性质。标准做法是用被删结点的中序前驱或中序后继顶替：中序前驱是左子树中关键字最大的结点，即左子树的最右下方结点；中序后继是右子树中关键字最小的结点，即右子树的最左下方结点。顶替后，再递归删除顶替结点在原子树中的原位置，由于顶替结点至多只有一棵子树，递归删除最终会归结为第一种或第二种情形。
为什么必须用中序前驱或中序后继顶替？根本原因在于中序序列的连续性。删除一个结点后，中序序列去掉该关键字仍应保持有序，而能够无缝填入空缺位置的，恰好是原序列中它的直接前驱或直接后继。用左子树的最大值顶替，保证左子树其余结点仍小于新值，右子树所有结点仍大于新值，排序性质得以完整保持。软考题目常让考生在给定树上执行删除后选出新的形态，解题关键是先定位中序前驱或后继，再逐步完成顶替与递归删除。