题18

题18

题目

Q:【2020 统考真题】已知森林 及与之对应的二叉树 ,若 的先根遍历序列是 ,后根遍历序列是 ,则 的后序遍历序列是 ( ).
A.
B.
C.
D.

分析

A:树、森林、二叉树之间的遍历关系如下

树	森林	二 叉 树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

根据题目也就是知道了这个森林所对应的二叉树的，先序遍历序列和中序遍历序列，所以可以唯一确定这个二叉树 然后就可以得到他的后序遍历 ### 解 森林 $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$ 。