• <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算法程序設(shè)計空間

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

            Tree的轉(zhuǎn)換與建立

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

            好久沒有寫隨筆了。。呵呵。。
            呵呵 步ASP后塵 寫他的題去。。。-_-!!!
            看到一個題目 說是已知(input)一棵樹的前序和中序遍歷 要求輸出后序遍歷
            我的算法很簡單啦 就拿個字符串按照遍歷的結(jié)構(gòu)剪來剪去 呵呵 后來又想如果我要得到這棵樹在內(nèi)存中的狀態(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的轉(zhuǎn)換與建立  回復  更多評論   

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

            # re: Tree的轉(zhuǎn)換與建立  回復  更多評論   

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

            # re: Tree的轉(zhuǎn)換與建立  回復  更多評論   

            2008-07-26 05:54 by lengbufang
            哦哦~!!
            18禁黄久久久AAA片| 无码人妻久久久一区二区三区| 久久久久久亚洲Av无码精品专口| 久久久久久亚洲精品成人| 国产精久久一区二区三区| 国产精品久久久久久五月尺| 国产综合久久久久| 久久人人爽人人爽人人片AV高清| 午夜不卡久久精品无码免费| 久久精品国产欧美日韩| 精品熟女少妇AV免费久久| 99久久99久久精品国产片果冻| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区 | 免费精品国产日韩热久久| 久久精品aⅴ无码中文字字幕重口| 99热精品久久只有精品| 漂亮人妻被黑人久久精品| 久久久久久久久久免免费精品| AV色综合久久天堂AV色综合在| 国产精品亚洲综合久久| 久久久久国产精品麻豆AR影院| 国产高潮国产高潮久久久| 久久综合精品国产二区无码| 中文字幕无码久久人妻| 久久综合视频网站| 久久久久噜噜噜亚洲熟女综合| 91精品国产91久久久久久| 久久精品国产99国产精偷| 99久久免费国产精精品| 精品无码久久久久久午夜| 日韩人妻无码精品久久久不卡| 国产成人久久精品一区二区三区| 久久久久亚洲AV成人网人人软件| 国产午夜福利精品久久| 热久久这里只有精品| 婷婷综合久久中文字幕| 精品久久国产一区二区三区香蕉| 中文字幕亚洲综合久久| 久久久久亚洲爆乳少妇无| 99久久这里只精品国产免费| 久久AV高潮AV无码AV|