アルゴリズムとプログラミング
平成26年度 春期 基本情報技術者試験 午前 問6
2 分木の各ノードがもつ記号を出力する再帰的なプログラム Proc(n) の定義は，次のとおりである。このプログラムを，図の 2 分木の根（最上位のノード）に適用したときの出力はどれか。
Proc(n) {
n に左の子 l があれば Proc(l) を呼び出す。
n に右の子 r があれば Proc(r) を呼び出す。
n の記号を出力して終了する。
}
2 分木:
根 +（左の子 a，右の子 *）
* の左の子 −，右の子 d
− の左の子 b，右の子 c
（a, b, c, d は葉）
- ア +a*−bcd
- イ a+b−c*d
- ウ abc−d*+
- エ b−c*d+a
出典：平成26年度 春期 基本情報技術者試験 午前 問6
答えと解説を見る
正解：ウ
覚える知識
2分木の巡回順序(帰りがけ順)
子を先に処理して自分を最後に出力する巡回が帰りがけ(後行)順で、式木では後置表記になる。
この問題で必要なこと
左の子、右の子、自分の順で出力する再帰は帰りがけ順(後行順)で、式木から逆ポーランド表記が得られる。結果は abc−d*+。
ひっかけ
+a*−bcd は行きがけ順(前置)、a+b−c*d は通りがけ順(中置、括弧なし)との混同。
この知識の出題：本試験系 1 回・免除試験 6 回（公開問題での観測値）