单选题 一棵完全二叉树,共有n个结点,那么,其叶结点数共有______个。
  • A.n/2
  • B.n
  • C.(n-1)/2
  • D.(n+1)/2
【正确答案】 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。