2. 专升本
  3. 已知一棵二叉树先序遍历结果为ABDEFG，中序遍历结果为BAEDGF，则后序遍历结果为( )。

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

admin2014-10-20  40
问题 已知一棵二叉树先序遍历结果为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://www.kaotiyun.com/show/2qvR777K
本试题收录于： 计算机科学与技术题库普高专升本分类
0

计算机科学与技术

普高专升本

相关试题推荐
随机试题
最新回复(0)