P1827 [USACO3.4]美国血统 American Heritage

由前序遍历 中序遍历求后序遍历。
主要方法是找根节点在中序遍历中的位置

char *p;p=(char *)malloc(sizeof(char)*N);cin>>p;char *i;int n=strlen(p);for(i=p;i<p+n;i++) {if(*i=='5') break;}cout<<i-p;

输入12345时，i-p = 4。可见下标是从1开始的。所以下面的递归构造左孩子时，就可以直接用k，因为这时的k是根节点所在位置-1。后面的构造右子树的时候，n是总数下标从1开始，k代表前序的串长度，再减1是减去根节点占的一格

//由二叉树的前序遍历，中序遍历求二叉树的后序遍历
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1000;
typedef struct node{char data;struct node *lchild;struct node *rchild;
}BTNode;
char *pre,*in; 
BTNode *CreateTree(char *pre,char *in,int n)//pre先序遍历  in中序遍历 n个数
{if(n<=0) return NULL;BTNode *st;st = (BTNode *)malloc(sizeof(BTNode));st->data = *pre;char *p;for(p=in;p<in+n;p++){if(*p==*pre) break;}//*p是当前的根节点int k = p - in;//k:根节点在中序遍历中的位置-1 (减去根节点所占的一格)st->lchild = CreateTree(pre+1,in,k);st->rchild = CreateTree(pre+k+1,p+1,n-k-1);return st;
}
void houxu(BTNode *bt)
{if(bt==NULL) return;houxu(bt->lchild);houxu(bt->rchild);cout<<bt->data;
}
int main()
{pre = (char *)malloc(sizeof(char)*N);in = (char *)malloc(sizeof(char)*N);cin>>in>>pre;  //半个小时，花在先输入中序遍历 后输入前序遍历BTNode *st;int n = strlen(in);st = CreateTree(pre,in,n); houxu(st);
}

不建树的方法：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100;
char lson[N],rson[N];
int pivot=0;
string in,pre;
void dfs(int root,int l,int r)
{if(l>=r) return;if(root>l){lson[root] = pre[++pivot];dfs(in.find(lson[root]),l,root-1);}if(root<r){rson[root] = pre[++pivot];dfs(in.find(rson[root]),root+1,r);}
}
void houxu(int root)
{if(root<0||root>in.length()) return;houxu(in.find(lson[root]));houxu(in.find(rson[root]));cout<<in[root];
}
int main()
{cin>>in>>pre;int root = in.find(pre[0]);dfs(root,0,in.length());houxu(root);
}