Created
May 8, 2022 23:06
-
-
Save elulcao/20903edab54b60727a918bdd45ed10ca to your computer and use it in GitHub Desktop.
Go Generics and a Binary Tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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