2. 从业资格
  3. 若某二叉树的先序遍历序列和中序遍历序列分别为PBECD、BEPCD，则该二叉树的

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

免费题库2022-08-02  75
问题 若某二叉树的先序遍历序列和中序遍历序列分别为PBECD、BEPCD，则该二叉树的后序遍历序列为（）。A.PBCDEB.DECBPC.EBDCPD.EBPDC
选项 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://www.tihaiku.com/congyezige/2428343.html
本试题收录于： 初级程序员题库软件水平考试初中高级分类

初级程序员

软件水平考试初中高级

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