单选题
一棵完全二叉树,共有n个结点,那么,其叶结点数共有______个。
A.n/2
B.n
C.(n-1)/2
D.(n+1)/2
A
B
C
D
【正确答案】
D
【答案解析】
此问题可以利用二叉树及完全二叉树的性质来求解。 设i、j、k分别为度为0、1、2的结点数目,则n=i+j+k。 根据二叉树的性质有i=k+1,即k=i-1,代入上式,得n=2i+j-1,即i=(n-j+1)/2。 由于完全二叉树中最多只有一个度为1的结点,同时考虑到i为整数, (1)当j=0时,此时n=i+k=2k+1为奇数,则i=(n+1)/2: (2)当j=1时,此时n=i+k+1=2k+2为偶数,则i=(n+1)/2向下取整。 所以选D。
提交答案
关闭