二叉搜索树（Binary Search Tree）简称 BST，是二叉树的一种特殊形式。它有很多别名，比如排序二叉树、二叉查找树等等。

虽然二叉搜索树多年来一直作为算法面试的“必要考点”存在，但在实际面试中，它的考察频率并不能和常规二叉树相提并论，算不上“大热”的考点，同时考察内容也是相对比较稳定的。对于二叉搜索树，我们只要能够把握好它的限制条件和特性，就足以应对大部分的考题。

什么是二叉搜索树

⚡ 30 秒速记

• 对每个结点，左子树所有值小于它，右子树所有值大于它；该约束作用于整棵子树而非只看直接孩子
• 中序遍历严格递增是无重复 BST 的等价特征，搜索可根据大小每次排除一侧
• 操作复杂度是 O(h)：平衡时约 O(log n)，退化成单链时为 O(n)

二叉搜索树是一种有序二叉树：任意结点的左子树值都不大于它，右子树值都不小于它，并且两棵子树也满足同样规则。 这个定义是递归的，所以空树本身也是二叉搜索树。判断时不能只比较结点和直接孩子，还要保证整棵左、右子树都符合大小关系。边界上该定义允许出现相等值，但相等结点具体放在哪一侧仍要遵守题目的约定。

树的定义总是以递归的形式出现，二叉搜索树也不例外，它的递归定义如下：

• 是一棵空树
• 是一棵由根结点、左子树、右子树组成的树，同时左子树和右子树都是二叉搜索树，且左子树上所有结点的数据域都小于等于根结点的数据域，右子树上所有结点的数据域都大于等于根结点的数据域

满足以上两个条件之一的二叉树，就是二叉搜索树。

从这个定义我们可以看出，二叉搜索树强调的是数据域的有序性。也就是说，二叉搜索树上的每一棵子树，都应该满足 左孩子 <= 根结点 <= 右孩子 这样的大小关系。下图我给出了几个二叉搜索树的示例

以第三棵树为例，根结点的数据域为6，它的左子树的所有结点都小于等于6、右子树的所有结点都大于等于6。同时在任意子树的内部，也满足这个条件——比如左子树中，根结点值为3，根结点对应左子树的所有结点都小于等于3、右子树的所有结点都大于等于3。

💬 面试官追问

• 代码评审里验证函数只检查每个结点的左孩子不大于它、右孩子不小于它；页面上的树为根 10、左子树中出现结点 12，为什么局部检查会误判？

  结点 12 虽可能满足其直接父结点的局部关系，却违反了整个左子树都不大于根 10 的约束。二叉搜索树的条件作用于每棵子树的全部结点，验证时必须携带祖先限定，不能只比较父子三元组。

• 你要给后台树形配置页实现 isBST，数据由接口反序列化而来且可能为空；递归代码应怎样传递约束，才能覆盖深层非法结点？

  空树应直接判定为合法，非空结点则同时接受祖先传下来的下界与上界。检查当前值落在允许区间后，左子树收紧上界、右子树收紧下界并继续递归；边界是否包含等号必须与重复值规则一致。

• 订单索引允许多个结点拥有相同键值，开发者一处把相等值插到左侧，另一处搜索时只向右找相等值，这种约束变化该怎么处理？

  定义允许左子树值小于等于根、右子树值大于等于根，因此相等值可能出现在任一侧，但实现仍需统一契约。插入、搜索、验证和删除必须采用兼容策略，或把重复次数集中记录；否则树形式合法，业务查找仍可能漏项。

• 线上搜索偶发找不到已写入的配置，日志显示从根结点按大小选分支后提前走到空结点；你会怎样判断是搜索代码还是树结构损坏？

  先沿失败搜索路径记录当前值与选择方向，再校验每个祖先对应子树的整体取值范围。若某个后代越过祖先边界，按大小剪枝必然跳过它，故障在构建或修改阶段；若结构满足约束，再检查相等值的分支规则是否一致。

• 团队为只读查询页争论使用二叉搜索树还是有序数组，数据加载后不再修改且页面频繁按位置读取，你会依据什么做取舍？

  二叉搜索树强调按数据域维持递归有序，但它并不天然提供数组式的直接下标访问。数据固定且按位置读取占主导时，有序数组通常更贴合访问路径；若需要频繁插入，数组移动元素的代价才会让树形结构更有讨论价值。

• 调试工具把一棵树中序输出为非递减序列，评审者据此认定它满足二叉搜索树定义；在允许重复值的前提下，这个判断为什么成立或可能失效？

  若中序遍历覆盖全部结点且输出非递减，它与左子树值不大于根、右子树值不小于根的递归约束相符，可作为验证依据。若遍历漏结点、比较器与建树规则不一致，或业务要求重复值只能放固定一侧，仅看数值序列就不足以验证额外契约。