青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(636) 評論(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
哦哦~!!
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲人久久久| 免费成人小视频| 欧美在线观看www| 久久先锋影音av| 欧美女同视频| 国产日韩亚洲| 亚洲美女毛片| 久久国产视频网站| 欧美激情精品久久久久久变态 | 激情视频亚洲| 日韩图片一区| 久久久之久亚州精品露出| 欧美激情1区| 午夜激情亚洲| 欧美日韩精品免费观看视频| 国产热re99久久6国产精品| 亚洲国产欧美久久| 久久高清一区| 亚洲欧洲偷拍精品| 亚洲欧美中文日韩在线| 欧美激情视频在线播放 | 国产精品毛片高清在线完整版| 一区二区亚洲精品| 亚洲视频电影图片偷拍一区| 久热综合在线亚洲精品| 一区二区成人精品| 噜噜爱69成人精品| 韩国成人福利片在线播放| 亚洲自拍啪啪| 亚洲精品在线电影| 欧美xxx在线观看| 在线观看日韩av| 久久久久久9999| 亚洲欧美日韩区| 国产精品久久91| 亚洲网站啪啪| 日韩午夜在线视频| 欧美精品久久久久久久免费观看| 亚洲电影在线观看| 久久在精品线影院精品国产| 午夜精品亚洲一区二区三区嫩草| 国产精品伦子伦免费视频| aa级大片欧美| 亚洲欧洲一区| 欧美国产大片| 亚洲伦理在线观看| 亚洲第一精品夜夜躁人人爽| 欧美性一二三区| 亚洲人成网在线播放| 欧美gay视频| 久热国产精品视频| 亚洲成色999久久网站| 久久久最新网址| 久久精品国产免费观看| 狠狠久久婷婷| 农村妇女精品| 欧美夫妇交换俱乐部在线观看| 亚洲第一色中文字幕| 米奇777在线欧美播放| 美国十次了思思久久精品导航| 亚洲福利视频网站| 亚洲韩国日本中文字幕| 欧美国产欧美亚洲国产日韩mv天天看完整 | 欧美性大战久久久久久久蜜臀| 亚洲国产天堂久久国产91| 欧美成年人视频| 欧美激情一区二区三区不卡| 在线视频日韩| 欧美一级网站| 91久久综合| 夜夜嗨av色一区二区不卡| 国产精品美女久久久久av超清 | 日韩一二三在线视频播| 国产精品免费福利| 久久综合网hezyo| 欧美激情一区二区三区成人| 亚洲欧美久久久久一区二区三区| 亚洲欧美第一页| 黄色成人91| 免费欧美视频| 欧美日韩精品| 久久久噜噜噜久噜久久| 欧美高清在线观看| 久久精品亚洲一区| 欧美精品激情在线| 久久这里只精品最新地址| 欧美另类极品videosbest最新版本| 午夜精品国产更新| 欧美成人精品福利| 久久精品国产免费看久久精品| 欧美第一黄网免费网站| 久久精品亚洲一区| 欧美视频网址| 亚洲国产成人久久| 国内精品久久久久久久果冻传媒| 亚洲美女电影在线| 亚洲高清免费在线| 小处雏高清一区二区三区| 99热在线精品观看| 老司机一区二区三区| 小处雏高清一区二区三区| 欧美国产激情| 欧美成人一区二区三区片免费| 国产毛片一区| 亚洲尤物影院| 亚洲欧美视频在线观看| 欧美日韩爆操| 亚洲黄色大片| 91久久精品美女| 久久免费99精品久久久久久| 欧美一区二区三区视频在线| 欧美系列电影免费观看| 最新日韩在线| 亚洲美女毛片| 欧美激情视频一区二区三区免费| 欧美多人爱爱视频网站| 韩国一区电影| 久久精品国产亚洲一区二区三区| 久久激情视频| 国际精品欧美精品| 小处雏高清一区二区三区| 久久www免费人成看片高清| 国产精品国产三级国产普通话蜜臀 | 久久亚洲精品欧美| 国产精品久久久一区二区三区| 日韩视频在线观看一区二区| 一本色道精品久久一区二区三区| 欧美91大片| 91久久精品国产91久久性色| 亚洲精品久久久久久久久久久久| 免费亚洲电影| 亚洲肉体裸体xxxx137| 亚洲精品一区二区三区在线观看| 欧美va亚洲va国产综合| 91久久在线| 在线视频你懂得一区二区三区| 国产精品成人一区二区三区吃奶| 一本大道久久a久久精品综合 | 国产欧美一级| 亚欧成人在线| 欧美/亚洲一区| 亚洲日韩欧美视频| 欧美新色视频| 久久国产精品一区二区| 欧美顶级艳妇交换群宴| 一区二区成人精品 | 小黄鸭精品aⅴ导航网站入口| 久久色中文字幕| 亚洲靠逼com| 国产精品入口| 美女主播一区| 一区二区欧美在线| 久久看片网站| 99亚洲精品| 国产一区免费视频| 欧美第一黄色网| 小黄鸭视频精品导航| 亚洲大胆女人| 性欧美8khd高清极品| 亚洲高清一区二| 国产精品国产三级国产aⅴ浪潮| 久久精品国产69国产精品亚洲| 91久久精品网| 久久久国产精彩视频美女艺术照福利 | 亚洲高清成人| 欧美一区二区三区在线播放| 最新国产の精品合集bt伙计| 国产精品婷婷| 裸体歌舞表演一区二区| 亚洲一区二区在线免费观看| 欧美国产一区在线| 久久精品五月婷婷| 亚洲综合第一页| 91久久夜色精品国产九色| 国产欧美韩日| 国产精品国色综合久久| 欧美国产日韩一区二区三区| 欧美在线观看视频在线| a4yy欧美一区二区三区| 欧美激情bt| 久久天天躁狠狠躁夜夜av| 亚洲欧美日韩国产中文在线| 亚洲人体大胆视频| 亚洲福利免费| 在线免费观看欧美| 国产在线精品一区二区中文| 国产精品女人久久久久久| 欧美人牲a欧美精品| 欧美福利在线观看| 久热成人在线视频| 久久久噜噜噜久久| 欧美中文字幕第一页| 一区二区久久久久| 日韩一级大片| 亚洲美女视频在线免费观看| 最新国产成人av网站网址麻豆| 欧美国产精品久久| 欧美国产另类| 亚洲高清免费视频| 亚洲黄色在线视频|