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