首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
知一棵二叉树的先序、中序、后序的部分序列如下,其中有些位置没有给出其值,则原二叉树的中序遍历序列为( )。 先序:A_CDEF_H_J 中序:C_EDA_GFI_ 后序:C__BHGJI__
知一棵二叉树的先序、中序、后序的部分序列如下,其中有些位置没有给出其值,则原二叉树的中序遍历序列为( )。 先序:A_CDEF_H_J 中序:C_EDA_GFI_ 后序:C__BHGJI__
admin
2019-03-15
24
问题
知一棵二叉树的先序、中序、后序的部分序列如下,其中有些位置没有给出其值,则原二叉树的中序遍历序列为( )。
先序: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
学硕统考专业
相关试题推荐
在19世纪晚期到20世纪初期时,英法经济发展缓慢下来的共同原因是()。①技术装备相对落后②战败的割地赔款③资本大量输出④资源和劳动力的匮乏
“二战”后世界经济发展变化迅速,这种变化主要表现在()。①国际金融体系和贸易体系的形成②国家垄断资本主义的空前发展③形成以美、苏“冷战”为特征的两极格局④科学技术推动生产力发展更为迅速
下列关于提督学政的说法不正确的是()。
经六朝时期的发展,南方形成了三个农业发达地区即()。
以下是“二战”后美国经济发展的排列组合。其中最正确的一组是()。
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
以数组Data[m+1]作为循环队列SQ的存储空间,front为头指针,rear为队尾指针,则执行出队操作的语句是()。
一个SPOOUNG系统由输入进程I、用户进程P、输出进程O、输入缓冲区、输出缓冲区组成。进程I通过输入缓冲区为进程P输入数据,进程P的处理结果通过输出缓冲区交给进程O输出。进程间数据交换以等长度的数据块为单位,这些数据块均存储在同一个磁盘上,因此,SPOO
某系统有三个进程P1,P2,P3并发工作,其中P1执行过程中需要使用资源S3,S1;P2需要使用资源S1,S2;P3需要使用资源S2,S3。(1)如果进程推进过程中对资源分配不加以限制,会导致什么结果,为什么?(2)如何避免这种后果,列出所有可
随机试题
王国维在__________中,将__________并称“四育”。
男性,7岁,6小时前由货车上跌下,伤后即有呼吸困难,并逐渐加重。入院查体:脉搏130次/分,血压10.7/6.7kPa,呼吸22次/分,颜面发绀,吸气性呼吸困难,颈上胸部有皮下气肿,气管向左移位,右侧呼吸音消失。急救措施是
慢性心功能不全的基本病因有哪些()。
腰痛固定不移,触之僵硬,舌暗,应选取()腰部冷痛重着,俯仰受限,舌淡缸,应选取()
FIDIC合同条件下,因发生了属于业主承担的特殊风险而导致合同被迫终止时,不给承包商补偿的( )。
【背景资料】A公司应邀参加氮制造厂合成压缩工段技改工程投标。招标书说明,以工期安排最短、最合理为中标主要条件,A公司技术部门依据招标书指出的工程内容编制了网络计划图。网络计划附加说明:(1)配管包括机泵本体配管25天,塔器本
俄国文学史上最后一个“多余人”形象是()。
求非齐次线性方程组的通解。
以下不属于C语言位运算符的是()。
收到一封邮件,再把它寄给别人,一般可以用______。
最新回复
(
0
)