已知后序遍历是dabec，中序遍历是debac，它的前序遍历的序列是什么？

 

1.由后序遍历，得知C肯定为根结点

2.由中序遍历可知，c的左边是左子树（c右边是右子树）

3.先从后序入树 dabec ，由遍历规则（先访问根节点，在访问左子树和右子树）得知,e 为第二层节点 ，于是有

 

      c

e

 

4.结合中序遍历debac观察节点,由于 e为第二层节点，又d先于e被访问，所以d 是e的左孩子，ab未知

               c

         e

  d             a b

 

5.接下来看e的子孙节点a,b的部分

 

后序遍历为：ab

中序遍历为： ba（b先被访问有可能是b是左孩子，或者是根节点）即：

      eg 1.      b

                          a

 

     eg2.

                           a

                    b

 

 

再结合节点后序遍历，不难分析出a,b的位置是 eg2

 

于是最终的树为

 

                              c

                        e

                     d       b

                                     a

 

先序遍历: cedba

来源: