構造を学習、ノードをドラッグ「二分探索木 ゲーム編」公開
こんばんは。えいたです。
「二分探索木 シミュレーション編」の補助教材を制作しました。
二分探索木を成立させるため、構造を満たす必要があります。
左(子)のノード < 中央(親)のノード < 右(子)のノード
構造をゲーム感覚で学習、ノードをドラッグして下さい。
木構造を視覚化
問題：空白の木に数値を記入して、二分探索木を完成して下さい。
とりあえず、回答例を示します。
- 左下の木に着目：５ ＞ ６ ＞ １３
- 中央の木に着目：１４ ＞ ４５ ＞ ８８
- 右下の木に着目：９０ ＞ ９３ ＞ ９５
その他の木を含めて、構造を満たしています。
５ ＞ ６ ＞ １３ ＞ １４ ＞ ３３ ＞ ３４ ＞ ４２ ＞ ４５ ＞ ５０ ＞ ５１ ＞ ８６ ＞ ８８ ＞ ９０ ＞ ９３ ＞ ９５
４２を探索する場合は、下記の関係が成立します。
４５より小さい、１４より大きい、３４より大きい
つまり、４２は「３４～４５」の間に存在する数値です。
- ３５～４１を挿入：４２の左側
- ４３～４４を挿入：４２の右側
二分探索木の座学終了、再帰的思考がポイント！
「二分探索木 ゲーム編」で学ぶ
「二分探索木 ゲーム編」について
ルール
ノード(ボール型)をドラッグして、二分探索木の完成を目指します。
右上にノードが１５個、数値(１～９９)はランダムです。
①とりあえず、ノードを中央に配置しました。
②二分探索木の構造に従い「左側に小さい数値、右側に大きい数値」を配置しました。
③線の色により、二分探索木の状態が確認できます。
- 青色線：ノード間について、構造が正解
- 赤色点線：ノード間について、構造が不正解
つまり、二分探索木の完成は青色線のみになります。
画面構成
初期化ボタン：ノードを右上に配置、数値はランダムで変更します。
判定ボタン：ノードの場所について、判定します。
ノードを青色で囲む：正解、ノードを赤色で囲む：不正解
上記は赤色点線が無し、二分探索木の構造は満たしています。
不正解の理由：３９より５６の方が、大きい場所に配置する必要あり！
操作方法
空白の木にノードをドラッグして下さい。
さいごに
「二分探索木の構造について、理解できたかな？」
３段目まで左右の子がある場合を示します。
１つのノードに着目した時、以下の関係が成立！
- 左側：小さいノードの集合体
- 右側：大きいノードの集合体
ドラッグするだけの教材ですが、二分探索木の構造を学習して下さい。
他のゲームも遊んで下さいね。