golangで2分木

tree.go

// http://play.golang.org/p/dB_zEZf_Rz

package main

import "fmt"

type TreeNode struct {
	value int
	left  *TreeNode
	right *TreeNode
}

type Tree struct {
	root *TreeNode
}

func (tree *Tree) LeftTree() *Tree {
	return &Tree{tree.root.left}
}

func (tree *Tree) RightTree() *Tree {
	return &Tree{tree.root.right}
}

func (tree *Tree) Contains(value int) bool {
	if (tree.root == nil) {
		return false
	} else if (tree.root.value == value) {
		return true
	} else if (value > tree.root.value) {
		return tree.RightTree().Contains(value)
	} else {
		return tree.LeftTree().Contains(value)
	}
}

func (tree *Tree) Insert(value int) *Tree {
	if (tree.root.value <= value) {
		if (tree.root.right != nil) {
			tree.RightTree().Insert(value)
		} else {
			tree.root.right = &TreeNode{value, nil, nil}
		}
	} else {
		if (tree.root.left != nil) {
			tree.LeftTree().Insert(value)
		} else {
			tree.root.left = &TreeNode{value, nil, nil}
		}
	}
	return tree
}

func main() {
	n4 := &TreeNode{4, nil, nil}
	n7 := &TreeNode{7, nil, nil}
	n9 := &TreeNode{9, nil, nil}
	n8 := &TreeNode{8, n7, n9}
	n5 := &TreeNode{5, n4, n8}
	tree := &Tree{n5}


	tree.Insert(3).Insert(10)

	for i := 1; i <= 10; i++ {
		fmt.Println(i, tree.Contains(i))
	}
}