2. 从业资格
  3. 已知某二叉树的先序遍历序列为ABCD，中序遍历序列为BADC，则该二叉树的后序遍

已知某二叉树的先序遍历序列为ABCD，中序遍历序列为BADC，则该二叉树的后序遍

考试题库2022-08-02  41
问题 已知某二叉树的先序遍历序列为ABCD，中序遍历序列为BADC，则该二叉树的后序遍历序列为（  ）。A.BDCAB.CDBAC.DBCAD.BCDA
选项 A.BDCA
B.CDBA
C.DBCA
D.BCDA
答案 A
解析 本题考查数据结构基础知识。    二叉树的先序遍历定义为：访问根结点，先序遍历根的左子树，先序遍历根的右子树。    二叉树的中序遍历定义为：中序遍历根的左子树，访问根结点，中序遍历根的右子树。    显然，先序遍历序列的第一个结点就是二叉树的根结点，而在中序遍历序列中，根结点的左边为左子树上的结点，右边为右子树上的结点。因此，首先由先序遍历序列确定根结点，然后在中序遍历序列中找到根结点，据此就可以将左子树和右子树的结点区分开。对于左、右子树同样处理，就可以得到对应的二叉树。    本题中的二叉树如下图所示，其后序遍历序列为BDCA。
转载请注明原文地址:https://tihaiku.com/congyezige/2427535.html
本试题收录于： 初级程序员题库软件水平考试初中高级分类

初级程序员

软件水平考试初中高级

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