折半查找判定树实际上是一棵二叉搜索树，它的中序遍历序列是一个单调序列。

折半查找即二分查找，假设搜索的有序数组为 A[1:n] ，目标元素为 target，二分查找伪代码如下：

向下取整：

BINARY-SERACH(A, n, target){
    left = 1
    right = n;
    while(left <= right) {
        mid = ⌊(left + right) / 2⌋
        if (A[mid] == target) { 
            return mid; 
        } else if(nums[mid] < target) { 
            left = mid + 1; 
        } else { 
            right = mid - 1; 
        }
    }
    error "not found"
}

向上取整：

BINARY-SERACH(A, n, target){
    left = 1
    right = n;
    while(left <= right) {
        mid = ⌈(left + right) / 2⌉
        if (A[mid] == target) { 
            return mid; 
        } else if(nums[mid] < target) { 
            left = mid + 1; 
        } else { 
            right = mid - 1; 
        }
    }
    error "not found"
}

方法一：构造

A选项二叉树10个结点。

B选项二叉树11个结点。

C选项二叉树9个结点。

D选项二叉树10个结点。

我们尝试构造一棵含10个元素的折半查找判定树，每个结点存储数组元素下标。

设有长度为10的升序序列 A[1:10] ，即满足 a1<a2<a3<a4<a5<a6<a7<a8<a9<a10 。为了方便讨论，考虑下标序列 {1,2,3,4,5,6,7,8,9,10} 。

折半查找规则要统一，要不全部折半向下取整，要不全部折半向上取整。下面分情况讨论。

折半向下取整：

根结点元素下标为⌊(1 + 10) / 2⌋ = 5，下标序列 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}分为{1, 2, 3, 4}, {5}, {6, 7, 8, 9, 10}。对于左子树，根结点元素下标为⌊(1 + 4) / 2⌋ = 2。{1, 2, 3, 4}可以分为{1}, {2}, {3, 4}。对于右子树，根结点元素下标为⌊(6 + 10) / 2⌋ = 8。{6, 7, 8, 9, 10}可以分为{6, 7}, {8}, {9, 10}。递归执行上述过程直到折半查找判定树构造完成。

折半向上取整：

根结点元素下标为⌈(1 + 10) / 2⌉ = 6，下标序列{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}分为{1, 2, 3, 4, 5}, {6}, {7, 8, 9, 10}。对于左子树，根结点元素下标为⌈(1 + 5) / 2⌉ = 3。{1, 2, 3, 4, 5}可以分为{1, 2}, {3}, {4, 5}。对于右子树，根结点元素下标为⌈(7 + 10) / 2⌉ = 9。{7, 8, 9, 10}可以分为{7, 8}, {9}, {10}。递归执行上述过程直到折半查找判定树构造完成。

此折半查找判定树与选项A中的二叉树一致。

本题选A。

方法二：代入选项

考虑升序序列 A[1:n] ，其中 n 为对应二叉搜索树的结点个数，可以在树结点上依次填上相应的元素下标，符合折半查找规则的二叉树树即为所求。

折半查找规则要统一，要不全部折半向下取整，要不全部折半向上取整。

B选项中，观察以元素下标 2 为根结点的子树，二分查找区间为 [1, 2]，⌈(1 + 2) / 2⌉ = 2；观察以元素下标 7 为根结点的子树，二分查找区间为 [7, 8]，⌊(7 + 8) / 2⌋ = 7，错误。

C选项，观察以元素下标 2 为根结点的子树，二分查找区间为 [1, 4]，⌊(1 + 4) / 2⌋ = 2；观察以元素下标 8 为根结点的子树，二分查找区间为 [6, 9]，⌈(6 + 9) / 2⌉ = 8，错误。

D选项，观察以元素下标 7 为根结点的子树，二分查找区间为 [6, 7]，⌈(6 + 7) / 2⌉ = 7；观察以元素下标 5 为根结点的子树，二分查找区间为 [1, 10]，⌊(1 + 10) / 2⌋ = 5，错误。

只有A选项符合折半查找规则，正确。

本题选A。

方法三：确定性

本题考察算法的确定性。

折半查找规则要统一，要不全部折半向下取整，要不全部折半向上取整。也就是只有一个孩子结点的子树孩子结点固定在一侧，可以断言：下面两个命题必然有一个为真。

1. 对于任意一个结点，其左子树结点个数大于或等于其右子树结点个数。
2. 对于任意一个结点，其左子树结点个数小于或等于其右子树结点个数。

命题1对应折半向上取整的情况，命题2对应折半向下取整的情况。

观察最下面一层子树，只有选项A和D符合要求，均满足命题1，继续扩大范围观察，观察根结点所在子树，即整棵树，发现D中出现了右子树结点比左子树结点多的情况，违反命题1，排除。只有A符合要求。

本题选A。