C++中如果知道了二叉树的前序和中序遍历，怎么知道后序遍历？有点急~

Question

如题所述

Answer 1

知道前序遍历就相当于知道了这棵二叉树的根节点（第一个节点便是）
而知道中序遍历
又
知道这棵树的根节点
就能知道
这棵树的左子树和右子树的所有节点（在中序遍历中找出根节点，根节点左边的所有节点是左子树，右边的所有节点是右子树）。
再分别把左子树和右子树当做一颗完整的树，按照前面的步骤继续分左子树和右子树。
然后就是重复以上动作来遍历整个一棵树（用递归来做），每当访问完一个子树时就输出本子树的根节点（为了后序遍历……）。
到最后分不出来时（既某个子树只有一个节点），这时就可以输出本节点，并且返回。
比如：前序遍历是：ABCD，中序遍历是：BADC。
首先，能求出此树的根节点是A，其次能知道这棵树的左子树的中序遍历是B。
所以这棵子树的前序遍历是B。
因为只有一个节点
所以输出B
再来看看这棵“大”树的右子树，右子树的中序遍历是DC，对应到前序遍历就是CD，所以这棵右子树的根节点就是C。
这棵右子树的左子树就是D，没有右子树。
所以这棵右子树的左子树的根节点也就是D
因为这课左子树的节点只有D，所以输出D。
返回到整棵树的右子树那一层，右子树的根节点是C，它的左右子树又都遍历完了，所以输出C。
最后退回到整棵树那一层，整棵树的根节点是A，左右子树又都遍历完了。
所以输出A。
一共输出了：BDCA。
这便是后序遍历。

Answer 2

这个好麻烦呢，似乎要用递归方法呢。
你看例如一个简单二叉树，根为A，B、C为叶子；前序为BAC，中序为ABC，后序为CAB。理论上已知前序和中序，就知道后序了。
思路：中序中第一个为根节点，后面的是左分支右分支；（左右两个分支中也要重复此处的，所以是递归。）然后在前序中找根节点的位置，前面的都是左分支的；进入下一次递归了。（当在中序中找到的某节点，在前序中没有前面没有了，那当前的就是叶子，然后开始右分支。）
主要是根据这两个遍历结果，重建二叉树。
你先不要编辑个什么二叉树类，先实现建立二叉树这个功能再说啊。上来就弄个类，自己还不太熟悉，当然会很多错误，你自己还不知道怎么错了。
你下载个MSDN可以查各个错误的原因，里面还有错误的例子，很好用，编程必须品。迅雷上有，评论多的就是。