• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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 幻浪天空領主 閱讀(230) 評論(0)  編輯 收藏 引用 所屬分類: USACO

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統(tǒng)計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            99蜜桃臀久久久欧美精品网站| 性欧美大战久久久久久久久 | 久久国产精品99久久久久久老狼| 久久久国产乱子伦精品作者| 久久精品国产91久久综合麻豆自制| 91精品观看91久久久久久| 久久天天躁狠狠躁夜夜2020老熟妇| 超级97碰碰碰碰久久久久最新| 国产99久久精品一区二区| 无码任你躁久久久久久| 精品蜜臀久久久久99网站| 伊人久久大香线蕉成人| 国产国产成人久久精品| 日本久久久久亚洲中字幕| 久久青青草原精品国产软件| 久久久久久久亚洲Av无码| 中文字幕无码久久精品青草| 久久er热视频在这里精品| 久久久久久精品免费看SSS | 一级做a爰片久久毛片免费陪| 996久久国产精品线观看| 久久夜色精品国产亚洲| 久久精品无码一区二区三区日韩| 7777久久亚洲中文字幕| 99久久综合国产精品免费| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 国产成人久久精品一区二区三区| 久久亚洲AV永久无码精品| 一级做a爰片久久毛片16| 久久中文字幕一区二区| 久久精品国产亚洲AV电影| 久久精品国产亚洲AV麻豆网站| 精品国产乱码久久久久软件| 无码乱码观看精品久久| 久久性精品| 久久综合久久鬼色| 国产69精品久久久久观看软件| 久久人人爽人人爽人人片AV东京热| 久久嫩草影院免费看夜色| 亚洲AⅤ优女AV综合久久久| 久久亚洲国产成人影院|