• <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 閱讀(629) 評論(3)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽

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

            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精品| 久久精品国产亚洲77777| 久久综合九色综合久99| 亚洲а∨天堂久久精品9966| 久久亚洲中文字幕精品有坂深雪| 青草影院天堂男人久久| 久久影院亚洲一区| 国内精品久久久人妻中文字幕| 国产精品va久久久久久久| 久久精品人人做人人爽电影| 亚洲综合婷婷久久| 久久超碰97人人做人人爱| 久久久青草青青国产亚洲免观| 亚洲va国产va天堂va久久| 夜夜亚洲天天久久| 国产精品岛国久久久久| 一本色道久久综合亚洲精品| 久久久精品日本一区二区三区| 亚洲成色www久久网站夜月| 欧美激情精品久久久久久| 久久久精品免费国产四虎| 99精品久久久久久久婷婷| 国产伊人久久| 97超级碰碰碰碰久久久久| 国产精品久久久久…| 亚洲乱码中文字幕久久孕妇黑人| 久久久精品久久久久久| 免费国产99久久久香蕉| 狠狠色丁香久久婷婷综合五月| 亚洲午夜久久久久久久久久| 久久久久久久免费视频| 精品久久人人爽天天玩人人妻| 久久国产欧美日韩精品| 99久久99这里只有免费费精品| 国内精品伊人久久久久777| 久久精品人人做人人爽电影| 久久精品免费一区二区| 人妻精品久久久久中文字幕69| 久久亚洲欧美国产精品| 97久久天天综合色天天综合色hd | 97精品国产97久久久久久免费|