修了試験 2018-01-28実施分 基本情報技術者試験 問5

解説

正解は2です。 2分探索木の条件を満たす木を、図の4つから選ぶ問題です。 2分探索木では、どの節についても、左の部分木の値はすべてその節より小さく、右の部分木の値はすべてその節より大きくなります。 【選択肢別解説】 1：× 選択肢1（図のア）は、根16の左の子が15で、15の左の子が10、右の子が14です。 15の右の子は15より大きくなければなりませんが、14は15より小さいので条件に反します。 2：○ 選択肢2（図のイ）は、根17の左の子が14（その子は左が10、右が16）、右の子が19（その左の子が18）です。 左の部分木の10、14、16はすべて17より小さく、右の部分木の18、19はすべて17より大きくなっています。 14に対して10は小さく16は大きく、19に対して18は小さいので、すべての節で条件を満たします。 3：× 選択肢3（図のウ）は、根18の左の子16の右の子が14です。 16の右の子は16より大きくなければならないので、条件に反します。 4：× 選択肢4（図のエ）は、根20の右の部分木に19、15、16があり、いずれも20より小さいので条件に反します。 左の子18の右の子が14である点も誤りです。 【ポイント】 2分探索木を中間順（左の部分木、節、右の部分木の順）でたどると、値が昇順に並びます。 選択肢2（図のイ）を中間順でたどると10、14、16、17、18、19と昇順になるので、確認に使えます。