已知一棵二叉树的中序序列和后序序列分别为B,D,C,E,A,G,H,F和D,E,C,B,H,G,F,A,求其对应的树

Question

如题所述

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
就可推算出一颗整树 .
你就可用递归的办法写出程序。

Answer 2