首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
知一棵二叉树的先序、中序、后序的部分序列如下,其中有些位置没有给出其值,则原二叉树的中序遍历序列为( )。 先序:A_CDEF_H_J 中序:C_EDA_GFI_ 后序:C__BHGJI__
知一棵二叉树的先序、中序、后序的部分序列如下,其中有些位置没有给出其值,则原二叉树的中序遍历序列为( )。 先序:A_CDEF_H_J 中序:C_EDA_GFI_ 后序:C__BHGJI__
admin
2019-03-15
72
问题
知一棵二叉树的先序、中序、后序的部分序列如下,其中有些位置没有给出其值,则原二叉树的中序遍历序列为( )。
先序: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
学硕统考专业
相关试题推荐
美国首次提出争夺世界霸权的纲领性文件是()。
论述印度非暴力运动的过程和失败原因。
下列说法中,全部符合历史事实的是()。①阿拉伯阿拔斯王朝的首都是麦地那②穆罕默德死后,他的继承人改称为哈里发,第三任哈里发奥斯曼时期,部分下层莫斯林组建了军事民主派,称为哈瓦立及派③阿拉伯人灭亡了具有1200年历史的波斯帝国的战役是雅穆克
我国发明生铁冶炼技术是在()。
阅读下面史料,回答问题:材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下:合众国525000吨;英帝国525000吨;法国175000吨;意大利175000吨;日本315000吨。
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段,种类多,交换规模大,交换方式多。试回答问题:下列关于隋唐钱币的表述,不正确的是()
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
高度为4的4阶B树最多可容纳()个关键字(根是第1层)。
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址?(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构连入网络并使用所分配的地址对TC
随机试题
政策问题一般都能顺利地进入正式议程的模型是()
禁婚亲
风险应对计划制定过程的依据不包括()
金属与石材幕墙工程采用的密封胶应掌握的原则有()。
蒸汽状态污染物,指在常温常压下易挥发的物质,以蒸汽状态进入大气,下列属于蒸汽状态污染物的是( )。
当给定利率及终值时,取得终值的时间越长,该终值的现值就越低。( )
银行从业操守和法律的区别有()。
(2012年)关于市场细分的说法,错误的是()。
A、 B、 C、 D、 B每行图形中分割空间数递减,小图形种类及数量轮换变化。
工作中你难以和同事、上司相处,你该怎么办?
最新回复
(
0
)