2. 计算机
  3. 若某二叉树的先序遍历序列和中序遍历序列分别为PBECD、BEPCD，则该二叉树的后序遍历序列为(38)。

若某二叉树的先序遍历序列和中序遍历序列分别为PBECD、BEPCD，则该二叉树的后序遍历序列为(38)。

admin2021-01-13  41
问题 若某二叉树的先序遍历序列和中序遍历序列分别为PBECD、BEPCD，则该二叉树的后序遍历序列为(38)。
选项 A、PBCDE
B、DECBP
C、EBDCP
D、EBPDC
答案C
解析 本题考查二叉树的遍历运算特点。
   先序遍历二叉树时，先访问根结点，然后先序遍历根的左子树，最后先序遍历根的右子树。因此，二叉树的先序遍历序列中第一个结点是树的根结点。
   中序遍历二叉树时，首先中序遍历根结点的左子树，然后访问根结点，最后中序遍历根的右子树。因此，若已知二叉树的根结点，则依据中序遍历序列可将根的左、右子树结点区分开。
   综上，首先根据先序序列确定根结点，然后依据中序遍历序列划分左、右子树，反复使用该规则，即可将每个结点的位置确定下来。
   对于本题，首先从先序遍历序列PBECD可知，P为树根，再由中序序列得知，B、 E为左子树上的结点，C、D为右子树上的结点。如下所示。
   
   对P的左子树进行先序遍历的序列为BE，即B是P的左子树的根结点，在以P为根的左子树中序序列中，E在B之后，所以E应在B的右子树上。依此类推，可知P的右子树的树根为C，D为C的右子树上的结点。因此，得到的二叉树如下所示，对该二叉树进行后序遍历得到序列EBDCP。
   
转载请注明原文地址:https://kaotiyun.com/show/POVZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

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