1001 : Binary Tree Intersection And Union
問題リンク:Binary Tree Intersection And Union | Aizu Online Judge
解法:
実際に2つ木を作って指定された処理を行った
配列で2分木を実装するとノードが最大100個なので配列内に収まらない
なのでポインタを使って実装した
struct Tree { bool child[2];//child[0] -> 左の子が存在するか, child[1] -> 右の子が存在するか Tree *next[2];//next[0] -> 左の子のポインタ, next[1] -> 右の子のポインタ };
久しぶりにポインタ使ったけど案外思い通りに動いてくれて楽しかった
コード:
struct Tree { bool root; bool child[2]; Tree *next[2];//left -> false, right -> true Tree() { child[0] = child[1] = false; root=false; } }; string s[2]; Tree tree[2]; void ddfs(Tree *t) { if(!t->child[0] && !t->child[1])return; if(t->child[0]) { ddfs(t->next[0]); t->child[0] = false; delete t->next[0]; } if(t->child[1]) { ddfs(t->next[1]); t->child[1] = false; delete t->next[1]; } } void init() { tree[0].root = tree[1].root = true; rep(i,2)ddfs(&tree[i]); } void parse(int index,int &pos,Tree *t,int depth) { if(pos >= s[index].size())return; bool LR = false; ++pos; while(pos < s[index].size() && !(LR && s[index][pos] == ')')) { if(s[index][pos] == '(') { t->next[LR] = new Tree; t->next[LR]->root = false; t->next[LR]->child[0] = t->next[LR]->child[1] = false; t->child[LR] = true; parse(index,pos,t->next[LR],depth+1); if(pos < s[index].size() && LR && s[index][pos] == ')')break; } if(s[index][pos] == ',') LR = true; ++pos; } ++pos; } void tree_walk(Tree *t,int depth) { cout << '('; if(t->child[0])tree_walk(t->next[0],depth+1); cout << ','; if(t->child[1])tree_walk(t->next[1],depth+1); cout << ')'; } void dfs_i(Tree *t1,Tree *t2,Tree *ans) { if(t1->child[0] && t2->child[0]) { ans->next[0] = new Tree; ans->child[0] = true; ans->next[0]->child[0] = ans->next[0]->child[1] = false; dfs_i(t1->next[0],t2->next[0],ans->next[0]); } if(t1->child[1] && t2->child[1]) { ans->next[1] = new Tree; ans->child[1] = true; ans->next[1]->child[0] = ans->next[1]->child[1] = false; dfs_i(t1->next[1],t2->next[1],ans->next[1]); } } void dfs_u(Tree *t,Tree *ans) { if(t->child[0]) { if(ans->child[0]) {//already exists dfs_u(t->next[0],ans->next[0]); } else {//not yet ans->next[0] = new Tree; ans->child[0] = true; ans->next[0]->child[0] = ans->next[0]->child[1] = false; dfs_u(t->next[0],ans->next[0]); } } if(t->child[1]) { if(ans->child[1]) {//already exists dfs_u(t->next[1],ans->next[1]); } else {//not yet ans->next[1] = new Tree; ans->child[1] = true; ans->next[1]->child[0] = ans->next[1]->child[1] = false; dfs_u(t->next[1],ans->next[1]); } } } void compute(char c) { Tree ans; ans.root = true; ans.child[0] = ans.child[1] = false; if(c == 'i') { dfs_i(&tree[0],&tree[1],&ans); tree_walk(&ans,0); cout << endl; } else if(c == 'u') { dfs_u(&tree[0],&ans); dfs_u(&tree[1],&ans); tree_walk(&ans,0); cout << endl; } ddfs(&ans); } int main() { char c; while(cin >> c) { cin >> s[0] >> s[1]; init(); int pos; rep(i,2) { pos = 0; parse(i,pos,&tree[i],0); } compute(c); } return 0; }