首页 > 试题广场 > 已知某二叉树的后序遍历序列是dabec,中序遍历序列是deb
[单选题]

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

  • acbed
  • decab
  • deabc
  • cedba

7个回答

添加回答
推荐
后序遍历:左右根
中序遍历:左根右
根据题目信息得出两个结论:后序遍历最后一位是c,整颗数的根节点是c;c是根结点,根据提供的中序遍历,它最后一位也是c,说明没有右子树。


前序遍历:根左右。即:c e d b a,图有点草不知道能不能看懂。
编辑于 2019-05-20 14:06:33 回复(0)
选D。
后序是:左子树-->右子树-->根节点
中序是:左子树-->节点-->右子树
前序是:根节点-->左子树-->右子树
根据题目已知的后续遍历得出c为整棵树的根节点。排除A、B、C选项。完整二叉树如下图:



编辑于 2019-05-17 17:21:53 回复(0)
D.
后续遍历是dabec,说明c是根节点。
中序遍历是debac,说明c无右子树。
既然c是根节点,且无右子树,根据后续遍历可得e是c的左子树根节点,再根据中序:说明d和b是e的左右子树的根节点。
还剩下a,综合后续和中序:a是b的右叶子节点。
得到二叉树后,便可以得出前序遍历是:cedba
发表于 2019-05-19 18:57:37 回复(0)
选D
【分析】

根据后序遍历结果可知,C为整颗树的根节点,再由中序遍历结果可知,整棵树的节点都是C的左子树,右子树为空。
只有D符合前序遍历 中-->左-->右 的遍历顺序(以C开头),所以选D了。
发表于 2019-05-17 19:34:51 回复(0)
选D,不过一楼的图画错了,a应该在b的右子节点上。按照一楼的图,中序遍历是deabc,不符合题意。
发表于 2019-05-17 17:15:30 回复(2)
答案:D
解答过程:
后序遍历是LRS,中序遍历是LSR(L代表左节点,R代表右节点,S代表中间节点)
后序遍历序列为dabec可以得出最后一个节点C为根节点,然后由中序遍历序列可知C节点以前的为C的左节点(即dabe),C节点以后的为C的右节点(无)
同理可以得到下一个节点为e,e的左节点为d,e的右节点为ba
依次观察直到重建完这个二叉树
然后可以得到前序队列cedba
发表于 2019-05-17 15:37:01 回复(0)
根据中序遍历与后序遍历一起可推出二叉树层序结构为
从左至右:第一层:c;第二层:e;第三层:d,b;第四层:a
前序遍历为:cedba
发表于 2019-05-17 15:34:58 回复(0)