首页 > 代码库 > POJ 2255 Tree Recovery(树的遍历)
POJ 2255 Tree Recovery(树的遍历)
给定前序遍历和中序遍历,写出后序遍历。
#include <iostream>#include <cstdlib>#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <assert.h>#include <algorithm>#define MAX 1234567890#define MIN -1234567890#define eps 1e-8using namespace std;char bef[32];char mid[32];char aft[32];char tree[1024];bool visit[32];int len;int p;void build(char root, int t){ int i, j; tree[t] = root; visit[root-‘A‘] = true; for(i = 0; i < len; i++) if(mid[i] == root) break; for(j = 0; j < len; j++) if(bef[j] == root) break; if(i-1 >= 0 && !visit[mid[i-1]-‘A‘]) { char lson = bef[j+1]; build(lson, 2*t); } if(i+1 < len && !visit[mid[i+1]-‘A‘]) { char rson; for(int k = j+1; k < len; k++) { if(!visit[bef[k]-‘A‘]) { rson = bef[k]; break; } } build(rson, 2*t+1); }}void after(char root, int t){ if(tree[2*t] != ‘\0‘) after(tree[2*t], 2*t); if(tree[2*t+1] != ‘\0‘) after(tree[2*t+1], 2*t+1); aft[p++] = root;}int main(){ #ifdef BellWind freopen("2255.in", "r", stdin); #endif // BellWind while (~scanf("%s %s", bef, mid)) { memset(visit, 0, sizeof(visit)); memset(tree, 0, sizeof(tree)); len = strlen(bef); build(bef[0], 1);// int cnt = 0;// for(int c = 1; cnt < len; c++)// {// if(tree[c] == ‘\0‘) cout << ‘ ‘;// else {cnt++; cout << tree[c];}// }// cout << endl; p = 0; after(bef[0], 1); for(int c = 0; c < len; c++) cout << aft[c]; cout << endl; } return 0;}
POJ 2255 Tree Recovery(树的遍历)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。