2分木の根から始めた場合の出力｜科目A-1（応用情報技術者） 令和6年 春期午前試験 問6
出典：令和6年春期 午前 問6
分野：アルゴリズムとプログラミング ／ アルゴリズム
各ノードがもつデータを出力する再帰処理 f（ノードn）を定義した。この処理を，図の2分木の根（最上位のノード）から始めたときの出力はどれか。
〔f（ノードn）の定義〕
- ノードnの右に子ノードrがあれば，f（ノードr）を実行
- ノードnの左に子ノードlがあれば，f（ノードl）を実行
- 再帰処理 f（ノードr），f（ノードl） を未実行の子ノード，又は子ノードがなければ，ノード自身がもつデータを出力
- 終了
- ア：+ ÷ - E D × C B A
- イ：A B C × D E - ÷ +
- ウ：E - D + C × B + A
- エ：E D - C B × ÷ A +
TSUNAGARU-ADVICE
まず押さえたいこと
この再帰処理では、各ノードについて右の子 → 左の子 → 自分自身の順に処理します。したがって、根から始めて、まず右部分木を最後までたどり、その後に左部分木をたどってから根のデータを出力します。
迷ったときの判断軸
再帰処理では、子ノードがあるとその処理が完了するまで親ノードには戻りません。右部分木でも同じ規則を繰り返すため、「右を深くたどる → 左をたどる → 親を出力する」という順序を各ノードで機械的に適用すると、出力順を整理しやすくなります。
科目Bにつなげるために
特にプロフェッショナルデジタルスキル（システム）試験合格を目指す方は、再帰処理を二分木の走査順序とスタックの動作に結び付けて理解しましょう。前順・中順・後順走査の変形や、再帰呼出しの戻り順を追う問題にも応用できます。
手順1 → 2 → 3の流れを見ると、f（ノードn）は「右の子 → 左の子 → 自分自身」の順でノードをたどっていきます。
子ノードを先に処理し、最後に自分自身を出力するので、後行順（帰りがけ順）の深さ優先探索です。ただし、一般的な「左 → 右 → 中」ではなく、この問題では「右 → 左 → 中」の順になっています。
根ノード「 + 」から実行すると、次のように処理が進みます。
f（ + ）：右の子があるのでf（ ÷ ）を実行します。
f（ ÷ ）：右の子があるのでf（ - ）を実行します。
f（ - ）：右の子があるのでf（E）を実行します。
f（E）：子ノードがないので、Eを出力します。
f（ - ）に戻り、左の子があるのでf（D）を実行します。
f（D）：子ノードがないので、Dを出力します。
f（ - ）に戻ると左右の子は処理済みなので、自分自身の「 - 」を出力します。ここまでの出力は、
E D -
となります。
次にf（ ÷ ）へ戻り、左の子であるf（ × ）を実行します。
f（ × ）：右の子があるのでf（C）を実行し、Cを出力します。
f（×）に戻り、左の子であるf（B）を実行し、Bを出力します。
左右の子の処理が終わったので、「 × 」を出力します。
f（ ÷ ）に戻ると左右の子は処理済みなので、「 ÷ 」を出力します。ここまでで、
E D - C B × ÷
となります。
最後にf（ + ）へ戻り、左の子であるf（A）を実行してAを出力し、その後に根ノード自身の「 + 」を出力します。
したがって、最終的な出力は、
E D - C B × ÷ A +
となります。
したがって、エが適切です。