4-20. 2分木探索における再帰的なプログラムの出力結果

　本記事では、2分木探索における再帰的なプログラムの出力結果を求める問題演習をします。本問題は、基本情報技術者試験レベルです。

問題　2分木の各ノードがもつ記号を出力する再帰的なプログラム Proc(n) の定義は、次のとおりです。このプログラムを、図の2分木の根（最上位のノード）に適用した時の出力はどれですか。
　Proc(n) {
　　n に左の子l があればProc(l) を呼び出す。
　　n に右の子r があればProc(r) を呼び出す。
　　n の記号を出力して終了する。
　}

図1. 本問題における2分探索木

選択肢

ア　+a*-dcb
イ　a+b-c*d
ウ　abc-d*+
エ　b-c*d+a

解説

再帰プログラムとは《recursive program》（goo 辞書）

　コンピューターのプログラムを実行中に、あるルーチンが自分自身を呼び出して実行すること。→再帰呼び出し

再帰呼び出しとは《recursive call》（goo 辞書）

　プログラミング技法の一。コンピューターのプログラムを実行中に、あるルーチンや関数が自分自身を呼び出して実行すること。無限に自分自身を呼び出さないよう、正常に機能させる手続きを必要とする。階乗やフィボナッチ数列の計算などに利用される。リカーシブコール。

　2分木の探索法としては、先行順探索（親ノード → 左ノード → 右ノード）、中間順探索（左ノード → 右ノード → 親ノード）、後行順探索（左ノード → 右ノード → 親ノード）がありますが、この問題では後行順探索におけるトレース能力が問われています。
　後行順探索によって探索を行うと、a , b , - , c, *, d, + の順番になります。 よって、（ウ）が正解です。

以上です。