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

解説

正解は2です。 2分探索木では、どの節についても、左部分木の値はすべてその節より小さく、右部分木の値はすべてその節より大きくなります。 図の4つの木について、この大小関係が崩れている節がないかを確かめます。 【選択肢別解説】 1：× 選択肢1（図のア）は根が1で、左の子が2、右の子が3です。 根の左側に1より大きい2、4、5があるので、2分探索木の条件を満たしません。 2：○ 選択肢2（図のイ）は根が4で、左部分木が2（子は1と3）、右部分木が8（子は6と9、6の子は5と7）です。 どの節でも左が小さく右が大きいので、条件を満たします。 3：× 選択肢3（図のウ）は根が7で、左の子6の右の子が5です。 5は6より小さいのに右側にあります。 さらに根7の右部分木に7より小さい3、1、2があるので誤りです。 4：× 選択肢4（図のエ）は根が9で、右の子が8です。 9より小さい8が右側にあり、左の子7の右側にも7より小さい2があるので誤りです。 【ポイント】 2分探索木を中間順（左、節、右の順）にたどると、値が昇順に並びます。 選択肢2を中間順にたどると1から9の順に並ぶので、これでも確認できます。