问题 单项选择题

已知某二叉树的中序、层序序列分别为DBAFCE,FDEBCA,则该二叉树的后序序列为()。

A.BCDEAF

B.ABDCEF

C.DBACEF

D.DABECF

答案

参考答案:B

解析:

按照遍历左子树要在遍历右子树之前进行的原则,根据访问根节点位置的不同,可得到二叉树的前序、中序和后序3种遍历方法。

层序遍历是从根节点(第1层)出发,首先访问第1层的树根节点,然后从左到右依次访问第2层上的节点,再次是第三层上的节点,依次类推,自上而下、自左向右逐层访问各层上的节点。对二叉树而言,第n层节点最多为2n-1

由层序序列可得;F是树根节点,D,E是第2层节点;结合中序序列有DBA构成F的左子树,CE构成F的右子树,进一步有C是E的左节点,E无右节点;这样A是第4层节点,据DBA序列有B是D的右节点,A是B的右节点。由此易知后序序列为ABDCEF。

选择题
单项选择题