首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
知一棵二叉树的先序、中序、后序的部分序列如下,其中有些位置没有给出其值,则原二叉树的中序遍历序列为( )。 先序:A_CDEF_H_J 中序:C_EDA_GFI_ 后序:C__BHGJI__
知一棵二叉树的先序、中序、后序的部分序列如下,其中有些位置没有给出其值,则原二叉树的中序遍历序列为( )。 先序:A_CDEF_H_J 中序:C_EDA_GFI_ 后序:C__BHGJI__
admin
2019-03-15
59
问题
知一棵二叉树的先序、中序、后序的部分序列如下,其中有些位置没有给出其值,则原二叉树的中序遍历序列为( )。
先序:A_CDEF_H_J 中序:C_EDA_GFI_ 后序:C__BHGJI__
选项
A、CBEDAHGFIJ
B、CHEDABGFIJ
C、CBEDAJGFIH
D、CJEDAHGFIB
答案
A
解析
对于一棵二叉树(包括子树),它的遍历序列对应的结构应该是:先序遍历:|根|左子树|右子树|,中序遍历:|左子树|根|右子树|,后序遍历:|左子树|右子树|根|,由题目中给出的先序序列的第一个结点我们找到树的根A,然后在中序序列中找到A,并以A为分界将中序序列划分为|C_ED|A|_GFI_|,所以C_ED为左子树,GFI为右子树,再对应到后序遍历序列上,这里左子树结点的个数等于中序遍历序列中左子树结点的个数,因此C__B为左子树,HGJI_为右子树,这样把中序序列和后续序列中的左右子树一对比,则C
B
ED为左子树,F
G
H
I
J为右子树。答案选A。
总结:根据树的遍历结果来还原二叉树,或者根据其中的两个遍历序列来求第三个遍历序列这是历年考试的热点,考生需要记住的是无论怎样的序列,要想构建二叉树必须有中序序列。这是很显然的,这里说明一下原因:我们知道二叉树的定义是递归的,那么我们在构建二叉树的时候势必也会用到递归这种方法,而这种形式的递归我们把它称之为分治(从中间分开来治理)法,而在三种遍历序列中只有中序遍历的结构才体现了这种思想。
转载请注明原文地址:https://kaotiyun.com/show/ZICi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
典型的西欧封建庄园对农民采用的剥削方式是()。
骑士团是罗马教皇推行反宗教改革的工具,其中在波罗的海南岸发挥重要作用的骑士团是()。
在巴黎和会上,法国要求严厉制裁德国的目的是()。
欧洲历史上第一部系统完备的法典是()。
“钟鸣鼎食”往往用来形容贵族生活。考古发现的青铜乐器“钟”始见于周代遗址,可能存在于()
第二次世界大战后,资本主义经济出现的新特点有()。①美国资本加强了对西欧和日本的渗透②国家开始参与资本主义生产过程③国家成为资本主义私有制的保护者④科技成果更为迅速地转化为生产力
()是清代管理边疆少数民族地区事务的机关,也掌管一部分外交事务。
对斯大林时期形成的高度集中的社会主义经济政治体制的叙述,不确切的是()。
在请求分页存储管理中,若采用FIFO的页面淘汰算法,当分配的页面数增加时,缺页中断的次数()。
随机试题
欧阳修在《五代史伶官传序》中提出王朝兴衰的主要因素是()
男性,22岁,进食后突发上腹痛,撕裂样,迅速波及全腹,3小时后于急诊求治,既往有溃疡病史,腹肌紧张,全腹压痛,肠鸣音弱,WBC10.1×109/L。目前最适宜的处置方式是
当采用匀速进展横道图比较工作实际进度与计划进度时,如果表示实际进度的横道线右端落在检查日期的右侧,则该端点与检查日期的距离表示工作( )。
如果主要分析技术方案状态和参数变化对技术方案投资回收快慢的影响,可选用()作为分析指标。
下列说法正确的是()。
从所给的四个选项中选择最合适的一个填入问号处,使之呈现一定的规律。
你在工作中由于能力比较突出,你的领导经常要你帮他修改一些由其他同事做的报告等材料,因此你同事对你有些不满,你怎么办?
在一个会议中有由1至3的3个会期,有8篇论文K、L、M、N、O、P、R和S将被讨论。每篇论文将被安排入1个会期,会期1和会期2每个将安排3篇论文,会期3安排2篇论文,论文安排入每个会期将遵从下列的条件。(1)K将被安排入比L早的会期。(
如果某事务成功完成执行,则该事务称为【】事务。
Anxietycanresultinstressand________.Yetexpertssaythattheproblemisthatmanypeoplejustconsiderthemasemotionalp
最新回复
(
0
)