有12个节点的平衡二叉树的最大深度是多少

2013年4月15日 由 Creater 留言 »

有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

广告位

发表评论

你必须 登陆 方可发表评论.