题目

下列二叉树中，可能成为折半查找判定树（不含外部结点）的是( )。

A 选项的二叉树（共 10 个节点）：

B 选项的二叉树（共 11 个节点）：

C 选项的二叉树（共 9 个节点）：

D 选项的二叉树（共 10 个节点）：

编号仅为表述方便（按层序遍历自顶向下、自左向右标注），原题节点皆为空圆。

错因

B

只看到 B "饱满又对称"就觉得它"更像合法判定树"。但左右镜像对称 ≠ 合法——N = 11 时合法判定树要求最底层 4 个叶子统一挂在同一侧（floor 时全是右孩、ceil 时全是左孩）。B 的左半边叶子全挂在父节点的左孩位置（LL.L、LR.L，ceil 风格）、右半边叶子全挂在父节点的右孩位置（RL.R、RR.R，floor 风格）——L 子树用 ceil、R 子树用 floor，左右子树各自合法，但整棵树没有统一的 mid 策略，违反硬约束。

C

把 C 误当成 N = 9 的判定树。N = 9 时合法判定树最底层 2 个叶子的位置是固定的：要么挂在 LL 和 RL 下方（floor），要么挂在 LR 和 RR 下方（ceil）。C 的 2 个叶子分别挂在 LR.L 和 RL.R 下，LR 用 ceil（左孩）而 RL 用 floor（右孩），左右子树 mid 策略不一致。

D

只看根这层 5 vs 4 = 1 就觉得"和 A 一样满足"，忘了判定树要求对每个内部节点都验。D 中 L 子树为 LL 有子、LR 是叶（ceil 风格：左 ≥ 右），R 子树为 RL、RR 都各带 1 个左孩（在 R 内部为 floor 风格）。整棵树左半边和右半边采用了不同 mid 策略，违反一致性。

总解析

核心：折半查找判定树的硬约束

一棵二叉树是 N 个有序元素的折半查找判定树，当且仅当：

1. 中序遍历 = 1, 2, ..., N（即它是一棵 BST）
2. 节点数对称：对每个内部节点，
3. 高度对称：对每个内部节点，左右子树高度差 ≤ 1（平衡性）
4. 同一棵判定树中 mid 取法（floor / ceil）必须对所有子树一致——即所有底层叶子要么"全挂左孩"（ceil），要么"全挂右孩"（floor）

题目节点都是空圆，条件 1 自动忽略。关键就是逐节点检查 2、3，再做整体一致性判定。

Step 1：验 A（合法）

A 共 10 节点，对照 N = 10、ceil 策略（每子树根取 ）的标准展开：

节点	左子树节点数	右子树节点数	差	高度差
根	5	4	1	0
2 (L)	2	2	0	0
3 (R)	2	1	1	1
4 (LL)	1	0	1	1
5 (LR)	1	0	1	1
6 (RL)	1	0	1	1

底层叶子 8、9、10 全部挂在父节点的左孩位置——策略一致（ceil）。✓

A 完美匹配 N = 10 的 ceil-style 折半查找判定树。

Step 2：找 B、C、D 的违反点

选项	总节点数	违反位置	违反类型
B	11	左半边叶子全挂左孩（LL.L、LR.L）、右半边叶子全挂右孩（RL.R、RR.R）	L 子树用 ceil、R 子树用 floor，整树左右镜像但 mid 策略不统一
C	9	2 个底层叶子分布在 LR.L 和 RL.R	左右子树混用 ceil / floor 策略
D	10	L 子树为 LL=2、LR=1（ceil），R 子树为 RL=2、RR=2（floor）	整棵树混用两种 mid 策略

Step 3：归纳

判定树的"形状一致性"是核心——所有内部节点必须用同一种 mid 取法展开。在视觉上表现为：底层叶子要么全部统一在父节点左侧（ceil），要么全部统一在父节点右侧（floor），不能混。

只有 A 整棵树自顶向下递归地满足节点数差 ≤ 1 和高度差 ≤ 1，且 mid 策略全程一致。

最终答案是 A。

判定树识别口诀：①数总节点 N → ②看根的左右子树节点数差是否 ≤ 1 → ③递归对左右子树重复 → ④底层叶子要挂在同侧（"全左孩"或"全右孩"，不能混）。任一条违反，即不是判定树。