题23

题23

题目

Q:【2017 统考真题】下列二叉树中, 可能成为折半查找判定树 (不含外部结点) 的是 ( ).
A.
B.
C.
D.

分析

A:折半查找判定树除了满足左子树的所有节点的值都小于根节点的值，右子树的所有节点的值都大于根节点的值外，还要求是一棵完全二叉树，左子树的元素个数或者与右子树的元素个数相等，或者比右子树少一个。

解

A
对于给定的一个有序查找表, 其对应的折半查找判定树是确定且唯一的。
7.2.2 节描述的折半查找算法中, ,因此若表中初始有 个元素,则 分割后, 左右子树各有 个元素;
若表中初始有 个元素,则 mid 分割后,左子树有 个元素,右子树有 个元素。即左子树的元素个数或者与右子树的元素个数相等,或者比右子树少一个。
若令 mid= (low+high) ,不难理解,左子树的元素个数或者与右子树的元素个数相等, 或者比右子树多一个。
选项 ,树中每个左子树都与右子树的结点个数相等,或者多一个结点, 符合向上取整的规则。
选项 B、C、D, 存在有的左子树比右子树多一个结点, 有的左子树比右子树少一个结点, 不符合折半查找的规则。