🏷️ 知识点：二叉树构建

已知森林 F 及与之对应的二叉树 T，若 F 的先根遍历序列是 a,b,c,d,e,f，中根遍历序列是 b,a,d,f,e,c，则 T 的后根遍历序列是（ ）。

二叉树的遍历 二叉树构建

A. b,a,d,f,e,c B. b,d,f,e,c,a C. b,f,e,d,c,a D. f,e,d,c,b,a

[tag_link]

正确答案：C

本题考察的是 森林的遍历，森林 F 的先根遍历序列对应其二叉树 T 的先序遍历序列，森林 F 的中根遍历序列对应其二叉树 T 的中序遍历序列。即 T 的先序遍历序列为 a,b,c,d,e,f，中序遍历序列为 b,a,d,f,e,c。根据二叉树 T 的先序序列和中序序列可以唯一确定它的结构，构造过程如下：可以得到二叉树 T 的后序序列为 b,f,e,d,c,a。

某森林 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

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