Binary Tree

A binary tree is a data structure that consists of nodes where each node has at most two children, known as the left child and the right child. The tree starts from the root node and branches out to multiple child nodes. Each node in a binary tree can have up to two children, which can either be a null reference or another node.

When to Use Binary Trees

Binary trees are often used to represent hierarchical data structures, such as family trees, file systems, and organization charts. They are also used for searching and sorting algorithms like binary search and heapsort.

Implementation of a Binary Tree

We can implement a binary tree using the following Java code.

Main


              12345678910111213141516171819202122232425262728293031323334353637
            
class Node {
    int data;
    Node left, right;
   
    public Node(int data) {
        this.data = data;
        left = right = null;
    }
}


class BinaryTree {
    Node root;
   
    public BinaryTree() {
        root = null;
    }
   
    public void insert(int data) {
        root = insertRecursive(root, data);
    }
   
    public Node insertRecursive(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }
       
        if (data < root.data) {
            root.left = insertRecursive(root.left, data);
        } else if (data > root.data) {
            root.right = insertRecursive(root.right, data);
        }
       
        return root;
    }
}

In this implementation, the Node class represents each node in the binary tree. It contains three fields: data to store the value of the node, left to store a reference to the left child node, and right to store a reference to the right child node.

The BinaryTree class is the main class that represents the binary tree itself. It has one field: root, which is a reference to the root node of the binary tree.

The insert() method is used to insert a new node into the binary tree. It takes a value as its parameter, creates a new Node object with the value, and then inserts the node into the binary tree in the correct position based on the value. If the binary tree is empty, the new node becomes the root node. If the binary tree is not empty, the method traverses down the tree to find the correct position for the new node, comparing the value of the new node with the values of the existing nodes.

Traversals of a Binary Tree

Traversal is the process of visiting each node in a binary tree exactly once. There are three main types of traversal in binary trees:

Pre-order Traversal
In-order Traversal
Post-order Traversal

Pre-order traversal is a type of depth-first traversal in which the root node is visited first, followed by the left sub-tree and then the right sub-tree.

In-order traversal is also a type of depth-first traversal in which the left sub-tree is visited first, followed by the root node and then the right sub-tree.

Post-order traversal is another type of depth-first traversal in which the left sub-tree is visited first, followed by the right sub-tree and then the root node.

Advantages and Disadvantages of Binary Trees

Advantages	Disadvantages
Binary trees are efficient for searching and sorting operations.	The performance of binary trees can degrade rapidly if they become unbalanced.
They are easy to implement and understand.	Balancing a binary tree can be a complex and time-consuming process.
Binary trees can be used to model many real-world situations, such as family trees and file systems.	Binary trees are not as efficient for insertion and deletion operations as other data structures, such as linked lists.

Все було зрозуміло?

Секція 1. Розділ 5