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

            oyjpArt ACM/ICPC算法程序設計空間

            // I am new in programming, welcome to my blog
            I am oyjpart(alpc12, 四城)
            posts - 224, comments - 694, trackbacks - 0, articles - 6

            Tree的轉換與建立

            Posted on 2006-11-08 20:00 oyjpart 閱讀(630) 評論(3)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽

            好久沒有寫隨筆了。。呵呵。。
            呵呵 步ASP后塵 寫他的題去。。。-_-!!!
            看到一個題目 說是已知(input)一棵樹的前序和中序遍歷 要求輸出后序遍歷
            我的算法很簡單啦 就拿個字符串按照遍歷的結構剪來剪去 呵呵 后來又想如果我要得到這棵樹在內存中的狀態(tài)呢?(也就是從上到下的長相) 于是添加了個東東 呵呵 隨筆上來 各位見笑。。 呵呵

            solution:
            //by Optimistic
            #include <iostream>
            #include <string>
            #include <math.h>
            using namespace std;

            int maxk;
            string sa, sb;
            char dst[1000];
            int index[30];

            void init()
            {
            ?//initiation
            ?maxk = 0;
            ?memset(dst, '^', sizeof(dst));
            ?memset(index, 0, sizeof(index));
            ?cout << "The PostOrder Of the tree:\n";
            }

            void cal_tree(string sa, string sb)
            {
            ?if(sb.length() == 0) return;
            ?if(sb.length() == 1) {cout << sb;return;}
            ?char x = sa[0];
            ?int mid = sb.find(x);
            ?string c = sb.substr(0, mid);
            ?string d = sb.substr(mid+1);
            ?cal_tree(sa.substr(1, c.length()), c);
            ?cal_tree(sa.substr(1+c.length()), d);
            ?cout << x;
            }

            void cal_BFStree(string sa, string sb, char * dst, int k, int pos)
            {
            ?if(k>maxk) maxk = k;
            ?if(sb.length() == 0) return;
            ?if(sb.length() == 1)
            ?{
            ??dst[(int)pow(2, k-1)-1+pos-1] = sb[0];
            ??return;
            ?}
            ?char x = sa[0];
            ?dst[(int)pow(2, k-1)-1+pos-1] = x;
            ?int mid = sb.find(x);
            ?string c = sb.substr(0, mid);
            ?string d = sb.substr(mid+1);
            ?cal_BFStree(sa.substr(1, c.length()), c, dst, k+1, 2*pos-1);
            ?cal_BFStree(sa.substr(1+c.length()), d, dst, k+1, 2*pos);
            }

            void work()
            {
            ?cal_tree(sa, sb);
            ?cal_BFStree(sa, sb, dst, 1, 1);
            }

            void output()
            {
            ?cout << endl;
            ?int i, k=0;
            ?cout << "The Tree in the RAM is like this:-) \n";
            ?for(i=0; i<pow(2, sa.length()); i++)
            ?{
            ??cout << dst[i];
            ??if(i==pow(2, k)-1) k++;
            ??if(k>maxk) break;
            ?}
            ?cout << endl;
            }

            int main()
            {
            ?while(cin >> sa >> sb)
            ?{
            ??init();
            ??work();
            ??output();
            ?}
            ?return 0;
            }

            Sample Input

            DBACEGF ABCDEFG
            BCAD CBAD
            

            Sample Output

            DBACEGF ABCDEFG
            The PostOrder Of the tree:
            ACBFGED
            The Tree in the RAM is like this:-)
            DBEAC^G^^^^^^F^^
            BCAD CBAD
            The PostOrder Of the tree:
            CDAB
            The Tree in the RAM is like this:-)
            BCA^^^D^
            Original Problem	Tree Recovery 
            Time Limit:1000MS? Memory Limit:65536K
            Total Submit:451 Accepted:325
            Description
            Little Valentine liked playing with binary trees very much. Her favorite game was constructing randomly looking binary trees with capital letters in the nodes.
            This is an example of one of her creations:
            								
            ?????????????????????????????????????????????? D
            ????????????????????????????????????????????? / \
            ???????????????????????????????????????????? /?? \
            ??????????????????????????????????????????? B???? E
            ?????????????????????????????????????????? / \???? \
            ????????????????????????????????????????? /?? \???? \
            ???????????????????????????????????????? A???? C???? G
            ??????????????????????????????????????????????????? /
            ?????????????????????????????????????????????????? /
            ????????????????????????????????????????????????? F
            								
            To record her trees for future generations, she wrote down two strings for each tree: a preorder traversal (root, left subtree, right subtree) and an inorder traversal (left subtree, root, right subtree). For the tree drawn above the preorder traversal is DBACEGF and the inorder traversal is ABCDEFG.
            She thought that such a pair of strings would give enough information to reconstruct the tree later (but she never tried it).
            Now, years later, looking again at the strings, she realized that reconstructing the trees was indeed possible, but only because she never had used the same letter twice in the same tree. 
            However, doing the reconstruction by hand, soon turned out to be tedious.
            So now she asks you to write a program that does the job for her!
            ?
            Input
            The input will contain one or more test cases.
            Each test case consists of one line containing two strings preord and inord, representing the preorder traversal and inorder traversal of a binary tree. Both strings consist of unique capital letters. (Thus they are not longer than 26 characters.)
            Input is terminated by end of file.
            ?
            Output
            For each test case, recover Valentine's binary tree and print one line containing the tree's postorder traversal (left subtree, right subtree, root).
            Sample Input
            								
            DBACEGF ABCDEFG
            BCAD CBAD
            								
            Sample Output
            								
            ACBFGED
            CDAB
            								
            Source
            Ulm Local 1997

            Feedback

            # re: Tree的轉換與建立  回復  更多評論   

            2006-11-08 20:23 by Asp
            ................................................

            # re: Tree的轉換與建立  回復  更多評論   

            2006-11-11 23:26 by 冬天¤不回來
            BS你,我看不懂

            # re: Tree的轉換與建立  回復  更多評論   

            2008-07-26 05:54 by lengbufang
            哦哦~!!
            亚洲精品国产第一综合99久久| 四虎国产精品成人免费久久| …久久精品99久久香蕉国产| 久久夜色精品国产亚洲| 香蕉aa三级久久毛片| 久久影院综合精品| 国产亚洲成人久久| 精品久久久噜噜噜久久久| 久久久99精品成人片中文字幕| 漂亮人妻被黑人久久精品| 国产精品热久久毛片| 久久午夜伦鲁片免费无码| 久久性生大片免费观看性| 国产V亚洲V天堂无码久久久| 久久久久久久亚洲精品| 久久91精品国产91久久麻豆| 性做久久久久久久| 偷偷做久久久久网站| 久久精品成人| 久久国产精品无码网站| 久久99精品综合国产首页| 婷婷久久久亚洲欧洲日产国码AV | 亚洲AV日韩精品久久久久| 久久久久亚洲AV综合波多野结衣| 久久美女网站免费| 77777亚洲午夜久久多喷| 亚洲精品美女久久777777| 国产精品久久久久久五月尺| 一本大道久久东京热无码AV| 亚洲国产成人久久笫一页| 看全色黄大色大片免费久久久| 国产成人精品久久亚洲| 亚洲国产精品久久66| 国产精品青草久久久久婷婷 | 久久99热国产这有精品| 久久精品a亚洲国产v高清不卡| 亚洲AV无码久久精品成人 | 国产三级观看久久| 久久影视综合亚洲| 久久久亚洲裙底偷窥综合 | 久久久久人妻一区精品果冻|