Example 1: binary tree in golang
package main
import (
"fmt"
"os"
"io"
)
type BinaryNode struct {
left *BinaryNode
right *BinaryNode
data int64
}
type BinaryTree struct {
root *BinaryNode
}
func (t *BinaryTree) insert(data int64) *BinaryTree {
if t.root == nil {
t.root = &BinaryNode{data: data, left: nil, right: nil}
} else {
t.root.insert(data)
}
return t
}
func (n *BinaryNode) insert(data int64) {
if n == nil {
return
} else if data <= n.data {
if n.left == nil {
n.left = &BinaryNode{data: data, left: nil, right: nil}
} else {
n.left.insert(data)
}
} else {
if n.right == nil {
n.right = &BinaryNode{data: data, left: nil, right: nil}
} else {
n.right.insert(data)
}
}
}
func print(w io.Writer, node *BinaryNode, ns int, ch rune) {
if node == nil {
return
}
for i := 0; i < ns; i++ {
fmt.Fprint(w, " ")
}
fmt.Fprintf(w, "%c:%v\n", ch, node.data)
print(w, node.left, ns+2, 'L')
print(w, node.right, ns+2, 'R')
}
func main() {
tree := &BinaryTree{}
tree.insert(100).
insert(-20).
insert(-50).
insert(-15).
insert(-60).
insert(50).
insert(60).
insert(55).
insert(85).
insert(15).
insert(5).
insert(-10)
print(os.Stdout, tree.root, 0, 'M')
}
Example 2: golang binary search tree bst
package main
import "fmt"
type bstnode struct {
value int
left *bstnode
right *bstnode
}
type bst struct {
root *bstnode
}
func (b *bst) reset() {
b.root = nil
}
func (b *bst) insert(value int) {
b.insertRec(b.root, value)
}
func (b *bst) insertRec(node *bstnode, value int) *bstnode {
if b.root == nil {
b.root = &bstnode{
value: value,
}
return b.root
}
if node == nil {
return &bstnode{value: value}
}
if value <= node.value {
node.left = b.insertRec(node.left, value)
}
if value > node.value {
node.right = b.insertRec(node.right, value)
}
return node
}
func (b *bst) find(value int) error {
node := b.findRec(b.root, value)
if node == nil {
return fmt.Errorf("Value: %d not found in tree", value)
}
return nil
}
func (b *bst) findRec(node *bstnode, value int) *bstnode {
if node == nil {
return nil
}
if node.value == value {
return b.root
}
if value < node.value {
return b.findRec(node.left, value)
}
return b.findRec(node.right, value)
}
func (b *bst) inorder() {
b.inorderRec(b.root)
}
func (b *bst) inorderRec(node *bstnode) {
if node != nil {
b.inorderRec(node.left)
fmt.Println(node.value)
b.inorderRec(node.right)
}
}
func main() {
bst := &bst{}
eg := []int{2, 5, 7, -1, -1, 5, 5}
for _, val := range eg {
bst.insert(val)
}
fmt.Printf("Printing Inorder:\n")
bst.inorder()
bst.reset()
eg = []int{4, 5, 7, 6, -1, 99, 5}
for _, val := range eg {
bst.insert(val)
}
fmt.Printf("\nPrinting Inorder:\n")
bst.inorder()
fmt.Printf("\nFinding Values:\n")
err := bst.find(2)
if err != nil {
fmt.Printf("Value %d Not Found\n", 2)
} else {
fmt.Printf("Value %d Found\n", 2)
}
err = bst.find(6)
if err != nil {
fmt.Printf("Value %d Not Found\n", 6)
} else {
fmt.Printf("Value %d Found\n", 6)
}
err = bst.find(5)
if err != nil {
fmt.Printf("Value %d Not Found\n", 5)
} else {
fmt.Printf("Value %d Found\n", 5)
}
err = bst.find(1)
if err != nil {
fmt.Printf("Value %d Not Found\n", 1)
} else {
fmt.Printf("Value %d Found\n", 1)
}
}