• <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)

            隨筆分類

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久夜色精品国产噜噜亚洲a| www性久久久com| 欧美激情精品久久久久久久| 日本欧美国产精品第一页久久| 中文成人无码精品久久久不卡| 久久精品青青草原伊人| 久久亚洲AV成人无码电影| 久久美女人爽女人爽| 国产69精品久久久久APP下载| 国产V亚洲V天堂无码久久久| 精品国产婷婷久久久| 人妻无码αv中文字幕久久| 国产69精品久久久久9999| 亚洲精品无码久久久久sm| 国产精品成人99久久久久| 久久亚洲日韩精品一区二区三区| 久久国产热这里只有精品| 久久精品人人做人人爽电影蜜月| 久久精品国产一区二区三区不卡| 日韩精品久久久肉伦网站| 亚洲精品无码久久久| 国内精品久久久久国产盗摄| 国内精品久久久久影院日本| 亚洲国产高清精品线久久| 日本免费久久久久久久网站| 波多野结衣AV无码久久一区| 久久久精品久久久久影院| 国产精品久久久99| 久久免费视频网站| 国产精品久久久天天影视| 久久婷婷五月综合国产尤物app| 四虎国产精品免费久久| 久久久WWW成人免费毛片| 国产精品青草久久久久婷婷 | 精品国产91久久久久久久 | 国内精品久久人妻互换 | 久久精品亚洲福利| 国产精品无码久久四虎| 18岁日韩内射颜射午夜久久成人 | 久久国产香蕉一区精品| 久久精品国产91久久麻豆自制|