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.

Most Helpful This Week