アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20200726 実施分 問7
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免除 修了試験 20200726 実施分 問7
答えと解説を見る
正解：ウ
覚える知識
2分木の巡回順序(帰りがけ順)
帰りがけ順は、左部分木、右部分木、節の順に訪問する巡回である。
この問題で必要なこと
左の子、右の子、自分の順に出力するので帰りがけ順（後行順）となり、abc−d*+を得る。
ひっかけ
行きがけ順（+a*−bcd）や通りがけ順（a+b−c*d）を選ばせる。
この知識の出題：本試験系 1 回・免除試験 6 回（公開問題での観測値）