在含有15个结点的平衡二叉树上，查找关键字为28(存在该结点)的结点，则依次比较的关键字有可能是( )。

admin2014-07-18 42

问题在含有15个结点的平衡二叉树上，查找关键字为28(存在该结点)的结点，则依次比较的关键字有可能是( )。

选项 A、30，36
B、38，48，28
C、48，18，38，28
D、60，30，50，40，38，36

答案C

解析设n_i表示深度为h的平衡二叉树中含有的最少结点数，有n₀=0，n₁=1，n₂=2；
计算的公式为：n_h=n_h-1+n_h-2+1；
n₃=n₂+n₁+1=4；
n₄=n₃+n₂+1=7；
n₅=n₄+n₃+1=12；
n₆=n₅+n₄+1=20＞15。
也就是说，高度为6的平衡二叉树的最少有20个结点，因此15个结点的平衡二叉树的高度为5，而最小叶子结点的层数为3，所以选项D错误。如下图所示：