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

admin2019-03-15 33

问题知一棵二叉树的先序、中序、后序的部分序列如下，其中有些位置没有给出其值，则原二叉树的中序遍历序列为( )。
先序：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

学硕统考专业

度田事件

论述印度非暴力运动的过程和失败原因。

对《魏玛宪法》的内容和影响叙述不正确的是()。

论述秦汉地方行政制度及其变化。

下列能体现《独立宣言》是“一个伟大的历史文件”的表述是()

第二次工业与第一次工业革命相比较，其新特点是()。①科学和技术真正结合起来②第二次工业革命几乎同时发生在几个先进的资本主义国家③与第一次工业革命交叉进行④使社会第一次分裂为工人阶级和资产阶级

—棵二叉树的后序遍历序列为DABEC，中序遍历序列为DFBAC，则先序遍历序列为()。

UDP的报文头部不包括()。

结核性腹膜炎腹痛的特点是()(2007年)

(2015年第45题)使用正压静脉输液时，可能发生的栓塞是

在海关估价中，成交价格是指买方为购买进口货物，并按有关规定调整后的实付或应付价格，因此，对于以租赁、寄售方式进口的货物而言，成交价格不存在。()

根据CreditRisk+模型，假设某贷款组合由100笔贷款组成，该组合的平均违约率为2％，E=2．72，则该组合发生4笔贷款违约的概率为()。

幼儿主动与外部环境相互作用的最重要的方式是()。

中国妇女发展基金会将委托专业金融机构对中国女足发展基金进行管理和运作，其收益部分用于资助中国女子足球队改善生活和训练条件，开展交流与合作，培养选拔后备力量。下列表述，符合文意的是()。

例如：小船上一河条有河上有一条小船。麦克到12点学习睡觉才

Foryearstheadvicehasbeenclear:Eatingfiveportionsadayoffruitandvegetablesisthekeytoahealthylife.Butfivem

Ifyouweretobeginanewjobtomorrow,youwouldbringwithyousomebasicstrengthsandweaknesses.Successor【67】inyourwor

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

计算机408

学硕统考专业

度田事件

论述印度非暴力运动的过程和失败原因。

对《魏玛宪法》的内容和影响叙述不正确的是()。

论述秦汉地方行政制度及其变化。

下列能体现《独立宣言》是“一个伟大的历史文件”的表述是()

第二次工业与第一次工业革命相比较，其新特点是()。①科学和技术真正结合起来②第二次工业革命几乎同时发生在几个先进的资本主义国家③与第一次工业革命交叉进行④使社会第一次分裂为工人阶级和资产阶级

—棵二叉树的后序遍历序列为DABEC，中序遍历序列为DFBAC，则先序遍历序列为()。

UDP的报文头部不包括()。

结核性腹膜炎腹痛的特点是()(2007年)

(2015年第45题)使用正压静脉输液时，可能发生的栓塞是

在海关估价中，成交价格是指买方为购买进口货物，并按有关规定调整后的实付或应付价格，因此，对于以租赁、寄售方式进口的货物而言，成交价格不存在。()

根据CreditRisk+模型，假设某贷款组合由100笔贷款组成，该组合的平均违约率为2％，E=2．72，则该组合发生4笔贷款违约的概率为()。

幼儿主动与外部环境相互作用的最重要的方式是()。

中国妇女发展基金会将委托专业金融机构对中国女足发展基金进行管理和运作，其收益部分用于资助中国女子足球队改善生活和训练条件，开展交流与合作，培养选拔后备力量。下列表述，符合文意的是()。

例如：小船上一河条有河上有一条小船。麦克到12点学习睡觉才

Foryearstheadvicehasbeenclear:Eatingfiveportionsadayoffruitandvegetablesisthekeytoahealthylife.Butfivem

Ifyouweretobeginanewjobtomorrow,youwouldbringwithyousomebasicstrengthsandweaknesses.Successor【67】inyourwor

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