在某个二叉查找树(即二叉排序树)中进行查找时,效率最差的情形是该二叉查找树是(59) 。A.完全二叉

Question

在某个二叉查找树（即二叉排序树）中进行查找时，效率最差的情形是该二叉查找树是(59) 。

A.完全二叉树

B.平衡二叉树

C.单枝树

D.满二叉树

Answer 1

正确答案：C
本题考查数据结构基础知识。非空二叉查找树中的结点分布特点是左子树中的结点均小于树根，右子树中的结点均大于树根。因此，在二叉查找树中进行查找时，走了一条从树根出发到所找到结点的路径，到达一个空的子树则表明查找失败。根据定义，高度为h的满二叉树中有2h-l个结点，每一层上的结点数都达到最大值。完全二叉树的最高层只要求结点先占据左边的位置。例如，高度为3的满二叉树如下图(a)所示，具有6个结点的完全二叉树如下图(b)所示。在平衡二叉树中，任何一个结点的左子树高度与右子树高度之差的绝对值不大于1。单枝树中给每个结点只有1个子树。例如，具有3个结点的单枝树如下图所示。显然，在结点数确定后，二叉查找树的形态为单枝树时查找效率最差。