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

admin2017-08-31 51

问题已知某二叉树的先序序列为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)

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

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

软考中级

某用户无法访问域名为www．cisco．com的网站，在用户主机上执行tracert命令得到提示如下：根据提示信息，造成这种现象的原因可能是__________。

如果一台CISIOPLX防火墙有如下的配置：PLX(config)#nameifetherent0f1security0PLX(config)#nameifetherent1f2security00PLX(config)#nameif

A．食管B．空肠C．二者均是D．二者均否管壁结构中形成皱襞的是()

肝经湿热型细菌性阴道病的特点是

2010年1月1日，丁公司相关科目的期初余额分别是：“实收资本”500000元，“资本公积”120000元，“盈余公积”90000元，“利润分配——未分配利润”2550000元。2010年有关业务及相关资料如下：(1)某投资者

关于我国信息披露的基本要求的表述，下面选项中正确的是()。

某企业销售商品一批，增值税专用发票上标明的价款为60万元，适用的增值税税率为17%，为购买方代垫运杂费2万元，款项尚未收回。该企业确认的应收账款为（）万元。

五种竞争力分析中，存在的主要结构性障碍包括()。

图书出版社经营的目标体系包括()等。

在BSP方法研究步骤中，下列()是研究数据逻辑相关性的归类工作。

下列叙述中正确的是()。