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

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

admin2021-08-17  18
问题 已知一棵二叉树的先序、中序、后序的部分序列如下，其中有些位置没有给出其值，则原二叉树的中序遍历序列为(    )。
    先序：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/BX3i777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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