令和6年度 春期 応用情報技術者試験 午前 問6
テクノロジ／アルゴリズム各ノードがもつデータを出力する再帰処理 f(ノード n) を定義した。この処理を，図の2分木の根（最上位のノード）から始めたときの出力はどれか。 〔f(ノード n) の定義〕 1. ノード n の右に子ノード r があれば，f(ノード r) を実行 2. ノード n の左に子ノード l があれば，f(ノード l) を実行 3. 再帰処理 f(ノード r)，f(ノード l) を未実行の子ノード，又は子ノードがなければ，ノード自身がもつデータを出力 4. 終了
出典：令和6年度 春期 応用情報技術者試験 午前 問6
- ア＋÷−ED×CBA
- イABC×DE−÷＋
- ウE−D÷C×B＋A
- エED−CB×÷A＋
正解：エ
解説
f(n)の定義は「右の子があればf(右)を実行→左の子があればf(左)を実行→両方について再帰未実行（子がない）ならば自身を出力」という，右部分木・左部分木・自分自身の順に処理する走査です。図の木は根+，左A，右÷で，÷の左×（左B，右C），右−（左D，右E）という構成です。根からf(＋)を呼ぶと，右部分木÷側を先にすべて処理してから左のAを出力し，最後に＋自身を出力します。÷側では右の−部分木（右Eを出力，左Dを出力，−自身を出力）を先に処理し，続いて左の×部分木（右Cを出力，左Bを出力，×自身を出力）を処理し，最後に÷自身を出力します。まとめると E，D，−，C，B，×，÷，A，＋ の順になり，選択肢の「ED−CB×÷A＋」と一致します。
選択肢ごとの解説
- ア誤り。これは自分自身を先に出力してから右・左の順に再帰する走査（根を先頭に出す前順型）をした場合の出力です。
- イ誤り。これは左の子を先に処理する通常の後順走査（左→右→自分）をした場合の出力（A B C×D E−÷＋）で，本問の定義（右→左→自分）とは逆になっています。
- ウ誤り。これは右部分木→自分自身→左部分木の順（中間順走査を左右反転したもの）で出力した場合の結果で，自分自身の出力位置を子の処理の間に置き違えています。
- エ正しい。右部分木，左部分木，自分自身の順に処理する定義どおりに走査すると，ED−CB×÷A＋の順で出力されます。