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