单选题 已知一棵二叉树的先序、中序、后序的部分序列如下,其中有些位置没有给出其值,则原二叉树的中序遍历序列为______。
先序:A_CDEF_H_J 中序:C_EDA_GFI 后序:C_ _BHGJI_ _
  • A.CBEDAHGFIJ
  • B.CHEDABGFIJ
  • C.CBEDAJGFIH
  • D.CJEDAHGFIB
【正确答案】 A
【答案解析】[解析] 对于一棵二叉树(包括子树),它的遍历序列对应的结构应该是:先序遍历:|根|左子树|右子树|,中序遍历:|左子树|根|右子树|,后序遍历:|左子树|右子树|根|,由题目中给出的先序序列的第一个结点我们找到树的根A,然后在中序序列中找到A,并以A为分界将中序序列划分为|C_ED|A|_GFI_|,所以C_ED为左子树,_GFI_为右子树,再对应到后序遍历序列上,这里左子树结点的个数等于中序遍历序列中左子树结点的个数,因此C_ _B为左子树,HGJI_为右子树,这样把中序序列和后续序列中的左右子树一对比,则C{{U}}B{{/U}}ED为左子树,F{{U}}G{{/U}}H{{U}}I{{/U}}J为右子树。答案选A。