• <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
            哦哦~!!
            国产69精品久久久久99| 久久亚洲私人国产精品vA| 国内精品久久久久久久久| 久久性精品| 7777精品久久久大香线蕉| 99久久精品午夜一区二区| 久久国产精品成人免费| 久久国产精品无码网站| 久久夜色精品国产亚洲| 亚洲国产精品久久久久| 久久久久久亚洲精品影院| 亚洲国产精品18久久久久久| 精品久久久久久无码中文字幕| 久久国产色av免费看| 国产成人久久精品麻豆一区| 久久亚洲私人国产精品| 亚洲国产成人久久精品99 | 99久久精品免费看国产免费| 亚洲国产精品成人久久蜜臀| 久久香蕉国产线看观看乱码| 亚洲精品乱码久久久久久蜜桃不卡| 91麻精品国产91久久久久| 无码精品久久久天天影视| 亚洲一级Av无码毛片久久精品| 国产激情久久久久影院| 国产精品青草久久久久婷婷| 亚洲国产精品无码久久一区二区| 无码8090精品久久一区| 日本免费一区二区久久人人澡| 蜜臀av性久久久久蜜臀aⅴ| 久久天天躁夜夜躁狠狠| 久久久中文字幕日本| 久久久久99精品成人片三人毛片 | 久久久久国产精品| 亚洲AV无码久久精品色欲| 久久久久久国产精品无码下载| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区 | 精品一区二区久久| 久久国产精品-国产精品| 久久99热国产这有精品| 久久精品人人做人人爽电影|