单选题
在含有15个结点的平衡二叉树上，查找关键字为28(存在该结点)的结点，则依次比较的关键字有可能是( )。
【正确答案】
C
【答案解析】解析：设N
i
表示深度为h的平衡二叉树中含有的最少结点数，有： N
0
=0，N
1
=1，N
2
=2； 计算的公式为： N
h
=N
h-1
+N
h-2
+1； N
3
=N
2
+N
1
+1=4； N
4
=N
3
+N
2
+1=7； N
5
=N
4
+N
3
+1=12； N
6
=N
5
+N
4
+1=20>15。 也就是说，高度为6的平衡二叉树最少有20个结点，因此15个结点的平衡二叉树的高度为5，而最小叶子结点的层数为3，所以选项D错误。
选项A在查找30后，指针应该指向左孩子，而不是右孩子；选项B与选项A存在同样的问题，因而选项A、B错误。而选项C的查找路径如下图所示：
选项A在查找30后，指针应该指向左孩子，而不是右孩子；选项B与选项A存在同样的问题，因而选项A、B错误。而选项C的查找路径如下图所示：