2分木の各ノードがもつ記号を出力する再帰的なプログラムProc(n)の定義は，次のとおりである。
このプログラムを，図の2分木の根（最上位のノード）に適用したときの出力はどれか。
Proc(n) {
nに左の子lがあればProc(l)を呼び出す。
nに右の子rがあればProc(r)を呼び出す。
nの記号を出力して終了する。
}
正答3
解説
正解は3です。
2分木の走査順序を問う問題です。
図の2分木は、根が「＋」で、左の子が「a」、右の子が「＊」です。
「＊」の左の子は「－」、右の子は「d」で、「－」の左の子は「b」、右の子は「c」です。
Proc(n)は、左の子、右の子、自分自身の順に処理するので、後行順（帰りがけ順）の走査です。
【選択肢別解説】
1：× 「＋a＊－bcd」は、自分自身を先に出力してから左、右の順に処理する先行順（行きがけ順）の結果です。
Proc(n)は自分の記号を最後に出力するので、先頭が根の「＋」にはなりません。
2：× 「a＋b－c＊d」は、左の子、自分自身、右の子の順に処理する中間順（通りがけ順）の結果です。
Proc(n)の処理順とは異なります。
3：○ 根でまず左の子「a」を処理し、「a」を出力します。
次に右の子「＊」の処理で、左の子「－」から「b」「c」「－」を出力します。
続いて「d」を出力し、最後に「＊」を出力します。
最後に根の「＋」を出力するので、「abc－d＊＋」になります。
4：× 根の左の子「a」には子がないので、最初に出力されるのは「a」です。
「b」から始まる出力にはなりません。
【ポイント】
この木は数式「a＋(b－c)＊d」を表しています。
後行順で走査すると逆ポーランド記法になり、先行順ではポーランド記法になります。