• <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 3.4 American Heritage

            給出一個樹的中序遍歷和先序遍歷,求它的后序遍歷。

            遞歸求解即可。
            先序遍歷中的第一個值必為中間結點的值,然后在中序遍歷中找到這個值。這個值左邊的為左子樹的中序遍歷,右邊為右子樹的中序遍歷。
            先序遍歷中,前半部分為左子樹的先序遍歷,其長度和中序子左子樹的長度相同。因此兩個子樹的中序和先序遍歷都可以確定了。

            構造出完整的樹之后,再后序遍歷即可。


            #include?<iostream>
            #include?
            <fstream>

            using?namespace?std;

            ifstream?fin(
            "heritage.in");
            ofstream?fout(
            "heritage.out");

            #ifdef?_DEBUG
            #define?out?cout
            #define?in?cin
            #else
            #define?out?fout
            #define?in?fin
            #endif

            char?in_order[27];
            char?pre_order[27];

            struct?tree_node{
            ????
            char?value;
            ????tree_node
            *left,*right;
            ????tree_node(){
            ????????left?
            =?right?=?NULL;
            ????}
            };

            tree_node
            *??build_tree(int?in_start,int?in_end,int?pre_start,int?pre_end)
            {
            ????tree_node?
            *node?=?new?tree_node;

            ????node
            ->value?=??pre_order[pre_start];

            ????
            if(pre_start>pre_end)?return?NULL;

            ????
            if(pre_start!=pre_end){
            ????????
            int?pos;
            ????????
            for(pos=in_start;pos<=in_end;++pos){
            ????????????
            if(in_order[pos]==pre_order[pre_start])
            ????????????????
            break;
            ????????}
            ????????node
            ->left?=?build_tree(in_start,pos-1,pre_start+1,pre_start+pos-in_start);
            ????????node
            ->right?=?build_tree(pos+1,in_end,pre_start+pos-in_start+1,pre_end);
            ????}

            ????
            return?node;
            }

            void?post_traverse(const?tree_node*node)
            {
            ????
            if(node==NULL)?return;

            ????
            if(node->left!=NULL){
            ????????post_traverse(node
            ->left);
            ????}

            ????
            if(node->right!=NULL){
            ????????post_traverse(node
            ->right);
            ????}

            ????
            out<<node->value;
            }


            void?solve()
            {
            ????
            in>>in_order;
            ????
            in>>pre_order;

            ????post_traverse(?build_tree(
            0,strlen(in_order)-1,0,strlen(pre_order)-1)?);

            ????
            out<<endl;
            }


            int?main(int?argc,char?*argv[])
            {
            ????solve();?
            ????
            return?0;
            }



            其實不需要建樹,再后序遍歷。直接在建樹過程中后序輸出即可。

            #include?<iostream>
            #include?
            <fstream>

            using?namespace?std;

            ifstream?fin(
            "heritage.in");
            ofstream?fout(
            "heritage.out");

            #ifdef?_DEBUG
            #define?out?cout
            #define?in?cin
            #else
            #define?out?fout
            #define?in?fin
            #endif

            char?in_order[27];
            char?pre_order[27];
            char?post_order[27];

            struct?tree_node{
            ????
            char?value;
            ????tree_node
            *left,*right;
            ????tree_node(){
            ????????left?
            =?right?=?NULL;
            ????}
            };

            void??build_tree(int?in_start,int?in_end,int?pre_start,int?pre_end)
            {
            ????
            if(pre_start>pre_end)?return;

            ????
            if(pre_start!=pre_end){
            ????????
            int?pos;
            ????????
            for(pos=in_start;pos<=in_end;++pos){
            ????????????
            if(in_order[pos]==pre_order[pre_start])
            ????????????????
            break;
            ????????}
            ????????build_tree(in_start,pos
            -1,pre_start+1,pre_start+pos-in_start);
            ????????build_tree(pos
            +1,in_end,pre_start+pos-in_start+1,pre_end);
            ????}

            ????
            out<<pre_order[pre_start];
            }

            void?solve()
            {
            ????
            in>>in_order;
            ????
            in>>pre_order;

            ????build_tree(
            0,strlen(in_order)-1,0,strlen(pre_order)-1);

            ????
            out<<endl;
            }


            int?main(int?argc,char?*argv[])
            {
            ????solve();?
            ????
            return?0;
            }


            posted on 2009-07-10 18:51 YZY 閱讀(292) 評論(0)  編輯 收藏 引用 所屬分類: AlgorithmUSACO圖論

            導航

            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            統計

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            开心久久婷婷综合中文字幕| 精品久久久一二三区| www性久久久com| 久久久中文字幕| 国产无套内射久久久国产| 性做久久久久久久久久久| 久久久久女人精品毛片| 欧美一区二区精品久久| 久久精品国产精品亜洲毛片| 久久精品国产99国产精品亚洲| 久久精品麻豆日日躁夜夜躁| 精品免费久久久久国产一区| 午夜欧美精品久久久久久久| 久久99久久无码毛片一区二区| 久久精品国产亚洲av水果派| 久久99精品久久久久久水蜜桃| 国产精品久久久久9999| 狠狠色丁香久久婷婷综合图片| 精品久久久久久无码免费| 思思久久精品在热线热| 久久精品国产99久久久香蕉| 久久精品夜夜夜夜夜久久| 国产精品久久久久久久人人看| 久久影视综合亚洲| 国产亚州精品女人久久久久久 | 久久精品这里热有精品| 亚洲午夜精品久久久久久app| 久久高潮一级毛片免费| 国产精品免费福利久久| 77777亚洲午夜久久多人| 亚洲国产精品成人久久蜜臀 | 国产精品免费福利久久| 欧美日韩久久中文字幕| 国产精品久久新婚兰兰| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区| 国产精品美女久久久| 久久免费线看线看| 狠狠色伊人久久精品综合网| 国产精品亚洲美女久久久| 久久九九久精品国产| 久久这里有精品视频|