Golang program to implement Binary Tree
A binary tree is a data structure consisting of nodes, where each node has at most two children (also called "left" and "right" children). The nodes in a binary tree are connected by edges, which represent the links between nodes. The topmost node in the tree is called the root node, and each node other than the root is connected to a unique parent node.
Binary trees are often used to represent hierarchical data structures, such as family trees, organization charts, and file system directories. They are also used as the underlying data structure for many algorithms, such as binary search, sorting, and graph traversal algorithms.
Binary trees have several important properties, including:
The maximum number of nodes at level l is 2^l, and the maximum number of nodes in a binary tree of height h is 2^(h+1)-1.
The height of a binary tree is the number of edges on the longest path from the root node to a leaf node (a node with no children). The height of an empty tree is defined as -1.
A binary tree is said to be balanced if the height of the left and right subtrees of every node differ by at most 1. A balanced binary tree has a height of O(log n), where n is the number of nodes in the tree.
A binary tree can be traversed in several ways, including in-order (left subtree, root node, right subtree), pre-order (root node, left subtree, right subtree), and post-order (left subtree, right subtree, root node) traversal.
Binary trees have many variants, including binary search trees (BSTs), AVL trees, and red-black trees, which have different rules for ordering and balancing the nodes in the tree.
Example
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')
}
Output
M:100
L:-20
L:-50
L:-60
R:-15
R:50
L:15
L:5
L:-10
R:60
L:55
R:85
This is a Golang program that implements a binary search tree (BST) and prints the nodes of the tree in a graphical format.
The program first defines a BinaryNode
struct, which represents a single node in the tree. Each node contains a data field (an integer value), and pointers to its left and right child nodes. The BinaryTree
struct represents the entire tree, and contains a pointer to the root node.
The program then defines two methods for the BinaryTree
and BinaryNode
structs. The insert
method inserts a new node with the given data value into the tree in the correct location according to the rules of a BST. If the tree is empty, the new node becomes the root node. If the data value is less than or equal to the current node's data value, it is inserted into the left subtree. Otherwise, it is inserted into the right subtree. The method is called recursively until it finds the correct location for the new node.
The print
function is a recursive function that prints the nodes of the tree in a graphical format, with the root node at the top and its children below it. The ns
parameter is the number of spaces to indent the node based on its level in the tree, and the ch
parameter is the character used to indicate whether the node is a left or right child of its parent. The function first prints the required number of spaces, followed by the character (L
or R
) and the data value of the node. It then recursively calls itself to print the left and right subtrees of the node.
Finally, in the main
function, a new BinaryTree
is created, and several nodes are inserted into it using the insert
method. The print
function is then called with the root node of the tree, along with the starting indentation level (0) and the character M
to indicate that the node is the root node. The output of the print
function is sent to os.Stdout
, which prints it to the console.