平成26年度 春期 午前 問6
データ構造
2分木に関する問題
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
答えと解説を見る
✓ これが正解ウabc−d＊＋
解説
左と右を先に出し自分を最後に出す順です。
この手続は、まず左の子を処理し、次に右の子を処理し、最後に自分の記号を出力します。出力する行がいちばん後ろに置かれているので、どのノードも両方の子が済んでから字を出します。この順序を帰りがけ順と呼びます。判定の軸は一つで、自分を出力する位置が子の処理より前か、間か、後かという点だけです。図の 2 分木にこの順で当てると、左に下がった葉から出力が始まり、次に右側の枝の中をさらに左から下りていき、それぞれの親は子が出尽くした後に現れます。得られる並びは a b c − d ＊ ＋ となります。演算子が二つの項の後ろに置かれる形なので、後置記法そのものです。並びを後ろから組み立て直すと、もとの 2 分木が表している式に戻ります。
ほかの選択肢はなぜ違うのか
- ア＋a＊−bcd：自分の記号を先に出し、そのあとで左と右をたどった場合の並びです。演算子が二つの項の前に置かれる形になり、出力を最後の行に置いたこの手続とは順序が逆です。
- イa＋b−c＊d：左の子を出した後にいったん自分を出し、それから右の子へ進んだ場合の並びで、演算子が二つの項の間に来ます。手続には自分を途中で出す行が書かれていません。
- エb−c＊d＋a：演算子が項の間に置かれている点は途中まで似ていますが、いちばん上の記号が末尾ではなく途中に現れ、根に近い方の記号の位置も合いません。三つのどの順序をたどっても得られない並びです。
出典：平成26年度 春期 基本情報技術者試験 午前 問6（改変：原典の図表をテキストに書き起こした）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）