问题
单项选择题
已知一棵二叉树前序序列和中序序列分别为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。