随笔-141  评论-9  文章-3  trackbacks-0
采取递归的方法建立二叉树。
首先取前序遍历的首元素当作二叉树的根,当前元素为根。
把前序遍历中的当前元素当作中序遍历的分割点,中序遍历分割点前面的元素一定在当前元素的左子树,分割点后面元素一定在当前元素的右子树。然后加入下一个顶点,再把它当作分割点。
如此递归的进行,直到二叉树建立完成。
/*
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+12*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 小阮 阅读(203) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理