已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是? A acbed
答案:1 悬赏:0 手机版
解决时间 2021-12-01 08:53
- 提问者网友：做自己de王妃
- 2021-11-30 23:09
已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是? A acbed
最佳答案
- 五星知识达人网友：轮獄道
- 2021-11-30 23:21
选D。
由后序遍历可知c是根结点，符合条件的只有D。追问但是怎么判断出原来的二叉树是什么样子呢？追答也可以的，步骤如下：
1、由后续遍历可知c是根结点。
2、由中序遍历可知deba在c的左孩子树上。
3、由后序遍历知e是c的左孩子树的根结点。
4、由中序遍历可知d是e的左孩子，ba在e的右孩子树上。
5、由后序遍历，可以得出b是e的右孩子，a是e的左孩子，而第4步中确定了a不在e的左孩子数上，因此，a只能在b上。
6、由中序遍历，可知，a是b的右孩子。
可以得出原二叉树如下图：
追问太感谢你了！谢谢，我会好好努力的
由后序遍历可知c是根结点，符合条件的只有D。追问但是怎么判断出原来的二叉树是什么样子呢？追答也可以的，步骤如下：
1、由后续遍历可知c是根结点。
2、由中序遍历可知deba在c的左孩子树上。
3、由后序遍历知e是c的左孩子树的根结点。
4、由中序遍历可知d是e的左孩子，ba在e的右孩子树上。
5、由后序遍历，可以得出b是e的右孩子，a是e的左孩子，而第4步中确定了a不在e的左孩子数上，因此，a只能在b上。
6、由中序遍历，可知，a是b的右孩子。
可以得出原二叉树如下图：
追问太感谢你了！谢谢，我会好好努力的
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯