2. 计算机
  3. 设一棵二叉树的中序遍历结果为ABCDEFG，前序遍历结果为DBACFEG，则后序遍历结果为______。

设一棵二叉树的中序遍历结果为ABCDEFG，前序遍历结果为DBACFEG，则后序遍历结果为______。

admin2010-12-16  61
问题 设一棵二叉树的中序遍历结果为ABCDEFG，前序遍历结果为DBACFEG，则后序遍历结果为______。
选项
答案ACBEGFD
解析 由于在前序遍历中首先访问根结点，因此，前序序列中的第一个结点为二叉树的根结点，即D为二叉树的根结点。又由于在中序遍历中访问根结点的次序为居中，而访问左子树上的结点为居先，访问右子树上的结点为最后，因此，在中序序列中，以根结点(D)为分界线，前面的子序列(ABC)一定在左子树中，后面的子序列(EFG)一定在右子树中。同样的道理，对于已经划分出的每一个子序列的所有结点中，位于前序序列最前面的一个结点为子树的根结点，而在中序序列中位于该根结点前面的结点构成左子树上的结点子序列，位于该根结点后面的结点构成右子树上的结点子序列。这个处理过程直到所有子序列为空为止。
   根据上述道理，该二叉树恢复的过程如下图所示：
  
   根据后序遍历的方法，对该二叉树后序遍历的结果为ACBEGFD。
转载请注明原文地址:https://kaotiyun.com/show/SLVp777K
本试题收录于： 二级C题库NCRE全国计算机二级分类
0

二级C

NCRE全国计算机二级

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