🏷️ 知识点：森林的概念
某二叉树结点的中序序列为 BDAECF，后序序列为 DBEFCA，则该二叉树对应的森林包括（ ）棵树。
A. 1 B. 2 C. 3 D. 4
[tag_link]
正确答案：C
考查由遍历序列确定二叉树、森林与二叉树的转换。 根据后序序列，A 是二叉树的根结点。 根据中序遍历序列，则二叉树的形态一定如下图左所示。 对于 A 的左子树，由后序序列可知，因为 B 比 D 后被访问，因此，B 必为 D 的父结点，又由中序序列可知，D 是 B 的右儿子。 对于 A 的右子树，同理可确定结点 E、C、F 的关系。 此二叉树的形态如下图右所示。
再根据二叉树与森林的对应关系。 森林中树的棵数即为其对应二叉树（向右上旋转 45° 后）中根结点 A 及其“右兄弟”数。 可知此森林中有 3 棵树，根结点分别为 A、C 和 F。
若森林 F 有 15 条边、25 个结点，则 F 包含树的个数是（ ）。
A. 8 B. 9 C. 10 D. 11
[tag_link]
正确答案：C
解法一：树有一个很重要的性质：在 n 个结点的树中有 n-1 条边，“那么对于每棵树，其结点数比边数多 1”。题中的森林中的结点数比边数多 10（即 25-15=10），显然共有 10 棵树。 解法二：若考生再仔细分析可发现，此题也是考察图的某些方面的性质：生成树和生成森林。此时对于图的生成树有一个重要的性质：若图中顶点数为 n，则它的生成树含有 n-1 条边。对比解法一中树的性质，不难发现两种解法都利用到了“树中结点数比边数多 1”的性质，接下来的分析如解法一。
由 4 棵树组成的森林中，第一、第二、第三和第四棵树中的结点数分别为 30、10、20、5，当把森林转换成二叉树后，对应二叉树中根结点的右子树的左子树的结点数为（ ）。
A. 29 B. 9 C. 25 D. 19
[tag_link]
正确答案：B
将森林转换成二叉树时，采用“左孩子右兄弟”的表示法。
对于由多棵树组成的森林，转换规则为：取第一棵树的根作为二叉树的根，根的左子树由第一棵树中根的子树森林转换而成，根的右子树由剩余树组成的森林转换而成。
给定森林中四棵树的结点数分别为 30、10、20、5。 转换后二叉树的结构如下：
- 二叉树的根对应第一棵树的根。 >
- 根的左子树由第一棵树中除根外的 29 个结点转换而成，结点数为 29。 >
- 根的右子树由第二、三、四棵树（结点数共 10+20+5=35）转换而成。 >
根的右子树本身也是一棵二叉树，其根对应第二棵树的根。 > 该右子树的左子树由第二棵树中除根外的子树森林转换而成，第二棵树有 10 个结点，除根外有 9 个结点，因此该左子树的结点数为 9。 >
故根结点的右子树的左子树的结点数为 9。 >