「AOJ1001 Binary Tree Intersection And Union」の編集履歴（バックアップ）一覧に戻る
*AOJ1001 Binary Tree Intersection And Union
**サイト
[http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1001]
**解説
タイトルの通り入力の木は二分木である。
入力のBNFを書いてみると実装がしやすい。以下がBNFである。
>>
< binary> := (<binary>,<binary>) | ε
<<
εは空文字列を意味し、木構造の葉（終端）である。
このBNFによって記述された2つの二分木をIntersectまたはUnionする。先ずは上のBNFの構文解析をして、1つの二分木のみの解析を考えてみよう。
カンマの位置を特定することが必要なのでその方法を考える。先頭の'('を読み飛ばしてから、'('が来たらカウントを1増やし、')'が来たらカウントを1減らす操作をする。カウントが0になったときにカンマの位置が発見できるので前後の<binary>が分割可能。分割のコードは以下。
>||
void divStr(const string& s, string& s1, string& s2) {
int n = s.size();
int retain = 0;
for(int pos=1; ; pos++) {
if(s[pos] == '(') retain++;
if(s[pos] == ')') retain--;
else if(retain == 0) {
s1 = s.substr(1, pos-1);
s2 = s.substr(pos+1, n-pos-2);
return;
}
}
}
||<
分割が完了したら、(A,B)のAとB両方で再帰が起こる。BNFの通り、再帰の終了条件を空文字列とすれば二分木の構文解析が終了する。
次に、２つの二分木のIntersectとUnionについて考えよう。２つの木を重ねあわせたとき「片方が終端に達していても、もう片方が非終端である場合」がある。出力すべき文字列の形式で言い換えると、「片方が空文字列であっても、もう片方がまだ文字列をもつ場合がある」と言える。つまり2つの木のどちらかが終端に達した時点で、残りは文字列のminを取るかmaxを取るかでIntersectとUnionが完了する。コードは以下。
>||
string make(string op, string s, string t) {
if(s == "" || t == "") {
if(op == "i") return "";
else return s == "" ? t : s;
}
string sL, sR, tL, tR;
divStr(s, sL, sR);
divStr(t, tL, tR);
return '(' + make(op, sL, tL) + ',' + make(op, sR, tR) + ')';
}
||<
