问题
单项选择题
假设一棵二叉树的后序遍历序列为DGJHEBIFCA,其中序遍历序列为DBGEHJACIF,则其前序遍历序列为______。
A.ABCDEFGHIJ
B.ABDEGHJFIC
C.ABDEGJHCFI
D.ABDEGHJCFI
答案
参考答案:D
解析:[分析] 由后序遍历序列为DGJHEBIFCA可知A为根结点,从中序遍历序列为DBGEHJACIF可知,根结点A的左子树为DBGEHJ,右子树为CIF,再根据后序遍历可知左子树中B为根结点,右子树中C为根结点,结合左子树DBGEHJ,得到D为B的左结点,GEHJ为B的右子树,以此类推,并按照前序遍历的方法可以得出前序遍历序列为ABDEGHJCFI。