正答4
解説
正解は4です。
この問題は、2分探索木へのデータの挿入手順を問うています。
2分探索木では、各節より小さい値を左の部分木に、大きい値を右の部分木に置きます。
新しいデータは根から比較を始め、空いている位置に葉として追加します。
【計算】
最初の8が根になります。
12は8より大きいので、8の右の子になります。
5は8より小さいので、8の左の子になります。
3は8より小さく5より小さいので、5の左の子になります。
10は8より大きく12より小さいので、12の左の子になります。
7は8より小さく5より大きいので、5の右の子になります。
6は8より小さく、5より大きく、7より小さいので、7の左の子になります。
【選択肢別解説】
1：× 選択肢1（図のア）は、8の右の子が10で、10の子が7と12になっています。
12は10より先に挿入されるので、8の右の子は12でなければなりません。
また、7は8より小さいので右の部分木には入りません。
2：× 選択肢2（図のイ）は、左の部分木は正しいですが、8の右の子が10、その右の子が12になっています。
先に挿入された12が8の右の子になるので誤りです。
3：× 選択肢3（図のウ）は、7が3の右の子になり、6が5の右の子になっています。
7は5より大きいので5の右側に入り、6はその7の左の子になるのが正しい形です。
4：○ 選択肢4（図のエ）は、根8の左に5（左の子3、右の子7、7の左の子6）、右に12（左の子10）という形です。
挿入手順をたどった結果と完全に一致します。
【ポイント】
2分探索木の形は、データを挿入する順序によって決まります。
先に挿入されたデータほど根に近い位置に置かれることを押さえておきましょう。