一棵二叉树的先序序列为ABCDEFG，它的中序序列可能是______。
A. CABDEFG
B. ABCDEFG
C. DACEFBG
D. ADCFEGB
选项D是对的，因为先序序列ABCDEFG和中序序列ADCFEGB能够生成唯一的一棵二叉树，画一下图就知道了（AC选项是画不出图的）。
至于A和C的序列中，C与D作为A的左子树，在先序序列ABCDEFG中C要与BDEFG分开而不是混在其中，D也是如此，所以说AC的序列不可能是这个先序序列的中序序列。
对于B来说，最明显了，每层一个右孩子结点就行了，自己画个图一眼能看出来。
但是我想说的是D也是对的。
当没有右孩子的时候，先序遍历就和中序遍历一样了
lightstar 回复 lightstar： 错了错了，写错了，是只有又孩子的时候
B
用户登录可进行刷题及查看答案
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案