American Heritage
Farmer John takes the heritage of his cows very seriously. He is not, however, a truly fine bookkeeper. He keeps his cow genealogies as binary trees and, instead of writing them in graphic form, he records them in the more linear `tree in-order' and `tree pre-order' notations.
Your job is to create the `tree post-order' notation of a cow's heritage after being given the in-order and pre-order notations. Each cow name is encoded as a unique letter. (You may already know that you can frequently reconstruct a tree from any two of the ordered traversals.) Obviously, the trees will have no more than 26 nodes.
Here is a graphical representation of the tree used in the sample input and output:
C
/ \
/ \
B G
/ \ /
A D H
/ \
E F
The in-order traversal of this tree prints the left sub-tree, the root, and the right sub-tree.
The pre-order traversal of this tree prints the root, the left sub-tree, and the right sub-tree.
The post-order traversal of this tree print the left sub-tree, the right sub-tree, and the root.
PROGRAM NAME: heritage
INPUT FORMAT
| Line 1: |
The in-order representation of a tree. |
| Line 2: |
The pre-order representation of that same tree. |
SAMPLE INPUT (file heritage.in)
ABEDFCHG
CBADEFGH
OUTPUT FORMAT
A single line with the post-order representation of the tree.
SAMPLE OUTPUT (file heritage.out)
AEFDBHGC
Analysis
A simple problem with binary tree structure. The first element of preorder traversal is root, which is used of building a tree. Constructing recurrensively, the tree will be build successfully.
In this problem, I made a mistake of applying space. When I applying for a Node of root, I only declared it in the function without opening it. Well, the pointer outside became wandering.It is fantasy!
Code
/**//*
ID:braytay1
PROG:heritage
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream fin("heritage.in");
ofstream fout("heritage.out");
typedef struct Node
{
char val;
struct Node *lc,*rc;
}Node, *BiTree;
Node* maketree(string &prev,string &inv){
if (prev.size()==0||inv.size()==0) return NULL;
Node *root=new Node[1];
//This sentence is very IMPORTANT!!
//The tree can only be saved with this sentence
//since the variables declared in a function are
//saved in the Stack Storage instead of globle storage.
root->val=prev[0];
string lp,li,rp,ri;
int len=0;
for (unsigned int i=0;;i++){
if (inv[i]==prev[0]){
len=i;
break;
}
}
for (int i=0;i<len;i++){
lp.push_back(prev[i+1]);
li.push_back(inv[i]);
}
for (int i=len+1;i<prev.size();i++){
rp.push_back(prev[i]);
ri.push_back(inv[i]);
}
root->lc=maketree(lp,li);
root->rc=maketree(rp,ri);
return root;
}
void post_tra(BiTree &r){
if (r==NULL) return;
post_tra(r->lc);
post_tra(r->rc);
fout<<r->val;
}
int main(){
string pretra,intra;
fin>>intra>>pretra;
BiTree Top;
Top=maketree(pretra,intra);
post_tra(Top);
fout<<endl;
return 0;
};