2 分木の再帰処理の出力順
出典: 令和6年度 春期 応用情報技術者試験 午前 問6 (IPA)
各ノードがもつデータを出力する再帰処理 f(ノード n) を定義した。この処理を，図の 2 分木の根（最上位のノード）から始めたときの出力はどれか。
〔f(ノード n) の定義〕
- ノード n の右に子ノード r があれば，f(ノード r) を実行
- ノード n の左に子ノード l があれば，f(ノード l) を実行
- 再帰処理 f(ノード r)，f(ノード l) を未実行の子ノード，又は子ノードがなければ，ノード自身がもつデータを出力
- 終了
- ア ＋÷－ED×CBA
- イ ABC×DE－÷＋
- ウ E－D÷C×B＋A
- エ ED－CB×÷A＋
正解と解説を見る
正解: エ
- ア: 根から行きがけ順 (自分 → 子) でたどった出力に似た形で、この再帰処理の順序とは合いません。
- イ: 左 → 右 → 自分 (通常の後置順) の出力です。この処理は右の子を先に処理します。
- ウ: 中間順 (左 → 自分 → 右) の出力です。この処理は自分を最後に出力します。
- エ: 右の子 → 左の子 → 自分の順で出力した結果で、ED－CB×÷A＋ になります。正しい答えです。
ポイント
f は「右の子 → 左の子 → 自分」の順に処理します (右から見た後置順)。
- 根 (＋) では、まず右の子 (÷) の f を実行します。
- ÷ では、右の子 (−) → 左の子 (×) → ÷ の順です。
- − は E, D, − の順 (右の子 E → 左の子 D → 自分)、× は C, B, × の順に出力します。
- これらをつなぐと E D − C B × ÷ となり、最後に左の子 A、自分の ＋ を出力して ED－CB×÷A＋ になります。