Introduction of Binary Tree:
A Binary tree is a rooted tree in which each node may have maximum 2 child. One child node may be in left and known as left child while other child node may be in right and known as right child.
Representations of a binary tree:
A binary tree may be represented in computer memory in two ways. These two ways are Linked representation of binary tree and sequential representation of binary tree.
Linked Representation of Binary Tree:
In this representation, the binary tree is stored in memory, as a linked list where the number of nodes is stored at non-contiguous memory locations and parent child relationships are inherited and linked together like a tree. is. Each node has three parts: pointer to the left node, data element and pointer to the right node. Each binary tree has a root pointer that points to the root node of the binary tree. In an empty binary tree, the root pointer will point to null. Below given binary tree.
In the figure above, a tree is seen as a collection of nodes where each node has three parts: left pointer, data element and right pointer. The left pointer stores the left child's address, while the right pointer stores the right child's address. The left and right pointers in the leaf node are null.
Sequential Representation of Binary Tree:
It is the simplest memory allocation technique for storing tree elements but it is an inefficient technique as it requires a lot of space to store tree elements. A binary tree with its memory allocation is shown in the following figure.
In this representation, an array is used to store tree elements. The size of the array will be equal to the number of nodes present in the tree. The root node of the tree will be present on the 1st index of the array. If a node is stored on the ith index then its left and right children will be stored at 2i and 2i + 1 location. If the 1st index of the array is tree [1] 0, it means that the tree is empty.
Eg. A node is at 7 th index then its left child index is 14 and right child index is 15.
Application of Binary Tree:
Binary tree is widely used in Computer Science since they allow efficient and quick searching, sorting and hierarchical binary data representation. Some application of binary tree is as:
- Binary Search Tree (BST)
- Binary Expression Tree (BET)
- Heap Tree
- Huffman encoding
- Decision Tree
- Syntax tree in compilers
- Game tree like Tic-Tac-Toe
Advantages of Binary Tree:
Some advantages of binary tree are as:
- Fast and efficient searching
- Fast and efficient sorting
- Hierarchical representation of binary data
- Dynamic Memory Allocation
- Efficient data management
Frequently Asked Questions (FAQs)
Q.1 What do you mean by binary tree?
Ans: A Binary tree is a rooted tree in which each node may have maximum 2 child.
Q.2 Write any two advantages of binary tree.
Ans: Fast and efficient searching, Fast and efficient sorting
Q.3 Write name of methods to represent binary tree in memory.
Ans: Linked representation of binary tree and sequential representation of binary tree.
Q.4 Write any two applications of binary tree.
Ans: Syntax tree in compilers, Game tree like Tic-Tac-Toe
Conclusion:
Binary tree is an important data structure which has many advantages and real-life applications. It can be represented in memory in two ways which are sequential representation and linked representation.
Author
Mr. Rahul Agarwal
Associate Professor, Department Of CS & IT
Biyani Group Of Colleges