2. 计算机
  3. 已知某二叉树的层序、中序序列分别为FDEBCA、DBAFCE，则该二叉树的后序序列为(57)。

已知某二叉树的层序、中序序列分别为FDEBCA、DBAFCE，则该二叉树的后序序列为(57)。

admin2010-01-23  7
问题 已知某二叉树的层序、中序序列分别为FDEBCA、DBAFCE，则该二叉树的后序序列为(57)。
选项 A、ABDCEF
B、BCDEAF
C、DABECF
D、DBACEF
答案A
解析 遍历二叉树是按某种搜索策略巡访二叉树中的每一个节点，使得每个节点均被访问一次，而且仅被访问一次。二叉树可以递归定义成由3个部分组成，即根节点(记为D)、左子树(记为L)和右子树(记为R)。只要按某种次序遍历这三部分，就可遍历整个二叉树。
   若限定左子树的遍历要在右子树之前遍历，那么根据访问根节点的位置的不同可有3种方法：前序遍历、中序遍历和后序遍历，分别简记为DLR、LDR和LRD。
   层序遍历二叉树的操作定义为：从树的根节点出发，首先访问第1层的树根节点，然后从左到右依次访问第二层上的节点，其次是第三层上的节点，依次类推，自上而下、自左至右逐层访问树中各层上的节点。
   根据以上遍历方法的特点，先序、后序和层序序列用于确定树根节点，在此基础上，根据中序序列划分根的左右子树，即可逐步构造出对应的二叉树。
   对于本试题，首先根据层序序列的第一个节点为根，即F为根节点，然后根据中序序列划分左、右子树，就分别得到左、右子树的中序序列分别为DBA和 CE，因此得知根的左右子树都不为空，也就是说层序序列中的D、E分别是F的左子节点和右子节点。由于中序序列中C在E之前，因此C为E的左子树根，而在F的左子树D上，B、A在D之后，即说明D的左子树为空，B、A为其右子树的节点且B、A两节点形成父子节点关系。在层序序列中B在A之前，因此B为A的父节点，在中序序列中B在A之前，因此A是B的右子节点。因此该二叉树如图2-16所示。
   
   图2-16二叉树的后序序列为ABDCEF。
转载请注明原文地址:https://kaotiyun.com/show/OYxZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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