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の左の子ノード。