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

admin2019-03-15 67

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

下列关于克里斯提尼改革的叙述不正确的是()。

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

欧洲历史上第一部系统完备的法典是（）。

下列关于基督教的思想来源的叙述，不正确的是()。

最早以立法形式巩固大化改新成果的法令是()。

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为m。试分别计算m=3和m=4时，FIFO和LRU两种替换算法的缺页(页故障)数，并给出：结果说明了什么?

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

下列几种排序方法中，要求内存量最大的是()。

充分反映当代中医药面貌和中西医结合状况的大型中医工具书是()。

我国目前最常见的缩窄型心包炎的病因是()。

国际多式联运费用中的经营管理费包括()。

(2008年考试真题)国际债券在国际市场上发行，其计价货币往往是国际通用货币，一般不用()表示。

房产税的征税对象是房屋，由于房屋属于不动产，所以与房屋不可分割的各种附属设备也应作为房屋一并征税。其中“各种附属设备”包括独立于房屋之外的建筑物，如水塔、烟囱等。()

下列有关实质性程序的说法中，正确的是()。

在计算机系统中，不同的应用程序之间可通过OLE技术共享数据。若源数据发生变化后，目标数据不随之变化，则这种共享称之为________。

北府兵

YouwillhearfivedifferentpeopletalkingaboutaposterbyAndrewClarkontheDiscuztheyhavejustloggedin.Foreach

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

计算机408

学硕统考专业

下列关于克里斯提尼改革的叙述不正确的是()。

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

欧洲历史上第一部系统完备的法典是（）。

下列关于基督教的思想来源的叙述，不正确的是()。

最早以立法形式巩固大化改新成果的法令是()。

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为m。试分别计算m=3和m=4时，FIFO和LRU两种替换算法的缺页(页故障)数，并给出：结果说明了什么?

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

下列几种排序方法中，要求内存量最大的是()。

充分反映当代中医药面貌和中西医结合状况的大型中医工具书是()。

我国目前最常见的缩窄型心包炎的病因是()。

国际多式联运费用中的经营管理费包括()。

(2008年考试真题)国际债券在国际市场上发行，其计价货币往往是国际通用货币，一般不用()表示。

房产税的征税对象是房屋，由于房屋属于不动产，所以与房屋不可分割的各种附属设备也应作为房屋一并征税。其中“各种附属设备”包括独立于房屋之外的建筑物，如水塔、烟囱等。()

下列有关实质性程序的说法中，正确的是()。

在计算机系统中，不同的应用程序之间可通过OLE技术共享数据。若源数据发生变化后，目标数据不随之变化，则这种共享称之为________。

北府兵

YouwillhearfivedifferentpeopletalkingaboutaposterbyAndrewClarkontheDiscuztheyhavejustloggedin.Foreach

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