修了試験 2018-06-10実施分 基本情報技術者試験 問5

解説

正解は3です。 図の2分木は、根が＋で、左の子がa、右の子が＊です。 ＊の左の子は－で、右の子はdです。 －の左の子はb、右の子はcです。 Proc(n)は「左の子を処理し、右の子を処理し、最後に自分の記号を出力する」ので、後行順（帰りがけ順、postorder）の走査になります。 【計算】 根の＋でProc(a)を呼び、葉のaを出力します。 次にProc(＊)を呼び、その中でProc(－)を呼びます。 Proc(－)ではb、cの順に出力し、最後に－を出力します。 Proc(＊)に戻ってdを出力し、続けて＊を出力します。 最後に根の＋を出力するので、出力はabc-d*+になります。 【選択肢別解説】 1：× +a*-bcdは、自分の記号を先に出力する先行順（行きがけ順）の結果です。 2：× a+b-c*dは、左の子、自分、右の子の順に出力する中間順（通りがけ順）の結果です。 3：○ 左、右、自分の順にたどった後行順の結果で、根の＋が最後に出力されています。 4：× b-c*d+aは右部分木を先にたどった並びで、根の＋も最後になっていません。 Proc(n)では根の記号は必ず最後に出力されます。 【ポイント】 演算式を表す2分木を後行順でたどると逆ポーランド表記、先行順でたどるとポーランド表記、中間順でたどると通常の中置記法になります。 「自分を出力するのが最初か、真ん中か、最後か」で3種類を区別しましょう。