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

解説

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