修了試験 2020-07-26実施分 基本情報技術者試験 問7

解説

正解は3です。 2分木を後行順（帰りがけ順）でたどる問題です。 Proc(n)は、左の子、右の子の順に処理してから、自分の記号を出力します。 図の2分木では、根が＋で、その左の子がa、右の子が＊です。 ＊の左の子が－、右の子がdで、－の左の子がb、右の子がcです。 【たどる手順】 根の＋に適用すると、まず左の子aを処理します。 aには子がないので、aを出力します。 次に、右の子＊を処理します。 ＊の左の子－を処理すると、bとcを順に出力し、続いて－を出力します。 ＊の右の子dを出力し、その後に＊を出力します。 最後に根の＋を出力します。 出力は、abc－d＊＋となります。 【選択肢別解説】 1：× ＋a＊－bcdは、自分を先に出力してから子をたどる先行順（行きがけ順）の結果です。 2：× a＋b－c＊dは、左の子、自分、右の子の順に出力する中間順（通りがけ順）の結果です。 3：○ 左の子、右の子、自分の順に出力する後行順の結果で、Proc(n)の定義と一致します。 4：× b－c＊d＋aは、どのたどり方とも一致しません。 後行順では、根の左の子であるaが最初に出力されます。 【ポイント】 数式を表す木を後行順でたどると、後置記法（逆ポーランド記法）の式が得られます。 abc－d＊＋は、a＋(b－c)＊dを後置記法で表したものです。