応用情報技術者 2024年春期午前2 問06

問題文

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

選択肢

ア：+÷-ED×CBA

イ：ABC×DE-÷+

ウ：E-D÷C×B+A

エ：ED-CB×÷A+（正解）

各ノードがもつデータを出力する再帰処理f(ノードn)の出力【午前2 解説】

要点まとめ

結論：再帰処理は「右→左→自身」の順で出力し、正解はエの「ED-CB×÷A+」です。
根拠：処理は右子ノードを先に再帰呼び出し、次に左子ノードを再帰呼び出し、最後に自身のデータを出力します。
差がつくポイント：左右の子ノードの呼び出し順序を間違えず、出力タイミングを正確に理解することが重要です。

正解の理由

この再帰処理は、ノードの右子を先に処理し、次に左子を処理し、最後に自身のデータを出力します。
根ノード「＋」から始めると、まず右子「÷」を処理。
「÷」の右子「−」はさらに右子「E」、左子「D」を処理し、最後に「−」を出力。
次に「÷」の左子「×」は右子「C」、左子「B」を処理し、最後に「×」を出力。
「÷」の処理が終わった後、左子「A」を処理し、最後に「＋」を出力。
これにより「ED-CB×÷A+」の順で出力され、選択肢エが正解です。

よくある誤解

左右の子ノードの処理順を「左→右」と誤認しやすい。
出力タイミングを「子ノード処理前」にしてしまう誤りが多い。

解法ステップ

根ノード「＋」から処理開始。
右子ノード「÷」を再帰呼び出し。
「÷」の右子「−」を再帰呼び出し。
「−」の右子「E」を再帰呼び出し（子なしなので「E」を出力）。
「−」の左子「D」を再帰呼び出し（子なしなので「D」を出力）。
「−」自身を出力。
「÷」の左子「×」を再帰呼び出し。
「×」の右子「C」を再帰呼び出し（子なしなので「C」を出力）。
「×」の左子「B」を再帰呼び出し（子なしなので「B」を出力）。
「×」自身を出力。
「÷」自身を出力。
左子ノード「A」を再帰呼び出し（子なしなので「A」を出力）。
根ノード「＋」を出力。

選択肢別の誤答解説

ア: 「+÷-ED×CBA」→ 根ノードを先に出力しており、処理順序が逆。
イ: 「ABC×DE-÷+」→ 左子を先に処理しており、右子優先の条件に反する。
ウ: 「E-D÷C×B+A」→ 出力順が混乱しており、右子・左子の順序が守られていない。
エ: 「ED-CB×÷A+」→ 正しい右→左→自身の順で出力されている。

補足コラム

この問題は二分木の再帰処理の理解を問う典型例です。
一般的な二分木の走査法には「前順（根→左→右）」「中順（左→根→右）」「後順（左→右→根）」がありますが、今回の処理は「右→左→根」の特殊な後順走査に相当します。
再帰の呼び出し順と出力タイミングを正確に把握することが重要です。

FAQ

Q: なぜ左子より右子を先に処理するのですか？
A: 問題文の処理定義で「右に子ノードがあれば先に処理」と明示されているためです。

Q: 出力はいつ行うのが正しいですか？
A: 子ノードの再帰処理が完了した後、つまり「右→左」の両方の処理が終わってから自身のデータを出力します。

Q: この処理はどの走査法に近いですか？
A: 通常の後順走査（左→右→根）とは異なり、「右→左→根」の順で処理する特殊な後順走査です。

関連キーワード: 二分木、再帰処理、木構造、深さ優先探索、走査順序、データ構造

← 前の問題へ次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！

応用情報技術者 2024年 春期 午前2 問06

問題文

選択肢