知一棵二叉树的先序、中序、后序的部分序列如下，其中有些位置没有给出其值，则原二叉树的中序遍历序列为( )。先序：A_CDEF_H_J 中序：C_EDA_GFI_ 后序：CBHGJI

admin2019-03-15 38

问题知一棵二叉树的先序、中序、后序的部分序列如下，其中有些位置没有给出其值，则原二叉树的中序遍历序列为( )。
先序：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_为右子树，这样把中序序列和后续序列中的左右子树一对比，则CBED为左子树，FGHIJ为右子树。答案选A。
总结：根据树的遍历结果来还原二叉树，或者根据其中的两个遍历序列来求第三个遍历序列这是历年考试的热点，考生需要记住的是无论怎样的序列，要想构建二叉树必须有中序序列。这是很显然的，这里说明一下原因：我们知道二叉树的定义是递归的，那么我们在构建二叉树的时候势必也会用到递归这种方法，而这种形式的递归我们把它称之为分治（从中间分开来治理）法，而在三种遍历序列中只有中序遍历的结构才体现了这种思想。

转载请注明原文地址:https://kaotiyun.com/show/ZICi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

知一棵二叉树的先序、中序、后序的部分序列如下，其中有些位置没有给出其值，则原二叉树的中序遍历序列为( )。先序：A_CDEF_H_J 中序：C_EDA_GFI_ 后序：CBHGJI

计算机408

学硕统考专业

在19世纪晚期到20世纪初期时，英法经济发展缓慢下来的共同原因是()。①技术装备相对落后②战败的割地赔款③资本大量输出④资源和劳动力的匮乏

中世纪德意志历史的特点是()。

第一次鸦片战争、第二次鸦片战争的时间，分别对应于法国的()时期和()时期。

关于垄断组织的积极作用，不正确的说法是()。

下列关于提督学政的说法不正确的是()。

试编写一个非递归算法，实现求以二叉链表存储的二叉树中q结点的祖先。

一个UDP用户的数据报的数据部分长为8192字节。那么通过以太网来传播该UDP数据报时，最后一个IP分片的数据长度是()。

在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值()。

如图所示，四个力F1、F2、F3和F4同时作用于同一物体上的A、B、C、D四个点(A、B、C、D共面)。已知F1=F3，F2=F4，该力系向D点简化，则合力为()。

齿轮磨损严惩或崩裂，一般均应更换新的齿轮。（）

Siouxnameswerealanguageuntothemselves,ladenwithdescriptive,allusive,orevenmagicalmeaning.ASiouxbabywasnameds

装配式拱桥构件在脱模、移运、堆放、吊装时，混凝土的强度一般不得低于设计强度的(　　)。

根据样本的位置和属性推断整个区域内事物在空间上的变化，就是所谓的空间插值法，其结果是产生()。

风险监测需要监测各种可量化的关键风险指标，以及不可量化的风险因素的变换和发展趋势；同时，需要向内外部不同层级主体报告银行对风险的定性、定量评估结果，以及所采取的风险管理和控制措施的质量与效果。()

开展控制工作的前提是()。

督导员与被督导者及其工作没有没有直接关系和责任，是纯粹的咨询角色。从专业的角度看，被督导者自己承担更多的责任，被督导者根据实务工作的要求，主动寻求帮助和支持更为重要。这种督导类型是()

人力资本投资的支出结构包括()

Thereisa______differenceinmeaningbetweenthewordscomradeandcolleague.

知一棵二叉树的先序、中序、后序的部分序列如下，其中有些位置没有给出其值，则原二叉树的中序遍历序列为( )。 先序：A_CDEF_H_J 中序：C_EDA_GFI_ 后序：C__BHGJI__

计算机408

学硕统考专业

在19世纪晚期到20世纪初期时，英法经济发展缓慢下来的共同原因是()。①技术装备相对落后②战败的割地赔款③资本大量输出④资源和劳动力的匮乏

中世纪德意志历史的特点是()。

第一次鸦片战争、第二次鸦片战争的时间，分别对应于法国的()时期和()时期。

关于垄断组织的积极作用，不正确的说法是()。

下列关于提督学政的说法不正确的是()。

试编写一个非递归算法，实现求以二叉链表存储的二叉树中q结点的祖先。

一个UDP用户的数据报的数据部分长为8192字节。那么通过以太网来传播该UDP数据报时，最后一个IP分片的数据长度是()。

在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值()。

如图所示，四个力F1、F2、F3和F4同时作用于同一物体上的A、B、C、D四个点(A、B、C、D共面)。已知F1=F3，F2=F4，该力系向D点简化，则合力为()。

齿轮磨损严惩或崩裂，一般均应更换新的齿轮。（）

Siouxnameswerealanguageuntothemselves,ladenwithdescriptive,allusive,orevenmagicalmeaning.ASiouxbabywasnameds

装配式拱桥构件在脱模、移运、堆放、吊装时，混凝土的强度一般不得低于设计强度的( )。

根据样本的位置和属性推断整个区域内事物在空间上的变化，就是所谓的空间插值法，其结果是产生()。

风险监测需要监测各种可量化的关键风险指标，以及不可量化的风险因素的变换和发展趋势；同时，需要向内外部不同层级主体报告银行对风险的定性、定量评估结果，以及所采取的风险管理和控制措施的质量与效果。()

开展控制工作的前提是()。

督导员与被督导者及其工作没有没有直接关系和责任，是纯粹的咨询角色。从专业的角度看，被督导者自己承担更多的责任，被督导者根据实务工作的要求，主动寻求帮助和支持更为重要。这种督导类型是()

人力资本投资的支出结构包括()

Thereisa______differenceinmeaningbetweenthewordscomradeandcolleague.

知一棵二叉树的先序、中序、后序的部分序列如下，其中有些位置没有给出其值，则原二叉树的中序遍历序列为( )。先序：A_CDEF_H_J 中序：C_EDA_GFI_ 后序：CBHGJI

装配式拱桥构件在脱模、移运、堆放、吊装时，混凝土的强度一般不得低于设计强度的(　　)。