二叉树遍历-题解(C++代码)

常规做法，先通过先序遍历和中序遍历构造二叉树，再输出后序遍历序列

#include<iostream>
#include<cstdlib>
using namespace std;
struct node
{
    char data;
    struct node *lchild;
    struct node *rchild;
};
node* create(string pre,string mid)
{
    node *root=NULL;
    int len,index;
    string s1,s2;
    string m1,m2;
    if(pre.length()>0)
    {
        root=(node*)malloc(sizeof(node));
        root->lchild=NULL;
        root->rchild=NULL;
        len=pre.length();
        root->data=pre[0];
        index=mid.find(pre[0]);
        m1=mid.substr(0,index);
        m2=mid.substr(index+1,pre.length()-index-1);
        s1=pre.substr(1,index);
        s2=pre.substr(index+1,pre.length()-index-1);
        root->lchild=create(s1,m1);
        root->rchild=create(s2,m2);
    }
    return root;
}
void lasvis(node *t)
{
    if(t==NULL)
    {
        return;
    }
    lasvis(t->lchild);
    lasvis(t->rchild);
    cout<<t->data;
}
int main()
{
    string pre,mid;
    while(cin>>pre>>mid)
    {
        node *t;
        t=create(pre,mid);
        lasvis(t);
        cout<<endl;    
    }    
    return 0;
}