修了試験 2021-07-25実施分 基本情報技術者試験 問7

解説

正解は2です。 2分探索木は、どの節についても「左の部分木の値はすべてその節より小さく、右の部分木の値はすべて大きい」という条件を満たす2分木です。 親子の関係だけでなく、祖先との大小関係も満たす必要があります。 【選択肢別解説】 1：× 選択肢1（図のア）は根16の左の子が15で、その右の子が14です。 14は15の右側にあるのに15より小さいので、条件に反します。 2：○ 選択肢2（図のイ）は根17の左部分木が14・10・16で、すべて17より小さい値です。 14の左が10、右が16で、10＜14＜16も成り立ちます。 右部分木は19と18で、すべて17より大きく、18は19の左の子なので18＜19も満たしています。 3：× 選択肢3（図のウ）は根18の左の子が16で、その右の子が14です。 14は16の右側にあるのに16より小さいので、条件に反します。 4：× 選択肢4（図のエ）は根20の右の子が19で、20より小さい値が右側にあります。 左の子18の右の子14も18より小さく、条件に反します。 【ポイント】 2分探索木を中間順（左、節、右の順）でたどると、値が小さい順に並びます。 選択肢2（図のイ）を中間順にたどると10、14、16、17、18、19となり、昇順になることで確認できます。