🏷️ 知识点：二叉树和森林的转换

某森林 F 对应的二叉树为 T , 若 T 的先序遍历序列是 a, b, d, c, e, g, f , 中序遍历序列是 b, d, a, e, g, c, f , 则 F 中树的棵数是（ ）。

二叉树构建 二叉树和森林的转换

A. 1 B. 2 C. 3 D. 4

[tag_link]

正确答案：C

这题考察的是两点，一是 二叉树构建 ，即根据 先序 和 中序 构建二叉树。二是 森林转二叉树 ，构建出二叉树后即可反向转化得到对应的森林。 森林中树的个数 即 二叉树根结点的右结点个数之和。

下列关于二叉树及森林的叙述中，正确的是？（ ）。

二叉树和森林的转换

A. 完全二叉树不存在度为 1 的结点 B. 任意一个森林可以转换为一棵二叉树。 C. 二叉树的分支结点个数比叶结点个数少 D. 链式树的根中保存的是最先计算的运算符

[tag_link]

正确答案：B

完全二叉树中，度为 1 的结点可能存在。比如一颗完全二叉树只有两个结点，那么根结点的度就是 1。A 选项错误。森林转二叉树 有固定的方法，B 选项正确。

将森林F 转换为对应的二叉树T,F 中叶子的个数等于()。

A.T 中叶结点的个数

B.T 中度为 1 的结点个数

C.T 中左孩子指针为空的结点个数

D.T 中右孩子指针为空的结点个数

[tag_link]

正确答案：C

将 森林转化为二叉树 即相当于用孩子兄弟表示法表示森林。在变化过程中，原森林某结点的第一个孩子结点作为它的左子树，它的兄弟作为它的右子树。那么森林中的叶结点由千没有孩子结点，那么转化为二叉树时，该结点就没有左结点，所以 F 中叶结点的个数就等于 T 中左孩子指针为空的结点个数，选 C。此题还可以通过一 些特例来排除 A、B、D 选项。