Formed in 2009, the Archive Team (not to be confused with the archive.org Archive-It Team) is a rogue archivist collective dedicated to saving copies of rapidly dying or deleted websites for the sake of history and digital heritage. The group is 100% composed of volunteers and interested parties, and has expanded into a large amount of related projects for saving online and digital history.
go-binarytree
A simple, generic implementation of Binary Trees in Go.
Installation
Install go-binarytree by executing the following command.
go get -v gopkg.in/dnaeon/go-binarytree.v1Usage
The following example builds a simple binary tree with 7 nodes, and performs in-, pre-, post- and level-order walking of the tree (error handling is omitted for simplicity).
package main
import (
"fmt"
"gopkg.in/dnaeon/go-binarytree.v1"
)
func main() {
root := binarytree.NewNode(10)
five := root.InsertLeft(5)
twenty := root.InsertRight(20)
five.InsertLeft(9)
five.InsertRight(18)
twenty.InsertLeft(3)
twenty.InsertRight(7)
fmt.Printf("height of tree: %d\n", root.Height())
fmt.Printf("size of the tree: %d\n", root.Size())
fmt.Printf("tree is balanced: %t\n", root.IsBalancedTree())
fmt.Printf("tree is complete: %t\n", root.IsCompleteTree())
fmt.Printf("tree is perfect: %t\n", root.IsPerfectTree())
// Function to be called while walking the tree, which simply
// prints the values of each visited node
walkFunc := func(n *binarytree.Node[int]) error {
fmt.Printf("%d ", n.Value)
return nil
}
fmt.Printf("in-order values: ")
root.WalkInOrder(walkFunc)
fmt.Println()
fmt.Printf("pre-order values: ")
root.WalkPreOrder(walkFunc)
fmt.Println()
fmt.Printf("post-orer values: ")
root.WalkPostOrder(walkFunc)
fmt.Println()
fmt.Printf("level-order values: ")
root.WalkLevelOrder(walkFunc)
fmt.Println()
}Running above example produces the following output.
height of tree: 2
size of the tree: 7
tree is balanced: true
tree is complete: true
tree is perfect: true
in-order values: 9 5 18 10 3 20 7
pre-order values: 10 5 9 18 20 3 7
post-orer values: 9 18 5 3 7 20 10
level-order values: 10 5 20 9 18 3 7 The following example generates the Dot representation of the binary tree and prints it to the standard output.
package main
import (
"os"
"gopkg.in/dnaeon/go-binarytree.v1"
)
func main() {
root := binarytree.NewNode(10)
five := root.InsertLeft(5)
twenty := root.InsertRight(20)
five.InsertLeft(9)
five.InsertRight(18)
twenty.InsertLeft(3)
twenty.InsertRight(7)
root.WriteDot(os.Stdout)
}Running above example produces an output similar to this one.
digraph {
node [color=lightblue fillcolor=lightblue fontcolor=black shape=record style="filled, rounded"]
824634441792 [label="<l>|<v> 10|<r>" ]
824634441792:l -> 824634441856:v
824634441792:r -> 824634441920:v
824634441856 [label="<l>|<v> 5|<r>" ]
824634441856:l -> 824634441984:v
824634441856:r -> 824634442048:v
824634441984 [label="<l>|<v> 9|<r>" ]
824634442048 [label="<l>|<v> 18|<r>" ]
824634441920 [label="<l>|<v> 20|<r>" ]
824634441920:l -> 824634442112:v
824634441920:r -> 824634442176:v
824634442112 [label="<l>|<v> 3|<r>" ]
824634442176 [label="<l>|<v> 7|<r>" ]
}The generated representation can be rendered using graphviz, e.g.
dot -Tsvg /path/to/file.dot -o /tmp/to/file.svgWhen building a binary tree with user-defined types such as structs, make sure that you also implement the fmt.Stringer interface for your type, so that Dot generation works properly.
Make sure to check the included test cases for additional examples.
Tests
Run the tests.
make testLicense
go-binarytree is Open Source and licensed under the BSD
License.