令和6年度 春期 高度試験共通 午前I 問3

各選択肢の解説

ア

+÷−ED×CBA

誤りです。+÷−ED×CBAは、各ノードでまず自身を出力し、その後に右、左の順で子をたどる前順の出力です。定義の手順3では、右と左の子の処理を終えた後、又は子がない場合に初めて自身を出力します。そのため根の+は先頭ではなく、最後に出力されます。

イ

ABC×DE−÷+

誤りです。ABC×DE−÷+は、左の子を先に処理する後順（左→右→自身）の出力です。定義では手順1で右の子を先に実行するので、f(+)はまず右の÷の部分木に進みます。根の左の子Aは、÷の部分木をすべて出力した後でなければ出力されず、先頭には来ません。

ウ

E−D÷C×B+A

誤りです。E−D÷C×B+Aは、右→自身→左の順にたどる中順の出力です。定義では、−は右の子Eと左の子Dの両方を処理し終えてから出力されます。そのためE、D、−の順になり、演算子が子の間に入る並びにはなりません。

エ

ED−CB×÷A+

正しいです。図の木は、+の左がA・右が÷、÷の左が×・右が−です。f(+)は右の÷へ、f(÷)は右の−へ進みます。f(−)では右のE、左のDを出力してから−を出力します。次に÷の左の×でC、B、×を出力し、続けて÷を出力します。最後に+の左のAを出力し、+を出力するので、結果はED−CB×÷A+です。