平成26年度 春期 基本情報技術者試験 午前 問6
テクノロジ／アルゴリズム2分木の各ノードがもつ記号を出力する再帰的なプログラム Proc(n) の定義は，次のとおりである。このプログラムを，図の2分木の根（最上位のノード）に適用したときの出力はどれか。 Proc(n) { n に左の子 l があれば Proc(l) を呼び出す。 n に右の子 r があれば Proc(r) を呼び出す。 n の記号を出力して終了する。 }
出典：平成26年度 春期 基本情報技術者試験 午前 問6
- ア+a*-bcd
- イa+b-c*d
- ウabc-d*+
- エb-c*d+a
正解：ウ
解説
Proc(n)は，まず左の子があればそちらを先に再帰呼出しし，次に右の子があれば再帰呼出しし，最後に自分の記号を出力するという「後行順（帰りがけ順）」の走査です。図の木では，根「+」から見て，左部分木は「a」のみ（そのままaを出力），右部分木「*」はさらに左の「-」（左a=b，右c，自身-の順でb,c,-の順）と右の「d」を処理してから自身「*」を出力するため，右部分木全体ではb,c,-,dの順に処理し最後に*を出力してb c - d *（=bc-d*）となります。全体では，根の左部分木a，右部分木bc-d*，最後に根自身+を出力するので，a bc-d* + すなわち「abc-d*+」の順で出力されます。
選択肢ごとの解説
- ア誤り。この順序は前行順（行きがけ順）でルートを先に出力した場合の並びに近く，後行順の定義とは一致しません。
- イ誤り。中間順（間順）で走査した場合の並びに相当し，後行順の定義とは異なります。
- ウ正しい。左部分木a，右部分木の左b，右c，右部分木の根-，右部分木の右d，右部分木の根*，最後に根+の順に出力され，abc-d*+になります。
- エ誤り。これは右部分木を先に処理してから左部分木を処理した場合に近い並びであり，定義された左優先の後行順とは異なります。