单选题 一个具有967个结点的完全二叉树,其叶子结点个数为______。
  • A.483
  • B.484
  • C.485
  • D.486
【正确答案】 B
【答案解析】[解析] 假设n0为度为0的结点总数(即叶子结点数),n1为度为1的结点总数,n2为度为2的结点总数,由二叉树的性质可知
n=n0+n1+n2 (1)
其中n为完全二叉树的结点总数。又根据二叉树的定义,有
n=n1+2×n2+1 (2)
由公式(1)和(2)可得
n2=n0-1 (3)
把(3)式代入(1)式,可得
n=2n0+n1-1 (4)
根据本题的条件,有967=2n0+n1-1,即968-n1=2n0。现在只需确定n1就能求得n0了。根据完全二叉树的定义,一棵K层的完全二叉树,上面的K-1层为满二叉树,最后一层的结点都靠左边,又因为满二叉树中只有度为0和度为2的结点,没有度为1的结点,这也就意味着在完全二叉树中,只有倒数第二层,才可能有度为1的结点,这就限制了完全二叉树只可能有0个或1个度为1的结点,对于968-n1=2n0,n1显然为0,所以n0=968/2=484。