题16

题16

题目

一棵有 124 个叶结点的完全二叉树, 最多有 ( ) 个结点.
A. 247
B. 248
C. 249
D. 250

分析

解

B
在非空的二叉树当中,由度为 0 和 2 的结点数的关系 可知 ;
总结点数 ,其最大值为 248 ( 的取值为 1 或 0,当 时结点最多)。
注意,由完全二叉树总结点数的奇偶性可以确定 的值,但不能根据 来确定 的值。
【另解】 ,所以第 8 层没满,前 7 层为完全二叉树,由此可推算第 8 层可能有 120 个叶结点, 第 7 层的最右 4 个为叶结点, 考虑最多的情况, 这 4 个叶结点中的最左边可以有 1 个左孩子 (不改变叶结点数),因此结点总数 。