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

admin2014-10-20  27

问题 已知一棵二叉树先序遍历结果为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。
转载请注明原文地址:https://kaotiyun.com/show/2qvR777K
0

最新回复(0)