2. 计算机
  3. 已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是( )。

已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是( )。

admin2013-02-04  29
问题 已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是(    )。
选项 A、acbed
B、decab
C、deabc
D、cedba
答案8
解析 中序遍历的递归算法如下：①遍历左子树；②访问根结点；③遍历右子树。前序遍历的递归算法如下：①访问根结点；②遍历左子树；③遍历右子树。后序遍历的递归算法如下：①遍历左子树；②遍历右子树；③访问根结点。由后序遍历结果dabec可知c是根结点，且无右子树。再由左子树的后序遍历结果dabe可知，e是左子树的根结点，且由左子树的中序遍历结果deba可知，d是左子树的左子树结点，b和a是左子树的右子树结点。再次由后序遍历结果ab可知，a是左子树结点。b是根结点。至此，各结点在树中的位置已完全确定。
转载请注明原文地址:https://kaotiyun.com/show/N5up777K
本试题收录于： 二级Access题库NCRE全国计算机二级分类
0

二级Access

NCRE全国计算机二级

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