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

admin2010-02-13  16

问题 假设一棵二叉树的后序遍历序列为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)