Question

c语言二叉树问题，勿写代码，求详细思考过程

已知二叉树后序遍历序列是CDABE,中序遍历序列是CADEB，问它的前序遍历序列是？
求思考过程啊大神，学c的时候老师根本没详细讲数据结构的内容，课本上也没，求思考过程

Answer 1

后序遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点。（先左后右）

中序遍历：若树不空，则先访问左子树，再访问根，再访问右子树。

从后序遍历：CDABE得出E是最顶根节点。

然后中序遍历：CADEB得出CAD是E的左子树中的，B是E的右子树中的。

再分析后序遍历CDA可以知道A是CD的根，

而中序是CAD得到C是A的左子树，D是A的右子树。（如下图）

最后，先序遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。

于是得到结束： 先序遍历是 EACDB

 

 

 

 

Answer 2

[1]由先序得E是根，由中序得左子树CAD,右子树B
[2]所以左子树先序CDA,中序CAD；右子树先序B,中序B
递归
故最终
E
A B
C D