问题详情

一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是______。

A、CABDEFG

B、ABCDEFG

C、DACEFBG

D、ADBCFEG

时间：2022-01-04 08:42 关键词：

答案解析

B
解析：由前序遍历序列为ABCDEFG可知，这棵树的根结点为A。先看选项A，如果中序遍历是CABDEFG，显然可以得出结点C是A的左孩子，而BDEFG都在A的右子树上，那么先序遍历时，应该是AC…B…，也就是说C在B的前面，而题设中前序遍历是ABC…。类似地我们可以判断出C、D都不可能。结合选项B的中序遍历序列，我们可以得出此时对应的二叉树如图3-73所示。[*]

相关问题

一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序历结果为（　　）。
若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是( )
设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。
已知二叉树的前序序列为ABDCEFG，中序序列为DBCAFEG，则后序序列为______。
若一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为(38)。