前序遍历与中序遍历确定后序遍历

#include <iostream>  
#include <string>  
using namespace std;  

//结点类  
struct Node  
{  
    Node * lchild;  
    Node * rchild;  
    char c;  
};  
//重建后续排序二叉树  
Node * rebuild(string s1, string s2)  
{  
    //建立根结点  
    Node * t=NULL;  //一定要初始化为NULL，不然报错  
    if(s1.size()>0){  
        t=new Node;  
        t->c=s1[0];  
        t->lchild=NULL;  
        t->rchild=NULL;  
    }  
    if(s1.size()>1){  
        //寻找根结点在中序遍历中的位置  
        int root;  
        for(int i=0; i<s2.size(); i++){  
            if(s2[i]==t->c){  
                root=i;  
                break;  
            }  
        }  
        //左子树重建  
        string qianxu_left=s1.substr(1, root); //注意substr的用法，第二个参数是子字符串长度  
        string zhongxu_left=s2.substr(0, root);  
        t->lchild=rebuild(qianxu_left, zhongxu_left);  
        //右子树重建  
        string qianxu_right=s1.substr(root+1, s1.size()-root-1);  
        string zhongxu_right=s2.substr(root+1, s2.size()-root-1);  
        t->rchild=rebuild(qianxu_right, zhongxu_right);  
    }  
  
    return t;  
}  
//后序遍历：左右根  
void houxu(Node * t)  
{  
    //左子树非空，遍历左子树  
    if(t->lchild!=NULL)  
        houxu(t->lchild);  
    //右子树非空，遍历右子树  
    if(t->rchild!=NULL)  
        houxu(t->rchild);  
    //取出该结点的值  
    cout<<t->c;  
}  
  
int main()  
{  
    string s1, s2;
    cin>>s1>>s2;
            Node * t=rebuild(s1, s2);  
        houxu(t);  
        cout<<endl;    
  
    return 0;  
}