问题 单项选择题

已知一棵二叉树前序序列和中序序列分别为GFDBHCEA和DFHBGCAE,则该二叉树的后序序列为 (37) ,层次序列为 (38)

A.DBHFEACG

B.GFCDBEHA

C.DHBFAECG

D.DFGBCEHA

答案

参考答案:B

解析:试题37~38

[分析]:
本题考查二叉树的遍历。
已知二叉树的前序序列和中序序列分别为GFDBHCEA和DFHBGCAE,根据前序序列的定义,可知G为根,然后再根据中序序列可知DFHB为G的左子树,CAE为G的右子树。
我们首先看左子树DFHB,其对应的前序序列为FDBH,因此F为根,D为F的左子树,HB为B的右子树。同理,HB对应的前序序列为BH,所以B为根,H为B的左子树。
同理,可以得出右子树CAE的构造。CAE对应的前序序列为CEA,所以C为根, EA为C的右子树。EA对应的前序序列为EA,因此E为根,A为F的左子树。
至此,我们就构造出了这棵二叉树,因此,我们可以知道二叉树的后序序列为 DHBFAECG。层次序列是将树的结点从上到下,从左到右依次写出,即GFCDBEHA。

单项选择题
单项选择题