各ノードがもつデータを出力する再帰処理f(ノードn)を定義した。この処理を、図の2分木の根(最上位のノード)から始めたときの出力はどれか。 〔f(ノードn)の定義〕 1. ノードnの右に子ノードrがあれば、f(ノードr)を実行 2. ノードnの左に子ノードlがあれば、f(ノードl)を実行 3. 再帰処理f(ノードr),f(ノードl)を未実行の子ノード、又は子ノードがなければ、ノード自身がもつデータを出力 4. 終了

選択肢

• ア+÷-ED×CBA
• イABC×DE-÷+
• ウE-D÷C×B+A
• エED-CB×÷A+

正解と解説

正解：エ ED-CB×÷A+

この再帰処理は「右の子→左の子→自分自身の出力」の順に処理する、後行順（帰りがけ順）の右優先版である。根+では、まず右部分木÷を処理し、その中でも右の-（E、D、-の順に出力）、次に左の×（C、B、×の順）、最後に÷を出力する。その後に左の子Aを出力し、最後に根の+を出力するので、全体はED-CB×÷A+となる。

選択肢ごとの解説

• ア自分自身を先に出力してから子に進む先行順（行きがけ順）の出力であり、定義の順序と異なる。
• イ左の子を先に処理する通常の後行順の出力で、右優先という条件を満たしていない。
• ウ根や部分木の値を子より先に出力しており、自分自身を最後に出力するという手順3に反する。
• エ正しい。右の子→左の子→自分自身の順に再帰した結果がED-CB×÷A+となる。

同じ分野の他の問題

• 図の2分探索木に1と0の二つの要素を順に追加したAVL木として，適切なものはどれか。2025年度 春期 午前 問6
• A，B，Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合，データ…2016年度 春期 午前 問5
• 次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで2分探索木を再構成するには、削除された要素の…2024年度 秋期 午前 問5
• 双方向リストを三つの一次元配列elem[i]、next[i]、prev[i]の組で実現する。双方向リストが図の状態のとき…2023年度 秋期 午前 問5
• 要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当て…2023年度 春期 午前 問5