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