package main
import (
"fmt"
)
type IntTree struct {
val int
left, right *IntTree
}
// valをitに挿入する
func (it *IntTree) Insert(val int) *IntTree {
if it == nil {
return &IntTree{val: val}
}
if val < it.val {
it.left = it.left.Insert(val)
} else if val > it.val {
it.right = it.right.Insert(val)
}
return it
}
// valがitに含まれるかをチェックし論理値を返す
func (it *IntTree) Contains(val int) bool {
switch {
case it == nil:
return false
case val < it.val:
return it.left.Contains(val)
case val > it.val:
return it.right.Contains(val)
default:
return true
}
}
func main() {
var it *IntTree
it = it.Insert(5)
it = it.Insert(3)
it = it.Insert(10)
it = it.Insert(2)
fmt.Println(it.Contains(2)) // true
fmt.Println(it.Contains(12)) // false
}
type IntTree struct { //liststart1
val int
left, right *IntTree
}
-
IntTreeという構造体を定義します。この構造体は、整数の値（val）と、左と右の子ノード（leftとright）を持っています。これにより、二分探索木（BST）を表現します。
// valをitに挿入する
func (it *IntTree) Insert(val int) *IntTree {
-
Insertメソッドを定義します。このメソッドは、整数valを木に挿入するためのものです。itはIntTreeのポインタです。
if it == nil {
return &IntTree{val: val}
}
-
itがnilの場合、新しいIntTreeのインスタンスを作成し、valをその値に設定して返します。
if val < it.val {
it.left = it.left.Insert(val)
} else if val > it.val {
it.right = it.right.Insert(val)
}
-
valが現在のノードの値より小さい場合、左の子ノードに対してInsertを再帰的に呼び出します。逆に、大きい場合は右の子ノードに対して呼び出します。
return it
}
- 最後に、現在のノード（
it）を返します。これにより、木全体の構造が保持されます。
// valがitに含まれるかをチェックし論理値を返す
func (it *IntTree) Contains(val int) bool {
-
Containsメソッドを定義します。このメソッドは、整数valが木に存在するかどうかをチェックします。
switch {
case it == nil:
return false
-
itがnilの場合、木に値は含まれないのでfalseを返します。
case val < it.val:
return it.left.Contains(val)
-
valが現在のノードの値より小さい場合、左の子ノードに対してContainsを再帰的に呼び出します。
case val > it.val:
return it.right.Contains(val)
-
valが現在のノードの値より大きい場合、右の子ノードに対してContainsを再帰的に呼び出します。
default:
return true
}
-
valが現在のノードの値と等しい場合、木に値が含まれているのでtrueを返します。
func main() { //liststart2
-
main関数を定義します。プログラムのエントリーポイントです。
var it *IntTree
-
IntTreeのポインタitを宣言しますが、まだ初期化はされていません。
it = it.Insert(5)
-
5を木に挿入し、その結果をitに再代入します。最初のノードが作成されます。
it = it.Insert(3)
-
3を木に挿入します。3は5より小さいので、左の子ノードとして追加されます。
it = it.Insert(10)
-
10を木に挿入します。10は5より大きいため、右の子ノードとして追加されます。
it = it.Insert(2)
-
2を木に挿入します。2は5より小さく、さらに3よりも小さいので、3の左に追加されます。
fmt.Println(it.Contains(2)) // true
-
2が木に含まれているかをチェックし、結果を出力します。trueが出力されます。
fmt.Println(it.Contains(12)) // false
IntTreeがどのように構築されるか
初期状態
最初は、itはnilです。
var it *IntTree
it = it.Insert(5)
-
itがnilなので、Insertメソッドは新しいIntTreeインスタンスを作成します。 -
valは5です。 - 新しいノードが作成され、
5がその値になります。 -
itはこの新しいノードを指すようになります。
5
/ \
nil nil
it = it.Insert(3)
- 現在のノードは
5です。 -
3 < 5なので、左の子ノードに挿入します。 - 左の子ノードは
nilなので、Insertメソッドは新しいノードを作成します。 -
valは3です。 - 新しいノードが作成され、
3がその値になります。
5
/ \
3 nil
/ \
nil nil
it = it.Insert(10)
- 現在のノードは
5です。 -
10 > 5なので、右の子ノードに挿入します。 - 右の子ノードは
nilなので、Insertメソッドは新しいノードを作成します。 -
valは10です。 - 新しいノードが作成され、
10がその値になります。
5
/ \
3 10
/ \ / \
nil nil nil
it = it.Insert(2)
- 現在のノードは
5です。 -
2 < 5なので、左の子ノード（3）に進みます。 - 現在のノードは
3です。 -
2 < 3なので、左の子ノードに挿入します。 - 左の子ノードは
nilなので、Insertメソッドは新しいノードを作成します。 -
valは2です。 - 新しいノードが作成され、
2がその値になります。
5
/ \
3 10
/ \ / \
2 nil nil
/ \
nil nil
最終的な木の構造
全ての挿入操作が完了した後、最終的な二分探索木の構造は次のようになります。
5
/ \
3 10
/ \
2 nil
/ \
nil nil
結果
-
5がルートノード。 -
3が5の左の子ノード。 -
10が5の右の子ノード。 -
2が3の左の子ノード。