• 欢迎浏览“String me = Creater\忠实的资深Linux玩家;”,请文明浏览,理性发言,有侵犯你的权益请邮件我(creater@vip.qq.com).
  • 把任何的失败都当作一次尝试,不要自卑;把所有的成功都想成是一种幸运,不要自傲。
  •    6年前 (2013-04-15)  算法/数据结构 |   6 条评论  92 
    文章评分 0 次,平均分 0.0

    有12个节点的平衡二叉树的最大深度是多少?
    A.4 B.5 C.6 D.3

    平衡二叉树,也即是AVL树,若将二叉树节点的平衡因子BF定义为该节点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有节点的平衡因子只可能为-1,0,1.只要二叉树上有一个节点的平衡因子的绝对值大于1,那么这颗平衡二叉树就失去了平衡。也即是至少要求左子树和右子数高度之差不大于1.另外对于N>2的平衡二叉树,其前N-2层必然是完全二叉树。
    在高度为h的AVL树中,最少节点数:
    S(h) = S(h-1) + S(h-2) +1;
    h=0,S(0)=1;
    h=1,S(1)=2;
    有了这个迭代式就好算了
    S(2) = 4
    S(3) = 7
    S(4) = 12
    S(5) = 20
    S(6) = 33

    如图所示深度为4的AVL树。
    1447764762.9950186

    可以得出答案A

     

    除特别注明外,本站所有文章均为String me = "Creater\忠实的资深Linux玩家";原创,转载请注明出处来自http://unix8.net/home.php/614.html

    关于

    发表评论

    暂无评论

    切换注册

    登录

    忘记密码 ?

    切换登录

    注册

    扫一扫二维码分享