首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
知一棵二叉树的先序、中序、后序的部分序列如下,其中有些位置没有给出其值,则原二叉树的中序遍历序列为( )。 先序:A_CDEF_H_J 中序:C_EDA_GFI_ 后序:C__BHGJI__
知一棵二叉树的先序、中序、后序的部分序列如下,其中有些位置没有给出其值,则原二叉树的中序遍历序列为( )。 先序:A_CDEF_H_J 中序:C_EDA_GFI_ 后序:C__BHGJI__
admin
2019-03-15
60
问题
知一棵二叉树的先序、中序、后序的部分序列如下,其中有些位置没有给出其值,则原二叉树的中序遍历序列为( )。
先序: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
学硕统考专业
相关试题推荐
世界近代史上,世界经济发展经历了两次大的飞跃,即第一次工业革命和第二次工业革命。阅读下面两段材料,回答问题:材料一工业革命的主角——蒸汽机,是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产,主要依靠以人力和经
“英国不想为捷克牺牲一兵一卒,英国同意任何合理的解决办法,只要不用武力。”下列哪一事件体现了这一主张?
在西欧列强海外殖民扩张进程中,各国之间相互争夺海上霸权。18世纪末,英国在争霸中取得胜利的根本原因在于()
下列法律文件中,规定内阁对君主负责的是()。
1940年毛泽东的《新民主主义论》:“而所谓民主主义,现在已不是旧范畴的民主主义,已不是日民主主义,而是新范畴的民主主义,而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是
20世纪30年代,美国推行“中立”的外交政策。对这一政策的正确表达是()。①适应国内外形势,维护自身利益②反映国际形势走向缓和③维护凡尔赛一华盛顿体系④不利于地区冲突的缓和与解决⑤不关心美洲地区以外的事务
关于一战后构筑的凡尔赛体系,说法不正确的是()。
以下()协议完成了从网卡到IP地址的映射。
给定单链表的结点结构typedefstructnode*link;structnode{intitem,linknext;);将两个升序单链表归并为一个升序单链表。
随机试题
卵巢早衰是指
下列哪项最支持右心功能不全
使君子在使用中应注意的是
建设工程施工预付款担保的主要形式是()。
2012年3月1日,A公司和B公司由于买卖关系,A公司签发一张20万元的于2012年5月1日付款的定期付款的甲银行承兑汇票。3月15日,B公司在和C公司购销合同中,将此汇票背书转让给C公司,并在汇票上记载“不得转让”字样。3月28日,C公司在和D公司的买卖
上海证券交易所和深圳证券交易所连续竞价期间的即时行情内容包括()
2007年甲公司委托乙公司加工商品一批(属于应税消费品)。有关经济业务如下:(1)1月5日,发出材料一批,计划成本为400000元,材料成本差异率为2%。(2)2月8日,支付商品加工费20000元,支付应当交纳的消费税43000元。该
寒来暑往,斗转星移。一年中同是在晚上,不同季节看到的星象是不一样的。下列星座属于冬季星空的有()。
在对资本主义工商业进行社会主义改造过程中,高级形式的国家资本主义是()
A、Whentheyarewithababy-sitter.B、Whentheyarewithanotherbaby.C、Whentheyarewithastrangeadult.D、Whentheyarewit
最新回复
(
0
)