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

Question

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

A．BCDEAF

B．ABDCEF

C．DBACEF

D．DABECF

Answer 1

正确答案：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。