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