单选题 13.在含有15个结点的平衡二叉树上,查找关键字为28(存在该结点)的结点,则依次比较的关键字有可能是( )。
【正确答案】 C
【答案解析】设Ni表示深度为h的平衡二叉树中含有的最少结点数,有:
N0=0,N1=l,N2=2;
计算的公式为:
Nh=Nh-1+Nh-2+1;
N3=N2+N1+1=4;
N4=N3+N2+l=7;
N5=N4+N3+1=12 ;
N6=N5+N4+1=20>15。
也就是说,高度为6的平衡二叉树最少有20个结点,因此15个结点的平衡二叉树的高度为5,而最小叶子结点的层数为3,所以选项D错误。

选项A在查找30后,指针应该指向左孩子,而不是右孩子;选项B与选项A存在同样的问题,因而选项A、B错误。而选项C的查找路径如下图所示: