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

admin2014-07-18  31

问题 在含有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-1+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错误。如下图所示:

A在查找30后,指针应该指向左孩子,而不是右孩子;B与A存在同样的问题,因而A、B错误。而C选项的查找路径,如下图所示:
转载请注明原文地址:https://kaotiyun.com/show/9axi777K
0

最新回复(0)