问题详情

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


A、ABCDEFGHIJ

B、ABDEGHJCFI

C、ABDEGHJFIC

D、ABDEGJHCFI

时间:2022-01-03 13:23 关键词:

答案解析

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为本题正确答案。