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

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

admin2010-02-13  20
问题 设一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为______。
选项 A、ACBEGFD
B、ABCDEFG
C、ACBEDFG
D、ABCEDFG
答案A
解析 基本思路如下：
   ①确定根结点。在前序遍历中，首先访问根结点，因此可以确定前序序列 DBACFEG中的第一个结点D为二叉树的根结点。
   ②划分左子树和右子树。在中序遍历中，访问根结点的次序为居中，首先访问访问左子树上的结点，最后访问右子树上的结点，可知，在中序序列ABCDEFG中，以根结点D为分界线，子序列ABC在左子树中，子序列EFG在右子树中。如图 8-22所示。
   
   ③确定左子树的结构。对于左子树ABC，位于前序序列最前面的一个结点为子树的根结点，根据前序遍历结果，B为该子树的根结点，中序序列中位于该根结点前面的结点构成左子树上的结点子序列，位于该根结点后面的结点构成右子树上的结点子序列，所以A为该左子树的左结点，C为右结点。现在可确定左子树结构如图8-23所示。
   
   ④确定右子树的结构。同理，可知右子树的结构。
   本二叉树恢复的结果如图8-24所示。
   
   根据后序遍历的原则，该二叉树后序遍历的结果为ACBEGFD。
转载请注明原文地址:https://www.kaotiyun.com/show/tZjZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

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