408 每日一题 Day6#

将包含 $22$ 个节点的森林转换为二叉树$T$。对$T$进行中序遍历，将各结点从 $1$ 开始依次编号。已知T的根结点编号为 $17$，下列说法正确的是（ ）。
I. 二叉树$T$的高度至少为 $5$
II. 森林中最多有 $6$ 棵树
III. 编号为 $16$ 的结点一定是叶结点
IV. 编号为 $18$ 的结点一定没有左孩子

A. I、IV
B. I、III
C. II、IV
D. II、III

正确答案：C#

解析：
根结点编号为 $17$，则左子树结点数为 $16$，右子树结点数为 $5$。

I：左子树有16个节点，$2^4-1 < 16 < 2^5-1$，因此左子树的最小高度为5，该二叉树最小高度为$6$
II：由于右子树节点数为5，则最多有$1+5=6$颗树
III：可能存在左孩子，不一定为叶节点
IV：如果存在左孩子，则编号为$17$的节点在编号为$18$的节点的左子树，与题目条件相矛盾，因此编号为$18$的节点没有左孩子

综上，正确选项为 II、IV，答案为 $C$。