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

admin2019-03-15 32

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

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

在巴黎和会上，法国要求严厉制裁德国的目的是()。

论述宋代理学的发展。

中华人民共和国恢复在联合国合法席位的时间是()。

公元9～13世纪是西欧封建庄园的兴盛时期，典型的庄园采用()的剥削方式。

永元四年(公元92年)，汉和帝用宦官()掌握的一部分禁军，消灭了窦氏势力。郑众从此参与预政事，并受封为侯，这是宦官用权和封侯的开始。

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

编写判定给定的二叉树是否是二叉排序树的函数。

在一个HDLC帧的数据中，如果出现了000111111011这样的流，请问发送到信道上它将会变成()。

电磁流量计不能测量气体介质的流量。()

8086／8088CPU执行软件中断指令INTn时，其中断类型码的提供者是()

以下关于计划的层次说法正确的是：()。

上颌骨LeFortⅡ型骨折，又称骨折或骨折，骨折线自向两侧横过鼻梁、眶内侧壁、眶底、颧上颌缝，再经上颌骨侧壁至。

墙体节能工程，现场拉拔试验是检验保温板材与基层的()。

对于未成年人的信件，教师可以藏匿或丢弃。()

0，4，3，10，6，7，()

新闻线索

Productionistobe______frombigcitiestothemountainousareasincaseofwar.

TopicTheGreatestInventioninYourEyesForthispart,youareallowed30minutestowriteashortessayentitledTheGreat

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

计算机408

学硕统考专业

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

在巴黎和会上，法国要求严厉制裁德国的目的是()。

论述宋代理学的发展。

中华人民共和国恢复在联合国合法席位的时间是()。

公元9～13世纪是西欧封建庄园的兴盛时期，典型的庄园采用()的剥削方式。

永元四年(公元92年)，汉和帝用宦官()掌握的一部分禁军，消灭了窦氏势力。郑众从此参与预政事，并受封为侯，这是宦官用权和封侯的开始。

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

编写判定给定的二叉树是否是二叉排序树的函数。

在一个HDLC帧的数据中，如果出现了000111111011这样的流，请问发送到信道上它将会变成()。

电磁流量计不能测量气体介质的流量。()

8086／8088CPU执行软件中断指令INTn时，其中断类型码的提供者是()

以下关于计划的层次说法正确的是：()。

上颌骨LeFortⅡ型骨折，又称________骨折或________骨折，骨折线自________向两侧横过鼻梁、眶内侧壁、眶底、颧上颌缝，再经上颌骨侧壁至________。

墙体节能工程，现场拉拔试验是检验保温板材与基层的()。

对于未成年人的信件，教师可以藏匿或丢弃。()

0，4，3，10，6，7，()

新闻线索

Productionistobe______frombigcitiestothemountainousareasincaseofwar.

TopicTheGreatestInventioninYourEyesForthispart,youareallowed30minutestowriteashortessayentitledTheGreat

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

上颌骨LeFortⅡ型骨折，又称骨折或骨折，骨折线自向两侧横过鼻梁、眶内侧壁、眶底、颧上颌缝，再经上颌骨侧壁至。