采取递归的方法建立二叉树。
首先取前序遍历的首元素当作二叉树的根，当前元素为根。
把前序遍历中的当前元素当作中序遍历的分割点，中序遍历分割点前面的元素一定在当前元素的左子树，分割点后面元素一定在当前元素的右子树。然后加入下一个顶点，再把它当作分割点。
如此递归的进行，直到二叉树建立完成。
/**//*
ID: lorelei3
TASK: heritage
LANG: C++
*/
#include <fstream>
#include <iostream>
#include <memory.h>
#include <string.h>
using namespace std;
const int MAX = 100;
const int N = 10000;
int t;
char pre[MAX], mid[MAX], tree[N];
ifstream fin;
ofstream fout;
void Build(int n, char* pre, char* mid, int i)
{
if(n<=0)
return;
tree[i] = pre[0];
int p = strchr(mid, pre[0]) - mid;
Build(p, pre+1, mid, 2*i);
Build(n-p-1, pre+p+1, mid+p+1, 2*i+1);
}
void PostOrder(int i){
if(tree[i]==NULL)
return;
PostOrder(2*i);
PostOrder(2*i+1);
fout<<tree[i];
}
int main(){
fin.open("heritage.in");
fout.open("heritage.out");
memset(tree, NULL, sizeof(tree));
fin>>mid>>pre;
Build(strlen(pre), pre, mid, 1);
PostOrder(1);
fout<<endl;
return 0;
}posted on 2011-01-19 16:39
小阮 阅读(197)
评论(0) 编辑 收藏 引用 所属分类:
USACO