二分探索木

bst.go

package main

import "fmt"

type binaryTree struct {
	root *node
}

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

func (n *node) add(val int) {
	if val < n.value {
		if n.left != nil {
			n.left.add(val)
		} else {
			n.left = &node{value: val}
		}
	} else {
		if n.right != nil {
			n.right.add(val)
		} else {
			n.right = &node{value: val}
		}
	}
}

func (b *binaryTree) add(val int) {
	if b.root == nil {
		b.root = &node{value: val}
	} else {
		b.root.add(val)
	}
}

func (b *binaryTree) contains(t int) bool {
	n := b.root
	for {
		if t == n.value {
			return true
		} else if t < n.value {
			if n.left == nil {
				return false
			}
			n = n.left
		} else if t > n.value {
			if n.right == nil {
				return false
			}
			n = n.right
		}
	}
}

func main() {
	b := binaryTree{}
	b.add(5)
	b.add(13)
	b.add(3)
	fmt.Println(b.contains(13))
	fmt.Println(b.contains(4))
}