アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20161211 実施分 問5
2分木の各ノードがもつ記号を出力する再帰的なプログラム Proc(n)の定義は，次のとおりである。このプログラムを，図の 2 分木の根（最上位のノード）に適用したときの出力はどれか。
Proc(n) {
n に左の子 l があれば Proc(l) を呼び出す。
n に右の子 r があれば Proc(r) を呼び出す。
n の記号を出力して終了する。
}
2分木: 根 + ，左の子 a，右の子 *。* の左の子 −，右の子 d。− の左の子 b，右の子 c。
答えを選ぶ
出典：基本情報技術者試験 科目A免除 修了試験 20161211 実施分 問5（問題文は IPA の公開問題。解説は当サイト作成）
解説に誤りを見つけたら、解説の誤りを報告してください。
答えと解説を見る
正解：ウ
覚える知識
2分木の巡回順序(帰りがけ順)
帰りがけ順は、左部分木、右部分木、節の順にたどる巡回方法で、結果は後置表記になる。
この問題で必要なこと
左の子、右の子の順に再帰してから自分の記号を出力する帰りがけ順(後行順)である。根+から abc−d*+ が得られる。
ひっかけ
行きがけ順(+a*−bcd)や通りがけ順(a+b−c*d)との混同。
この知識の出題：本試験系 1 回・免除試験 6 回（公開問題での観測値）。頻出知識ランキング455位（全1,254件中）。