首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
知一棵二叉树的先序、中序、后序的部分序列如下,其中有些位置没有给出其值,则原二叉树的中序遍历序列为( )。 先序:A_CDEF_H_J 中序:C_EDA_GFI_ 后序:C__BHGJI__
知一棵二叉树的先序、中序、后序的部分序列如下,其中有些位置没有给出其值,则原二叉树的中序遍历序列为( )。 先序:A_CDEF_H_J 中序:C_EDA_GFI_ 后序:C__BHGJI__
admin
2019-03-15
66
问题
知一棵二叉树的先序、中序、后序的部分序列如下,其中有些位置没有给出其值,则原二叉树的中序遍历序列为( )。
先序: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
学硕统考专业
相关试题推荐
印加人记载事物使用的方法是()。
现存迈锡尼线形文字B的材料绝大多数叙述的是迈锡尼的()
战国初期,上党地区在下列哪一个国家的控制范围之内?()
论述秦汉地方行政制度及其变化。
下列选项中,不属于“文革”中对“左”倾错误进行纠正的是()
最早以立法的形式巩固大化改新成果的法令是()。
最早发明玻璃制造技术的地区是()。
下列内容,与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张,从经济上瓜分世界
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
以数组Data[m+1]作为循环队列SQ的存储空间,front为头指针,rear为队尾指针,则执行出队操作的语句是()。
随机试题
患者,男性,88岁,戴用全口义齿2周后复诊。自诉义齿易松动。询问病史时,最重要的是应了解患者
“运输方式”栏应填()。
燃气轮机与柴油机相比主要缺点是()。
私募基金的合格投资者是指具备相应风险识别能力和风险承担能力,投资于单只私募基金的金额不低于()万元且符合相关标准的单位和个人。
制定转移价格的目的包括()。
20世纪60年代初,美国贝尔实验室编写了一个名为“磁芯大战“的游戏,游戏中通过复制自身来摆脱对方的控制,这就是()的第一个雏形。
2017年1月26日17时许,某县何坝镇村民林某为小孩过满月,邀请同村罗某、李某等十余人在家聚会。21时许,罗某、李某因相互劝酒发生口角后,罗某打了李某背部一拳,致李某滑倒在地扭伤脚踝。随后,李某拨打110报警。民警在初步了解现场情况后,按规定开展调查
设矩阵A与B相似,且求可逆矩阵P,使P-1AP=B.
Therearethreemaingroupsofoils:animal,vegetableandmineral.Greatnumbersofanimaloilcomefromwhales,thoseenormous
Businessandgovernmentleadersalsoconsidertheinflationratetobeanimportantgeneralindicator.Inflationisaperiodof
最新回复
(
0
)