问题 单项选择题

已知一棵二叉树先序遍历结果为ABDEFG,中序遍历结果为BAEDGF,则后序遍历结果为______。

A.BCDEFA

B.BFDECA

C.BEGFDA

D.BEFGDA

答案

参考答案:C

解析:1>根据前序遍历ABDEFG知,根结点一定是A;根据中序遍历BAEDGF,得:A的左侧全部为左子树结点(B),A的右侧全部为右子树结点(EDGF),于是有:
[*]
因为左子树只有一个结点,故不必再分析,否则将分析左子树。下面分析右子树。
2>对右子树的所有结点来说,其前序遍历是DEFG,因此右子树的根结点是D;根据中序遍历EDGF,得:D的左侧为E结点(构成D的左子树结点集合),D的右侧为G、F结点(构成D的右子树结点集合),于是有:D的左子树只有E,故不必再分析,否则将分析D的左子树。下面直接分析D的右子树。
[*]
3>对D的右子树的所有结点来说,其前序遍历是FG,因此D的右子树的根结点是F;根据中序遍历GF,得:F得左侧为G结点,右侧无结点。即F只有左子树,没有右子树。于是有:
[*]
4>对得到的树进行后序遍历,得到BEGFDA。

多项选择题
单项选择题