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

admin2014-10-20 28

问题已知一棵二叉树先序遍历结果为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://jikaoti.com/ti/849fFFFM

计算机科学与技术

相关试题推荐

随机试题

最新回复(0)