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

admin2009-09-04 19

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

选项 A、CABDEFG
B、ABCDEFG
C、DACEFBG
D、ADBCFEG

答案B

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

转载请注明原文地址:https://kaotiyun.com/show/puxZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类