已知一棵二叉树的中序序列和后序序列分别为c,b,a,e,d,h,g,j,i,f和c,b,e,h,j,i,g,f,d,a画出这棵二叉树,并写出其前序遍历序列

Question

已知一棵二叉树的中序序列和后序序列分别为c,b,a,e,d,h,g,j,i,f 和 c,b,e,h,j,i,g,f,d,a
画出这棵二叉树,并写出其前序遍历序列

Answer 1

这个问题我答了几次,搜一下就有答案了：
很简单.这也是个递归过程.
知道后序,就能找到“根”,是最后一个节点.
知道“根”节点,就好办了,从中序中把根结点找到,它左边是左子树的中序,
右边是右子树的中序,知道这两子树的中序,就能从后序中,把左子序、右子树
找出来（据中序的左、右子树的结点数）.
这样,根节点找出来了,左子数的后序、中序就分离出来了,右子数也分离出来了,
这个问题,就化成两个新树的问题.同样的办法如此,就是递归成两个子树的新问题.
如果用程序,一样用递归就做出来了.
如：后序中最后一个a就是根,从中序就能分出左右子树：
c b及 e d h g j i f 这是中序；
就可从后序分出左右子树：
cb 及 e h j i g f d
这个问题就变成了两个树的同样问题了.
左子树的中序c b,后序 c b
右子树的中序e d h g j i f 后序 e h j i g f d
就可推算出一颗整树 .
你就可用递归的办法写出程序.