2. 计算机
  3. 假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为______。

假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为______。

admin2010-02-13  22
问题 假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为______。
选项 A、ABCDEFGHIJ
B、ABDEGHJCFI
C、ABDEGHJFIC
D、ABDEGJHCFI
答案B
解析 这类题目，可以根据所给条件，还原二叉树，然后再进行前序遍历。还原二叉树的要点是首先确定根结点，再确定左子树的组成结点和右子树的组成结点。然后再针对每个左子树和右子树，继续确定其根结点以及左右子树。重点是，根据后序遍历的特点是，最后一个结点必然为根。中序遍历中，根结点的左边，是左子树的结点，右边是右子树的结点。
   分析过程如下：
   ①首先，根据后序遍历为DGJHEBIFCA，说明这棵二叉树的根为A。再根据中序遍历的结果：DBGEHJACIF，说明DBGEHJ在根结点A的左边，为左子树上的结点。CIF在根结点A的右边，是右子树上的结点。如图8-25所示。
   
   ②根据后序遍历结果，DGJHEBIFCA，说明CIF这棵子树上，C是根结点。再根据IF在中序遍历中的位置，可知FI都是其右子树。再根据后序遍历结果，可知， F为根，I是其右结点。如图8-26所示。
  
   ③对于DBGEHJ这棵左子树，根据后序遍历结果可知，B是其根结点。再根据中序遍历结果可知，D是其左子树，GEHJ是其右子树。如图8-27所示。
   ④对于GEHJ这个二叉树，根据后序遍历结果，E为根结点。再根据中序遍历结果，HJ为其右子树。G为其左子树。如图8-28所示。
   ⑤对于HJ，根据后序遍历结果，H是根，再根据中序遍历结果，J是H的右子树。构成二叉树如图8-29所示。
   
   对此二叉树进行前序遍历的结果是：ABDEGHJCFI。选项B为本题正确答案。
转载请注明原文地址:https://kaotiyun.com/show/3ZjZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

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