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

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

admin2019-03-15  49
问题 知一棵二叉树的先序、中序、后序的部分序列如下，其中有些位置没有给出其值，则原二叉树的中序遍历序列为(    )。
先序：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题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)