题目

一棵二叉搜索树如下图所示，、、 分别是对应结点中保存的关键字、三角形表示子树。则子树 T 中任一结点中保存的关键字 X 满足的是( )。

结构（文字版）：根为 ； 的左子树是某未命名子树（三角形）； 的右孩子是 ； 的左孩子是 ， 的右子树是另一未命名子树（三角形）； 的左子树是未命名子树（三角形）， 的右子树就是题目要分析的子树 T（也以三角形表示）。

错因

A

完全没沿祖先链一路推下来，可能把 T 误认成"K_1 的左子树"那个三角形（图里左侧也有一个三角形子树）。其实 T 是 的右子树，从 看 T 在 的右子树里，应该 而不是 ，方向反了。

B

抓住"T 在 子树里"这一点是对的，但搞反了 相对于 的左右位置。 是 的左孩子，T 是 的右子树——T 整体仍属于 的左子树这一侧，所以必有 。如果误以为 是 的右孩子或 T 在 右子树里，就会错填 。

C

下界用对了一半（ 隐含成立，因为 ），但上界紧错了方向：选 C 的人把 T 当成 的左子树，得到 ；实际上 T 是 的右子树，应该 。误把"右子树"读成"左子树"。

总解析

BST 性质回顾：在 BST 中，对任意节点 ，其子树里所有关键字的范围由 与它所有祖先共同决定——

• 对 的每个祖先 ：若 在 的左子树，则 子树所有键都 ；若 在 的右子树，则 子树所有键都 。

把所有这些约束求交，就是 子树关键字的合法区间。

沿 T 的祖先链一路推：

T 的祖先	T 在它的哪一侧	推出的约束
（T 的父结点）	右子树
（ 的父）	左子树（因为 是 的左孩子）
（ 的父）	右子树（ 是 的右孩子）

把三个约束求交：。

由 BST 性质又能推出 （ 在 的右子树里），所以 。最紧的合法区间就是：

最终答案是 D。