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

admin2008-01-15  37

问题 已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA,则该二叉树的后序序列为(38)。

选项 A、BCDEAF
B、ABDCEF
C、DBACEF
D、DABECF

答案B

解析 遍历二叉树是按某种搜索策略巡访二叉树中的每一个结点,使得每个结点均被访问一次,而且仅被访问一次。二叉树可以递归定义成由三个部分组成,即根结点(记为D)、左子树(记为L)和右子树(记为R)。只要按某种次序遍历这三部分,便是遍历了整个二叉树。若限定左子树的遍历要在右子树之前遍历,那么根据访问根结点的位置的不同可有三种方法:前序遍历、中序遍历和后序遍历,分别简记为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的右子结点。因此该二叉树如下图所示。
转载请注明原文地址:https://kaotiyun.com/show/AbxZ777K
0

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