二分探索木を作るキーの順番

二分探索木にキーを順に入れていったとき，図と同じ形の木ができる入れ方を見つける問題です。

キーは根から「小さければ左，大きければ右」へ進んで，空いている場所に置きます。

大事なのは「親のキーは子のキーより先に入れる」ことです。図では 12 が 10 の親，7 が 6 の親なので，12 は 10 より前，7 は 6 より前にないといけません。

• この条件で選択肢を見ると，10 が 12 より前にある②④と，6 が 7 より前にある③⑤は外れます
• 残った①で実際に木を作って確かめます。8 を根に置く
• 5：8 より小さいので 8 の左
• 7：8 より小さいので 5 へ。5 より大きいので 5 の右
• 12：8 より大きいので 8 の右
• 3：8 より小さいので 5 へ。5 より小さいので 5 の左
• 10：8 より大きいので 12 へ。12 より小さいので 12 の左
• 6：5 へ，7 へと進み，7 より小さいので 7 の左。図と同じ木になります。答えは ① 8，5，7，12，3，10，6

②・④（10 が 12 より前）：10 が先に 8 の右の子になり，12 はその右の子になって図と形が変わります。

③・⑤（6 が 7 より前）：6 が先に 5 の右の子になり，7 はその右の子になって図と形が変わります。

• 二分探索木：左の部分木のキーは親より小さく，右の部分木のキーは親より大きい
• キーを入れるときは，根から大小を比べて進み，空いている場所に置く
• 親のキーは子のキーより先に入れる。この順番が守られていれば同じ形の木になる