单选题
一般说来,若深度为k的n个结点的二叉树具有最小路径长度时,第k层(根为第1层)上的结点数为______。
A、
n-2
k-2
+1
B、
n-2
k-1
+1
C、
n-2
k
+n
D、
n-2
k-1
【正确答案】
B
【答案解析】
[解析] 考查完全二叉树。树的路径长度是从根结点到树中每一结点的路径长度之和。对于结点数固定为n,在二叉树每层(除最后一层)上的结点个数都饱和的二叉树的路径长度最短。在结点数目相同的二叉树中,完全二叉树的路径长度最短,最后一层(第k层)上的叶结点个数为n-(2
k-1
-1)=n-2
k-1
+1。
提交答案
关闭