扫码获取 VIP 码
添加管理员微信获取 VIP 码
在软件设计师、系统分析师和系统架构设计师的历年真题里，二叉树相关考点几乎从未缺席，而其中最容易让考生"看着会、一做就错"的，当属二叉排序树。很多考生能背出"左小右大"四个字，却说不清为什么中序遍历一定有序，也搞不懂删除一个双子树结点到底该怎么顶替，更不明白命题人为什么总爱拿"树高"和"查找效率"设陷阱。本文从定义出发，把二叉排序树的底层原理、三种核心操作、退化与平衡化、常见误区以及真题命题套路一次性讲透，读完你不仅能做对选择题，还能在下午题里稳稳拿分。
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree）、二叉搜索树，简称BST。教材给出的标准定义是：一棵二叉排序树要么是一棵空树，要么是满足下列性质的二叉树——第一，若它的左子树不为空，则左子树上所有结点的关键字值均小于根结点的关键字值；第二，若它的右子树不为空，则右子树上所有结点的关键字值均大于根结点的关键字值；第三，它的左、右子树本身也分别是二叉排序树。
这里要特别注意定义里反复出现的"所有结点"四个字。它不是要求左孩子小于根、右孩子大于根这么简单，而是要求左子树的全部结点都小于根、右子树的全部结点都大于根。这一字之差，正是后续所有性质和操作成立的根本依据。初学者常常只记住"左孩子比根小、右孩子比根大"这种局部关系，忽略了它是"整棵子树与根"之间的全局偏序关系，导致在做判断"给定一棵二叉树是否为二叉排序树"的题目时，误把局部满足当成了整体满足。
理解二叉排序树，必须把它放到二叉树的家族谱系里看。普通二叉树只对结构做约束，即每个结点最多有两棵子树，且子树有严格的左右之分，它完全不关心结点值的大小关系，所以一棵二叉树的结点值可以任意乱放。二叉排序树则是在普通二叉树的结构约束之上，追加了一条关于"值"的偏序约束，正是这条约束赋予了它"查找"的能力。换句话说，普通二叉树是"结构定义"，二叉排序树是"结构加序关系"。
平衡二叉树（AVL树）则是在二叉排序树的基础上再追加一条"高度平衡"的约束：任意结点的左、右子树高度之差的绝对值不超过一。三者是逐层收紧的关系，普通二叉树约束最弱，二叉排序树居中，平衡二叉树约束最强。考试中经常把这三者并列提问，让你判断"二叉排序树是否一定是平衡二叉树""平衡二叉树是否一定是二叉排序树"这类包含关系，答案分别是"不一定"和"一定是"。厘清这层包含关系，很多概念判断题就能一眼看穿。
二叉排序树最核心、也最常考的一条性质是：对一棵二叉排序树进行中序遍历，得到的结点序列一定是按关键字值递增排列的有序序列。这条性质看似神奇，其实完全可以从定义直接推出来。
中序遍历的顺序是"左子树、根、右子树"。根据二叉排序树的定义，左子树所有结点的值都小于根，右子树所有结点的值都大于根。当递归地按照"左—根—右"的顺序访问时，我们先输出的是整棵左子树（其中所有值都小于根），再输出根，最后输出整棵右子树（其中所有值都大于根）。而左右子树本身又是二叉排序树，内部同样满足这个序关系，因此递归到底之后，最终输出的序列天然就是从小到大排列的。这就是"排序树"名字的由来：它把"排序"这件事内化到了结构里，只要做一次中序遍历，就等价于完成了一次排序，而不需要额外的比较交换。
理解了这一点，也就自然明白为什么先序遍历和后序遍历得不到有序序列——先序是"根—左—右"，根先于它所有左子树结点输出，而这些左子树结点的值都小于根，于是序列里会出现"大的在前、小的在后"的乱序；后序同理。命题人最爱考的就是让考生在"先序、中序、后序"里选出"能得到有序序列"的那一个，答案永远是中序。
二叉排序树的查找过程是一条从根到目标结点的路径。每次比较一个结点，如果目标值等于当前结点就命中，小于就走左子树，大于就走右子树。由于每次比较都能排除一整棵子树，所以最坏情况下，查找一条记录的比较次数等于树的高度。
这里就引出了二叉排序树性能的关键变量：树高。当二叉排序树接近平衡时，高度约为以二为底的对数级别，查找效率可以达到对数复杂度；但当它退化成一条单链时，高度等于结点数，查找就退化成了顺序查找，复杂度变为线性级别。因此，"二叉排序树的查找效率是多少"这道题，标准答案绝不能写成"对数级"这么笼统，而必须区分"平均情况"和"最坏情况"——平均约对数级，最坏为线性级。命题人经常设置"二叉排序树查找时间复杂度一定是O(log n)"这样的干扰项，用"一定"两个字把人引入误区。
二叉排序树的查找算法极其简洁：从根结点开始，将目标值与当前结点比较，相等则查找成功；目标值小于当前结点则进入左子树继续查；大于则进入右子树继续查；走到空子树仍未找到，则判定查找失败。这个过程本质上是一棵决策树，每一步都在做一次"二分"式的排除。
插入操作与查找紧密相关，可以理解为"先查找、再落位"。插入一个新结点时，先按照查找规则从根向下走，找到它本应存在的位置——也就是查找失败时碰到的那个空位置，然后把这个新结点挂上去。这里有一个重要的结论：二叉排序树的插入结点一定是作为新的叶子结点加入的，绝不会插入到树的中间。这是因为插入前先执行查找，而查找失败只可能发生在空子树上。理解了"新结点必为叶子"，就能避开很多关于插入位置的误区，也为后面删除操作的理解打下基础。
用一个实例把插入规则看透。设根为五十，左孩子三十，右孩子七十。现要依次插入二十和六十。插入二十：二十小于五十，进入左子树；二十小于三十，进入三十的左空子树，于是二十作为三十的左孩子落位，成为新的叶子。插入六十：六十大于五十，进入右子树；六十小于七十，进入七十的左空子树，于是六十作为七十的左孩子落位。观察这两个新结点，它们无一例外都挂在了查找失败的空子树上，都是叶子。若换一种插入顺序，比如先插入六十再插入二十，最终树形不变，因为二叉排序树的形态由插入序列决定，与单个结点的相对位置无关，只与序列的先后有关。这正是"同一组关键字、不同插入顺序，会得到不同形态的二叉排序树"这一命题结论的直观来源，也是计算题里需要严格按题目给定顺序构造的原因。
删除是二叉排序树三种操作里最复杂、也是下午题和选择题里最容易丢分的部分。删除一个结点，核心原则是"删除后仍然要维持二叉排序树的性质"。根据被删结点的子树情况，分三种情形处理。
第一种，被删结点是叶子结点：直接删除即可，因为它没有子树，不会影响任何序关系。第二种，被删结点只有左子树或只有右子树：用它的那棵子树直接顶替它的位置即可，因为整棵子树的结点值都统一地偏小于或偏大于父结点，顶替后序关系依然成立。第三种，被删结点左右子树均不为空，这是最麻烦的情形。此时不能简单地把某个孩子顶上来，而要用"中序前驱"或"中序后继"来替换：中序前驱是左子树中关键字最大的那个结点，中序后继是右子树中关键字最小的那个结点。用前驱替换被删结点，能保证新的根结点值仍然大于左子树所有值、小于右子树所有值；然后再递归地删除那个前驱结点。由于前驱结点要么是叶子、要么只有左子树，最终总能归约到前两种简单情形。考生务必记住：双子树结点的删除，等价于"用前驱或后继的值替换，再删除前驱或后继"，这是命题的高频点。
用例子把第三种情形彻底说清。设二叉排序树的根是五十，左孩子三十，右孩子七十，三十的右孩子四十，七十的左孩子六十。现在要删除根结点五十。五十左右子树均不为空，属于双子树情形。先找五十的中序后继，即右子树七十里关键字最小的结点，沿七十的左孩子一路向左走到六十，六十没有左孩子，因此六十就是后继。于是用六十替换五十，然后删除原六十结点。原六十是叶子，删除后不破坏任何序关系。删除完成后的树，根变为六十，左子树仍是三十及其右孩子四十，右子树是七十，整个树的中序遍历序列为三十、四十、六十、七十，仍然有序。若改为用中序前驱处理，则找左子树三十里最大的结点四十，用四十替换五十再删除原四十，结果同样有序。这个例子说明，无论用前驱还是后继，结果都满足二叉排序树性质，只是得到的树形略有不同，命题人在选择题里往往只考察操作结果的正确性，而不纠结于唯一形态。