2. 计算机
  3. 已知某二叉树的先序序列为abcde，它可能的中序序列为( )。

已知某二叉树的先序序列为abcde，它可能的中序序列为( )。

admin2017-08-31  44
问题 已知某二叉树的先序序列为abcde，它可能的中序序列为(    )。
选项 A、bdaec
B、bcade
C、ecadb
D、beacd
答案B
解析 二叉树的先序序列可以分为连续的3个部分：根结点、左子树部分、右子树部分。中序遍历也可以分为3个部分：左子树部分、根结点、右子树部分。题目给出的先序序列为abcde，可知a为根结点。
在A选项中，给出的中序序列bdaec表示bd是左子树部分，ec是右子树部分，这与先序序列abcde矛盾(在先序序列中，bd不在一起，ec也不在一起)，因此，不是可能的中序序列。
    在B选项中，给出的序列bcade表示bc是左子树部分，de是右子树部分，这与先序序列abcde不矛盾，是可能的中序序列。对左子树部分而言，在先序序列中的顺序是bc，说明b是根结点；在中序序列中的顺序也是bc，说明c是b的右孩子。对右子树而言，在先序序列中的顺序是de，说明d是根结点；在中序序列中的顺序也是de，说明e是d的右孩子。因此，B选项符合要求。
    在C选项中，给出的中序序列ecadb表示ec是左子树部分，db是右子树部分，这与先序序列abcde矛盾(在先序序列中，ec不在一起，db也不在一起)，因此不是可能的中序序列。
    在D选项中，给出的中序序列beacd表示be是左子树部分，cd是右子树部分，这与先序序列abcde矛盾(在先序序列中，be不在一起)，因此，不是可能的中序序列。
转载请注明原文地址:https://kaotiyun.com/show/RNRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)