首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
知一棵二叉树的先序、中序、后序的部分序列如下,其中有些位置没有给出其值,则原二叉树的中序遍历序列为( )。 先序:A_CDEF_H_J 中序:C_EDA_GFI_ 后序:C__BHGJI__
知一棵二叉树的先序、中序、后序的部分序列如下,其中有些位置没有给出其值,则原二叉树的中序遍历序列为( )。 先序:A_CDEF_H_J 中序:C_EDA_GFI_ 后序:C__BHGJI__
admin
2019-03-15
30
问题
知一棵二叉树的先序、中序、后序的部分序列如下,其中有些位置没有给出其值,则原二叉树的中序遍历序列为( )。
先序: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
学硕统考专业
相关试题推荐
简述西欧专制制度的特点。
度田事件
试述“轴心时代”(公元前8世纪至前3世纪)中国、印度、希腊三大古典文化系统之异同。
试分析第二次工业革命的特点及其影响。
日本关东军认为()事件是军事干涉东北的最好借口。日本驻沈阳总领事林久治郎向辽宁省政府提出正式抗议。
战时共产主义政策中对后来的工农联盟最能构成威胁的是()。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
就绪队列中有n个进程等待使用一个CPU,那么,如果采用不同的调用算法,就有()种调度顺序。
如果互联的局域网高层分别采用TCP/IP协议与SPX/IPX协议,那么我们可以选择的多个网络互联设备应该是()。
假定在一个处理机上执行的操作如下:作业估计服务时间片优先数A103B11C23D14E52这些
随机试题
为保证焊透,同样厚度的T形接头应比对接接头选用直径较细的焊条。
患者男性,55岁,寒战高热(39.6℃)1d,咳嗽伴左胸痛,咳大量砖红色胶冻样痰,查体:轻度发绀,血压80/50mmHg,左肺叩诊浊音,呼吸音减低,X线胸片示左肺呈多发性蜂窝状阴影,最可能的诊断为
2型糖尿病四种口服药物有磺脲类、__________、葡萄糖苷酶抑制剂类、噻唑烷二酮类。
一天晚上,甲去电影院看电影。电影开始放映后,坐在甲后一排的乙、丙二人不停地说笑、打闹。甲按捺不住,起身回头指责二人。三人发生争吵,乙、丙二人对甲大打出手。甲情急中掏出随身携带的水果刀往前乱刺,结果刺中坐在乙旁边的观众丁,致丁重伤。甲的行为属于( )。
毛泽东思想的精髓是()。
根据以下资料回答下列问题。经国家统计局核准,2006年某省生产总值641.05亿元,比上年增长12.2%;人均生产总值11753元,比上年增长11.3%。在产业结构调整中,全年第一产业完成产值69.60亿元,比上年增长3.5%;第二产业完成增加值334.
ReadthestoryinChinesebelow,andthenwriteacompositionofnolessthan150wordsunderthetitleof"TheGoalofLife".Y
我国采取单一制国家结构形式的主要原因是()。
结合材料回答问题:习近平同志在主持中央政治局第三十七次集体学习时指出:“改革开放以来,我们深刻总结我国社会主义法治建设的成功经验和深刻教训,把依法治国确定为党领导人民治理国家的基本方略,把依法执政确定为党治国理政的基本方式,走出了一条中国特色社会主义法治
在窗体上画1名为Command1的命令按钮和1名Text1的文本框,再编写如下程序:DimssAsStringPrivateSubCommand1_Click()PrivateSubT
最新回复
(
0
)