题目

在任意一棵非空二叉排序树 T1 中，删除某结点 v 之后形成二叉排序树 T2 ，再将 v 插入 T2 形成二叉排序树 T3 。下列关于 T1 与 T3 的叙述中，正确的是( )。

I. 若 v 是 T1 的叶结点，则 T1 与 T3 不同

II. 若 v 是 T1 的叶结点，则 T1 与 T3 相同

III. 若 v 不是 T1 的叶结点，则 T1 与 T3 不同

IV. 若 v 不是 T1 的叶结点，则 T1 与 T3 相同

错因

A

把 II 错判成 I——以为"叶节点 v 删完再插，路径要重走、可能挂到别的位置"。但 BST 的插入是确定性的：只要 T2 = T1 删去 v 后的结果（即除 v 之外其他节点结构完全保留），插入 v 时按值比较走出来的路径与原来一模一样，最终落在原来那个空位上。所以 I 错、II 对。

B

I 和 IV 同时错。I 已分析；IV 错在"非叶节点删除会动用前驱/后继替代，结构必变，再插入只能成为新叶子"——v 在原树是分支节点（有子），插回来时按 BST 规则只能挂在某个空指针处变成叶子，不可能恢复"有子"的状态。

D

II 对，但 IV 也错（同 B）。选 D 的人通常确实理解了叶节点情形（II 对），但没看穿非叶情形里"v 在 T3 里只能当叶子"这一点——因为插入算法永远把新节点挂到某个空位，无法让它在树中部 "撑开"原来的子树。

总解析

分两种情况推演：

情况一：v 是 T1 的叶子

删除叶子是最简单的删除——直接断开 v 与父亲的连接，其他节点的位置/父子关系完全不变。

T2 = T1 \ {v}，结构上除了 v 缺一席之外其他节点都在原位。

再插入 v：BST 插入按"小于走左、大于走右"，从根开始走的路径完全由"v 的值"和"沿途节点的值"决定。沿途节点既然没变，路径就一字不差地重走原来到 v 的那条路；终点是同一个空位置（即原来 v 的位置）。

T3 与 T1 完全相同。✓ II 成立。

情况二：v 是 T1 的非叶（有孩子）

非叶删除有标准做法（任选其一）：

• 用 v 的直接后继（v 右子树的最左节点）替代 v
• 或用 v 的直接前驱（v 左子树的最右节点）替代 v

无论哪种，T2 的结构都和 T1 不一样——原本"v 顶在某个内部位置"的拓扑被改写了，替代节点抢占了 v 的位置，自身原来的子位置被它的子（或空）顶上。

再插入 v 到 T2：BST 插入只把新节点挂到某条搜索路径终点的空指针处，必然成为新的叶子。但 v 在 T1 里是有子节点的内部节点，T3 把它放到叶子位置，结构不可能与 T1 一致。

T3 与 T1 必不同。✓ III 成立。

小例验证（情况二）

设 T1：

删除非叶 3（用其直接后继 4 替代）：

插入 3：3 < 5 → 左；3 < 4 → 左；2 已在左，3 > 2 → 2 的右子，挂上：

T3 ≠ T1（3 从 T1 的内部节点变成 T3 的叶子）。

结论

正确陈述：II + III ⇒ 选 C。

速记：BST 里"删一个再插同一个"——叶子删插复原，非叶删插结构必变。本质是因为插入算法"只能挂叶子"，无法把节点放回原来的内部位置。

最终答案是 C（仅 II、III）。