基本情報技術者 2014年 春期 午前（科目A） 問06

二分木の走査と演算子記号出力【午前解説】

正解の理由

解法ステップ

1. Proc(n) の擬似コードを読み、出力の順序を確認する（左呼び出し → 右呼び出し → 出力）。
2. それが後順（post-order）であると判断する。
3. 木の根から開始し、再帰的に左部分木をすべてたどり出力を記録する（ここでは a）。
4. 次に右部分木に移り、さらにその左部分木を先に処理して b, c, - の順で出力する。
5. 右部分木の右葉 d を出力し、部分木の根 * を出力する。
6. 最後に木全体の根 + を出力し、出力列を連結して abc-d*+ を得る。

選択肢別の誤答解説

• ア: +a*-bcd
  • 説明: これは親を先に出力する前順（pre-order）に相当します。Proc の出力順は親を最後に出すため不適合です。
• イ: a+b-c*d
  • 説明: これは中順（in-order）で、左→親→右の順で出力した場合に得られる表現です。Proc は親を最後に出すので異なります。
• ウ: abc-d*+
  • 説明: 正解。後順（left, right, root）で処理した結果、葉から順に a → b → c → - → d → * → + となります。
• エ: b-c*d+a
  • 説明: これは木構造のたどり方や出力順が混同された誤答です。特定の部分木だけ先に出す順序になっており、Proc の明示的な左→右→親の順序とは一致しません。

よくある誤解

• 「左→親→右（中順）」や「親→左→右（前順）」と混同すること。再帰呼び出しと出力位置を見れば区別できます。
• 図の左右を逆に読む（右を先に処理）してしまい順序が入れ替わる誤り。常に左を先にたどることを確認してください。
• 演算子を見て算術式の優先順位で並べ替える（中置表記を想像する）と、出力順の判定を誤ることがあります。

補足コラム

• 後順（post-order）巡回は式木（演算子ノードを内部、オペランドを葉に置く木）に対して後置記法（逆ポーランド記法、RPN）を生成します。得られた abc-d*+ をスタックで評価すれば式の値を求められます。
• 試験対策としては、ノードを読む順序をコードから確実に引き出す練習を繰り返すことが重要です。「再帰呼出の順番」と「出力するタイミング（呼ぶ前か後か）」をチェックしましょう。

FAQ