单选题
具有5层结点的平衡二叉树至少有______个结点。若设树根结点在第1层，则深度最小的叶结点应在第______层。
【正确答案】
B
【答案解析】
【正确答案】
C
【答案解析】[解析] 若设高度为h的平衡二叉树的最少结点数为N
h
，则有：
N 0 =0，N 1 =1，N h =N h-1 +N h-2 +1(h>1)
逐项推导：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。
深度最小的叶结点在第3层。计算平衡二叉树深度最小的叶结点所在层次的方法与推导高度为h的平衡二叉树的最少结点个数的过程类似。如下图所示，若设高度为h的平衡二叉树的深度最小的叶结点所在层次为L h ，则有：L 1 =1，L 2 =2，L h =min{L h-1 ，L h-2 }+1=L h-2 +1，h＞2
因此
N 0 =0，N 1 =1，N h =N h-1 +N h-2 +1(h>1)
逐项推导：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。
深度最小的叶结点在第3层。计算平衡二叉树深度最小的叶结点所在层次的方法与推导高度为h的平衡二叉树的最少结点个数的过程类似。如下图所示，若设高度为h的平衡二叉树的深度最小的叶结点所在层次为L h ，则有：L 1 =1，L 2 =2，L h =min{L h-1 ，L h-2 }+1=L h-2 +1，h＞2
因此