单选题
高度为7的AVL树最少有______个结点,最多有127结点。
A.12
B.21
C.33
D.54
A
B
C
D
【正确答案】
C
【答案解析】
[解析] AVL树的最少结点数与树的高度h有如下关系式:设N
h
是高度为h的AVL树的最少结点数,则有N
0
=0,N
1
=1,N
h
=N
h-1
+N
h-2
+1(h≥2)。如此可得N
2
=N
1
+N
0
+1=2,N
3
=N
2
+N
1
+1=4,N
4
=N
3
+N
2
+1=7,N
5
=N
4
+N
3
+1=12,N
6
=20,N
7
=33。高度为h的AVL的最多结点数为2
h
-1,为满二叉树情形。当h=7时,有2
7
-1=127。
提交答案
关闭