首页 > 代码库 > 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(树的遍历)