修了試験 2015-12-20実施分 基本情報技術者試験 問5

解説

正解は2です。 2分探索木は、どの節でも「左部分木の値＜節の値＜右部分木の値」が成り立つ2分木です。 根だけでなく、すべての節でこの大小関係を確かめます。 【選択肢別解説】 1：× 選択肢1（図のア）は根が1で、左の子に2があります。 左部分木には根より小さい値が入るはずなので、1より大きい2が左にある時点で条件を満たしません。 2：○ 選択肢2（図のイ）は根4の左に2、右に8があります。 2の左右は1と3、8の左右は6と9、6の左右は5と7です。 どの節でも左が小さく右が大きく、通りがけ順にたどると1から9の昇順に並びます。 3：× 選択肢3（図のウ）は根7の右部分木に8があり、8の左の子が3です。 3は根7の右部分木にあるのに7より小さいので、条件を満たしません。 また、6の右の子の5も6より小さく誤りです。 4：× 選択肢4（図のエ）は根9の右の子が8です。 右部分木には9より大きい値が入るはずなので、8が右にある時点で条件を満たしません。 【ポイント】 2分探索木を通りがけ順（中間順）で走査すると、値が昇順に並びます。 親子だけでなく、部分木全体と祖先の値の関係も確認するのがコツです。