USACO Section 3.4 American Heritage

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()==0return 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;
}
;

posted on 2008-09-23 17:05 幻浪天空领主 阅读(212) 评论(0)  编辑 收藏 引用 所属分类: USACO


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


<2024年12月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(1)

随笔档案(2)

文章分类(23)

文章档案(22)

搜索

最新评论

阅读排行榜

评论排行榜