题目

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

错因

A

没意识到题问的是森林棵数，把整棵 T 当成 1 棵。看到给的是"一棵二叉树"就以为森林只对应一棵树。其实森林转二叉树（孩子-兄弟表示法）后，根的右链上有几个结点，森林就有几棵树——必须先把 T 重建出来再数右链。

B

右链结点数错算成 2。先把 T 重建出来后，根 a 的右链是 a → c → f，共 3 个结点。选 B 的人通常只数到 a → c 就停了，把最后那个右孩子 f 漏掉。漏掉的原因往往是误以为"右链只算到根的直接右孩子"，但其实整条右链上的所有结点都各对应森林里的一棵树。

D

把右子树里的左孩子 e 也算进右链。重建 T 时，c 的左孩子是 e、右孩子是 f。e 是 c 的左孩子，不属于根 a 的右链；只有 c 和 c 的右孩子 f 才在右链上。选 D 的人没把"左孩子-右孩子"区分开，把 c 子树里的所有结点都当成右链结点算了。

总解析

思路：森林 F = {T₁, T₂, …, Tₖ} 转换为二叉树 T 的规则是孩子-兄弟表示法：

• T₁ 的根作为 T 的根
• T₁ 中"森林转二叉树"的结果作为 T 根的左子树
• {T₂, …, Tₖ} 转成的二叉树作为 T 根的右子树

由此推出关键结论：森林棵数 = 二叉树根的右链长度（根本身 + 沿右孩子能到达的所有结点数）。所以解题分两步：① 由先序+中序重建 T；② 数 T 根的右链结点数。

第一步：由先序 + 中序重建二叉树 T。

先序 = a, b, d, c, e, g, f，中序 = b, d, a, e, g, c, f。

• 先序首字 a 是根。中序 a 左侧 [b, d] 是左子树中序，右侧 [e, g, c, f] 是右子树中序。
• 左子树（先序剩 b, d，中序 b, d）：根 b；中序 b 左空、右是 d；故 b 无左孩子、右孩子是 d。
• 右子树（先序剩 c, e, g, f，中序 e, g, c, f）：根 c；中序 c 左侧 [e, g] 是左子树、右侧 [f] 是右子树。
  • c 的左子树（先序 e, g，中序 e, g）：根 e，无左孩子，右孩子 g。
  • c 的右子树：单结点 f。

整棵 T 的结构：

第二步：数 T 根 a 的右链。

从 a 出发沿 right 指针走：

a ──right──► c ──right──► f ──right──► (空)

右链结点：a, c, f，共 3 个。

需要分清"右链"和"右子树"：右子树是 c 及其下属（含 e、g）；右链只算 a → c → f 这条由 right 指针串成的链路，不进入子树内部。

第三步：把右链对应回森林。

按转换规则倒推：

• a 是森林第 1 棵树 T₁ 的根。a 的左子树（b 这一支）是 T₁ 的子结构。
• a 的右孩子 c 是森林第 2 棵树 T₂ 的根。c 的左子树（e、g）是 T₂ 的子结构。
• c 的右孩子 f 是森林第 3 棵树 T₃ 的根。

森林共 3 棵树。

最终答案是 C（3）。