单选题
下列说法中,正确的是______。
Ⅰ.具有10个叶子结点的二叉树中有9个度为2的结点
Ⅱ.设高度为5的二叉树上只有度为0和度为2的结点,则该二叉树中所包含的结点数至少为9
Ⅲ.一棵完全二叉树上有1001个结点,则可知叶子结点的个数为501个
Ⅳ.高度为h的完全二叉树最少有2
h个结点
- A.仅Ⅰ、Ⅱ
- B.仅Ⅱ、Ⅲ、Ⅳ
- C.仅Ⅰ、Ⅲ、Ⅳ
- D.仅Ⅰ、Ⅱ、Ⅲ
【正确答案】
D
【答案解析】[解析] Ⅰ:二叉树叶子结点的个数比度为2的结点的个数多1,故Ⅰ正确。
Ⅱ:最少结点的情况应该是除根结点层只有1个结点外,其余4层都有2个结点,因此结点总数为2×(5-1)+1=9。如图所示,故Ⅱ正确。
[*]
Ⅲ:由二叉树的性质可知:n0=n2+1,且完全二叉树度为1的结点个数要么为0,要么为1。又因为二叉树的总结点个数n=n0+n1+n2。将n0=n2+1代入,可得n=2n0+n1-1;由于n=1 001,得到2n0=1 002+n1。
①当n1=1时,无解。
②当n1=0时,可解得n0=501
故Ⅲ正确。
Ⅳ:高度为h的完全二叉树中,第1层~第h-1层构成一个高度为h-1的满二叉树,结点个数为2h-1-1。第h层至少有一个结点,所以最少的结点个数=(2h-1-1)+1=2h-1,故Ⅳ错误。