问题
单项选择题
在含有15个结点的平衡二叉树上，查找关键字为28(存在该结点)的结点，则依次比较的关键字有可能是______。
A．30．36
B．38，48，28
C．48，18，38，28
D．60，30，50，40，38，36
答案
参考答案：C
解析： 设ni表示深度为h的平衡二叉树中含有的最少结点数，有n0=0，n1=1，n2=2；
计算的公式为：nh=nh-l+nh-2+1；
n3=n2+n1+1=4；
n4=n3+n2+1=7；
n5=n4+n3+1=12；
n6=n5+n4+1=20＞15。
也就是说，高度为6的平衡二叉树的最少有20个结点，因此15个结点的平衡二叉树的高度为5，而最小叶子结点的层数为3，所以选项D错误。如下图所示：
