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

Question

如题所述

Answer 1

后序：左 右 根
中序：左 根 右

由定义可以知道：
1、后序遍历中最后一个就是树根节点，即C节点
2、在中序遍历中，根结点左边的是左儿子集，右边的是右儿子集，即deab是根节点C的左儿子集合

问题就会转化为：
求后序遍历是dabe，中序遍历是deab的子树，方法同上
因为中序遍历中，C节点右边没有节点了，所以C节点不包含右儿子，否则就会被分为2个子问题

以下是你这道题的详细推理过程：
1、由dabec得出根结点为C，由中序遍历可知:{deab}c，二叉树如下
C
/ \
{deab} {右儿子为空}

2、由dabe得出左儿子集合的根节点为e，由中序可知：{d}e{ab}，二叉树更新后如下
C
/
e
/ \
d {ab}

3、由ab可知，e的右儿子集合的根节点为b，由中序可知{a}b，二叉树更新后如下
C
/
e
/ \
d b
/
a

4、由上图可得，前序遍历为：cedba

Answer 2

此树的先序遍历为：cedba。这是方法：先看后序，最后一个节点为根节点。所以根节点为C。然后发现此树为左树分支。右树为空。然后以此方法逐个查找根节点。即得该树。呵呵，如果不明白此树的生成树图形就来Q我吧：4510553 55。我将图画给你。