平成26年度 春期 午前 問6

✓ これが正解ウabc−d＊＋

解説

左と右を先に出し自分を最後に出す順です。

この手続は、まず左の子を処理し、次に右の子を処理し、最後に自分の記号を出力します。出力する行がいちばん後ろに置かれているので、どのノードも両方の子が済んでから字を出します。この順序を帰りがけ順と呼びます。判定の軸は一つで、自分を出力する位置が子の処理より前か、間か、後かという点だけです。図の 2 分木にこの順で当てると、左に下がった葉から出力が始まり、次に右側の枝の中をさらに左から下りていき、それぞれの親は子が出尽くした後に現れます。得られる並びは a b c − d ＊ ＋ となります。演算子が二つの項の後ろに置かれる形なので、後置記法そのものです。並びを後ろから組み立て直すと、もとの 2 分木が表している式に戻ります。

ほかの選択肢はなぜ違うのか

• ア＋a＊−bcd：自分の記号を先に出し、そのあとで左と右をたどった場合の並びです。演算子が二つの項の前に置かれる形になり、出力を最後の行に置いたこの手続とは順序が逆です。
• イa＋b−c＊d：左の子を出した後にいったん自分を出し、それから右の子へ進んだ場合の並びで、演算子が二つの項の間に来ます。手続には自分を途中で出す行が書かれていません。
• エb−c＊d＋a：演算子が項の間に置かれている点は途中まで似ていますが、いちばん上の記号が末尾ではなく途中に現れ、根に近い方の記号の位置も合いません。三つのどの順序をたどっても得られない並びです。