Skip to content

Instantly share code, notes, and snippets.

@elulcao
Created May 8, 2022 23:06
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save elulcao/20903edab54b60727a918bdd45ed10ca to your computer and use it in GitHub Desktop.
Go Generics and a Binary Tree
package main
import (
"fmt"
)
// BinaryNode is the placeholder for a number
type BinaryNode[T NumberType] struct {
value T
left *BinaryNode[T]
right *BinaryNode[T]
}
type BinaryTree[T NumberType] struct {
root *BinaryNode[T]
}
// NumberType is the constraint on the type of Number
// In case T is not a valid constraint, the program will not compile
type NumberType interface {
int32 | int64 | float32 | float64
}
// getValue is the generic function that returns the value of a Number
func (n *BinaryNode[T]) getValue() T {
return n.value
}
// InsertNode is the generic function that inserts a Node into a BinaryTree
func (t *BinaryTree[T]) InsertNode(n BinaryNode[T]) *BinaryTree[T] {
if t.root == nil {
t.root = &BinaryNode[T]{value: n.getValue()}
} else {
t.root.insert(n.getValue())
}
return t
}
// insert is the generic function that inserts a value into a BinaryTree
func (n *BinaryNode[T]) insert(value T) {
if n == nil {
return
}
if value <= n.getValue() {
if n.left == nil {
n.left = &BinaryNode[T]{value: value} // Already the correct type
} else {
n.left.insert(value)
}
} else {
if n.right == nil {
n.right = &BinaryNode[T]{value: value} // Already the correct type
} else {
n.right.insert(value)
}
}
}
func (n *BinaryNode[T]) print(ns int, ch rune) {
if n == nil {
return
}
for i := 0; i < ns; i++ {
fmt.Printf(" ")
}
fmt.Printf("%c:%v\n", ch, n.getValue())
n.left.print(ns+1, 'l')
n.right.print(ns+1, 'r')
}
func main() {
tree := &BinaryTree[int64]{}
tree.InsertNode(BinaryNode[int64]{value: 10})
tree.InsertNode(BinaryNode[int64]{value: 20})
tree.InsertNode(BinaryNode[int64]{value: 30})
tree.InsertNode(BinaryNode[int64]{value: 3})
tree.InsertNode(BinaryNode[int64]{value: 2})
tree.InsertNode(BinaryNode[int64]{value: 1})
tree.root.print(0, 'R')
treeFloat := &BinaryTree[float64]{}
treeFloat.InsertNode(BinaryNode[float64]{value: 11.11})
treeFloat.InsertNode(BinaryNode[float64]{value: 22.22})
treeFloat.InsertNode(BinaryNode[float64]{value: 33.33})
treeFloat.InsertNode(BinaryNode[float64]{value: 0.1})
treeFloat.root.print(0, 'R')
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment