题1

题1

题目

Q:下列关于树的说法中, 正确的是 ( ).
I. 对于有 个结点的二叉树,其高度为
II. 完全二叉树中, 若一个结点没有左孩子, 则它必是叶结点
III. 高度为 的完全二又树对应的森林所含的树的个数一定是
IV. 一棵树中的叶子数一定等于与其对应的二叉树的叶子数
A. I 和 III
B. IV
C. I 和 II
D. II

分析

A:二叉树也有很多种，得看是哪种二叉树
一个有 n 个结点的满二叉树的高度为 log₂(n+1)。
完全二叉树中最多存在一个度为 1 的结点且只有左孩子

解

D
若 个结点的二叉树是一棵单支树,则其高度为 。
完全二叉树中最多存在一个度为 1 的结点且只有左孩子, 若不存在左孩子, 则一定也不存在右孩子, 因此必是叶结点, 选项 II 正确。
只有满二叉树才具有性质 III, 如下图所示。

(a) 满二叉树转化为对应的森林

(b) 非满二叉树转化为对应的森林
在树转换为二叉树时, 若有几个叶结点具有共同的双亲, 则转换成二叉树后只有一个叶结点 (最右边的叶结点), 如下图所示, 选项 IV 错误。
注意, 若树中的任意两个叶结点都不存在相同的双亲, 则树中的叶子数才有可能与其对应的二叉树中的叶子数相等。