###### tags: `Golang` `算法` `資料結構`

# Binary SearchTree


package binarysearchtree

type BinarySearchTree struct {
	left  *BinarySearchTree
	data  int
	right *BinarySearchTree
}

func NewBst(i int) *BinarySearchTree {
	return &BinarySearchTree{data: i}
}

func (bst *BinarySearchTree) Insert(i int) {
	switch {
        case i <= bst.data && bst.left == nil:
    		bst.left = &BinarySearchTree{data: i}
            // bst.left = NewBst(i)
        case i >= bst.data && bst.right == nil:
    		bst.right = &BinarySearchTree{data: i}
            // bst.right = NewBst(i)   
        case i <= bst.data:
    		bst.left.Insert(i)
        case i > bst.data:
    		bst.right.Insert(i)
    }
}

func (bst *BinarySearchTree) SortedData() []int {
	sorted := []int{}

    if bst.left != nil {
        sorted = append(sorted , bst.left.SortedData()...)
    }

    sorted = append(sorted, bst.data)

    if bst.right != nil {
        sorted = append(sorted, bst.right.SortedData()...)
    }

    return sorted
}




func (s *BinarySearchTree) MapString(f func(int) string) []string {
	if s == nil {
		return []string{}
	}
	return append(append(s.left.MapString(f), f(s.data)), s.right.MapString(f)...)
}

func (s *BinarySearchTree) MapInt(f func(int) int) []int {
	if s == nil {
		return []int{}
	}
	return append(append(s.left.MapInt(f), f(s.data)), s.right.MapInt(f)...)
}