2. 计算机
  3. 若二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则其后序遍历序列为(8)。

若二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则其后序遍历序列为(8)。

admin2010-05-22  32
问题 若二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则其后序遍历序列为(8)。
选项 A、DEBAFC
B、DEFBCA
C、DEBCFA
D、DEBFCA
答案D
解析 本题要求根据二叉树的先序遍历和中序遍历求后序遍历。我们可以根据这棵二叉树的先序和中序遍历画出这棵二叉树，然后再得出其后序遍历结果。
   根据先序和中序来构造二叉树的规则是这样的：
   首先看先序遍历序列ABDECF，先序遍历中第一个访问的结点是A，这说明A是二叉树的根结点(因为先序遍历顺序是：根，左，右)。然后看中序遍历序列DBEAFC，中序中A前面有结点DBE，后面有结点FC。这说明DBE是A的左子树，FC是A的右子树(因为中序遍历顺序是：左，根，右)。
   再回到先序遍历序列中看DBE的排列顺序(此时可以不看其他的结点)，我们发现在先序遍历序列中B排在最前面，所以 B是A的左子树的根结点。
   接下来又回到了中序遍历序列，中序遍历序列中D在B的前面，E在B的后面，所以D是B的左子树，E是B的右子树。
   对于A的右子树，可同样依此规则得出。由此，可构造二叉树，如图4-8所示。
     
   然后对这棵二叉树进行后序遍历，得到DEBFCA。
转载请注明原文地址:https://kaotiyun.com/show/d6TZ777K
本试题收录于： 数据库系统工程师上午基础知识考试题库软考中级分类
0

数据库系统工程师上午基础知识考试

软考中级

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