题目

下列给定的关键字输入序列中，不能生成如下二叉排序树的是( )。

错因

A

直觉上"先插 5 之后再插 2、1、3 应该会破坏左右结构"，于是错选 A。其实 5 走到 4 的右子树独立成枝，与左子树（后续插入的 2,1,3）互不影响——结构最终仍是 。BST 插入只看大小关系，不看插入先后。

C

被"5 在 2 之后插入"迷惑——觉得"应该先插 5 再插 2"才合理。其实 4 之后无论先插 2 还是先插 5，2 和 5 各走一边互不交叉。3 走到 4 左子树后比 2 大成为 2 的右孩子，1 比 2 小成为左孩子，最终仍是给定结构。

D

被"5 最后才插入"迷惑，认为"5 应该在前面就插好"。但 BST 的子树根不一定先插入——节点最终位置由比较路径决定，与插入顺序无关。D 序列依次得到 ，正好是题目给的结构。

总解析

核心规则：BST 插入新节点时，从根开始按"小走左、大走右"找到第一个空位放下，先插入的节点更靠近根。所以一旦确定了根，剩下两个子树是相互独立的——左右子树里节点的相对插入顺序互不影响。

逐个验证四个选项：

A.

步	插入	比较路径	结果
1	4	空树	根 = 4
2	5	5 > 4 → 右	4 的右孩子
3	2	2 < 4 → 左	4 的左孩子
4	1	1 < 4 → 左; 1 < 2 → 左	2 的左孩子
5	3	3 < 4 → 左; 3 > 2 → 右	2 的右孩子

得到 ✓

B.

步	插入	比较路径	结果
1	4	空树	根 = 4
2	5	5 > 4 → 右	4 的右孩子
3	1	1 < 4 → 左	4 的左孩子是 1（不是 2！）
4	2	1 < 2 < 4，走 4 左 → 1 的右	1 的右孩子
5	3	1 < 3 < 4，走 4 左 → 1 右 → 比 2 大走右	2 的右孩子

得到的树是：

4 的左孩子是 1，不是题目给的 2。所以 B 不能生成给定的 BST。

C.

依次：根 4 → 2 是 4 的左 → 5 是 4 的右 → 3 走左到 2 后比 2 大成右 → 1 走左到 2 后比 2 小成左。得到 ✓

D.

依次：根 4 → 2 是 4 的左 → 1 是 2 的左 → 3 是 2 的右（3 < 4 走左、3 > 2 走右）→ 5 是 4 的右。得到 ✓

关键观察：要生成 ，必须满足"2 比 1、3 先插入"（否则 4 的左孩子就成了 1 或 3）。B 中 1 在 2 之前插入，违反此条件。

最终答案是 B（4, 5, 1, 2, 3）。

速判技巧：题目要求生成的结构里 4 的左孩子是 2，所以序列里 2 必须比 1 和 3 先出现（在 4 之后）；类似地 4 的右孩子是 5，5 必须比所有比 5 大的元素先插入（本题没有比 5 大的元素，所以 5 的位置不受约束）。用这个原则一眼能筛掉 B（B 中 1 在 2 之前）。