binary tree implement

binaryTree.go

package main

import "fmt"

type BinaryTree struct {
	head *node
}

func NewBinaryTree(value int) BinaryTree {
	return BinaryTree{&node{val: value}}
}

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

type TraverseType int

const (
	Pre TraverseType = iota
	In
	Post
)

func (tree BinaryTree) Insert(target int) {
	insert(tree.head, target)
}
func (tree BinaryTree) Search(target int) bool {
	return search(tree.head, target)
}
func (tree BinaryTree) Delete(target int) bool {
	return delete(tree.head, target)
}
func (tree BinaryTree) Traverse(traverseType TraverseType) {
	switch traverseType {
	case Pre:
		traversePre(tree.head)
	case In:
		traverseIn(tree.head)
	case Post:
		traversePost(tree.head)
	}
	fmt.Println()
}

func insert(h *node, target int) {
	cur := h
	newNode := node{val: target}
	for cur != nil {
		if target < cur.val {
			if cur.left == nil {
				cur.left = &newNode
				break
			} else {
				cur = cur.left
			}
		} else {
			if cur.right == nil {
				cur.right = &newNode
				break
			} else {
				cur = cur.right
			}
		}
	}
}
func traversePre(h *node) {
	if h != nil {
		fmt.Print(h.val, "->")
		traversePre(h.left)
		traversePre(h.right)
	}

}
func traverseIn(h *node) {
	if h != nil {
		traverseIn(h.left)
		fmt.Print(h.val, "->")
		traverseIn(h.right)
	}
}
func traversePost(h *node) {
	if h != nil {
		traversePost(h.left)
		traversePost(h.right)
		fmt.Print(h.val, "->")
	}
}
func search(h *node, target int) bool {
	cur := h
	for cur != nil {
		if target < cur.val {
			cur = cur.left
		} else if target > cur.val {
			cur = cur.right
		} else {
			return true
		}
	}
	return false
}
func delete(h *node, target int) bool {
	var parent *node = nil
	cur := h
	//find the delete node
	for cur != nil && cur.val != target {
		parent = cur
		if cur.val > target {
			cur = cur.left
		} else {
			cur = cur.right
		}
	}
	if cur == nil {
		return false
	}

	//left child is null
	if cur.left == nil {
		if cur == h {
			h = h.right
		} else if cur == parent.left {
			parent.left = cur.right
		} else {
			parent.right = cur.right
		}
		//right child is null
	} else if cur.right == nil {
		if cur == h {
			h = h.left
		} else if cur == parent.left {
			parent.left = cur.left
		} else {
			parent.right = cur.left
		}
		//both child exist
	} else {
		//find the first bigger node than cur ,the first smaller also work
		bigger := cur.right
		bigParent := cur
		for bigger.left != nil {
			bigParent = bigger
			bigger = bigger.left
		}

		cur.val = bigger.val

		if bigParent.left == bigger {
			bigParent.left = bigger.right
		} else {
			// when initially bigger don't have left child
			bigParent.right = bigger.right
		}

	}
	return true

}

func main() {
	tree := NewBinaryTree(5)
	tree.Insert(1)
	tree.Insert(3)
	tree.Insert(8)
	tree.Insert(4)
	tree.Insert(7)
	tree.Insert(9)

	tree.Traverse(Pre)
	tree.Traverse(In)
	tree.Traverse(Post)

	fmt.Println(tree.Search(2))
	fmt.Println(tree.Search(3))

	fmt.Println(tree.Delete(5))
	fmt.Println(tree.Delete(3))
	fmt.Println(tree.Delete(1))

	tree.Traverse(Pre)

}