Binary Tree
Binary trees are a fundamental data structure in computer science that organize data in a hierarchical manner. They consist of nodes connected by edges, where each node has at most two child nodes: a left child and a right child. Therefore, a parent in a binary tree might have 2 or 1 or no child at all.
In this tutorial we will learn about various types of binary tree, their properties and how to implement a binary tree in C++.
The topics covered in this tutorial are-
- Types of Binary Tree
- C++ implementation of Binary Tree Step by Step
- Code for Binary Tree in C++
- Application of Binary Tree
Types of Binary Tree
Depending on the arrangement of nodes and their properties, binary trees can be classified into various types.
1.Full Binary Tree:
A Full Binary Tree is a type of binary tree in which every node has either zero or two child nodes. In other words, a full binary tree is a binary tree where each node has exactly zero or two children, and there are no nodes with only one child.
- In a full binary tree, each node has either zero or two child nodes.
2. Complete Binary Tree:
complete binary tree is a special type of binary tree in which all levels, except possibly the last one, are completely filled, and all nodes are as left as possible. In a complete binary tree, if a node has a right child, it must have a left child as well.
- A complete binary tree is a binary tree in which all levels, except possibly the last, are completely filled, and all nodes are as left as possible.
- In a complete binary tree, if a node has a right child, it must have a left child as well.
- It can be efficiently represented using an array.
3. Perfect Binary Tree:
A perfectly balanced binary tree, often referred to as an r-perfect binary tree, is a specific type of binary tree where all the leaf nodes are at the same level, and all the internal nodes have exactly r children. This means that the tree is both full and complete.
- A perfect binary tree is a full binary tree in which all levels are completely filled.
- The number of nodes in a perfect binary tree is 2^h - 1, where h is the height of the tree.
- All leaf nodes are at the same level.
4. Right Skew Binary Tree:
A right skew binary tree is a type of binary tree where each node has only a right child or no children at all. In other words, the right child of each node is not empty, but the left child is always empty. Consequently, the tree extends towards the right side, forming a skewed shape.
Properties of a right skew binary tree:
- All nodes, except the rightmost leaf node, have only a right child.
- Thee depth (height) of the tree is equal to the number of nodes.
- The left subtree of any node is empty.
5. Left Skew Binary Tree: Conversely, a left skew binary tree is a type of binary tree where each node has only a left child or no children at all. In this case, the left child of each node is not empty, but the right child is always empty. The tree extends towards the left side, creating a skewed shape in the opposite direction compared to the right skew binary tree.
Properties of a left skew binary tree:
- All nodes, except the leftmost leaf node, have only a left child.
- The depth (height) of the tree is equal to the number of nodes.
- The right subtree of any node is empty.
C++ implementation of Binary Tree Step by Step:
Step 1: Define the structure for the tree node. Each node should have a data value and pointers to its left and right child nodes.
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
};
Step 2: Implement functions to create new tree nodes. These functions allocate memory for a new node, initialize its data, and set its left and right pointers to nullptr.
TreeNode* createNode(int data) {
TreeNode* newNode = new TreeNode;
newNode->data = data;
newNode->left = nullptr;
newNode->right = nullptr;
return newNode;
}
Step 3: Implement functions to insert nodes into the binary tree. The insertion logic determines whether the new node should be placed on the left or right side of the current node based on the data value.
TreeNode* insertNode(TreeNode* root, int data) {
if (root == nullptr) {
return createNode(data);
} else {
if (data < root->data) {
root->left = insertNode(root->left, data);
} else {
root->right = insertNode(root->right, data);
}
return root;
}
}
Step 4: Implement a function to perform an in-order traversal of the binary tree. In-order traversal visits the left subtree, then the current node, and finally the right subtree.
void inOrderTraversal(TreeNode* root) {
if (root != nullptr) {
inOrderTraversal(root->left);
cout << root->data << " ";
inOrderTraversal(root->right);
}
}
Step 5: Implement a function to delete the binary tree. This function frees the memory allocated for each node using a post-order traversal.
void deleteTree(TreeNode* root) {
if (root != nullptr) {
deleteTree(root->left);
deleteTree(root->right);
delete root;
}
}
Step 6: Test the binary tree implementation by creating a root node and inserting some nodes. Finally, perform an in-order traversal to display the nodes in sorted order.
(More about Inorder Traversal: Inorder Traversal)
int main() {
TreeNode* root = nullptr;
// Insert nodes
root = insertNode(root, 50);
root = insertNode(root, 30);
root = insertNode(root, 20);
root = insertNode(root, 40);
root = insertNode(root, 70);
root = insertNode(root, 60);
root = insertNode(root, 80);
// Perform in-order traversal
cout << "In-order traversal: ";
inOrderTraversal(root);
cout << endl;
// Delete the tree
deleteTree(root);
return 0;
}
Full Code:
#include <iostream>
using namespace std;
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
};
TreeNode* createNode(int data) {
TreeNode* newNode = new TreeNode;
newNode->data = data;
newNode->left = nullptr;
newNode->right = nullptr;
return newNode;
}
TreeNode* insertNode(TreeNode* root, int data) {
if (root == nullptr) {
return createNode(data);
} else {
if (data < root->data) {
root->left = insertNode(root->left, data);
} else {
root->right = insertNode(root->right, data);
}
return root;
}
}
void inOrderTraversal(TreeNode* root) {
if (root != nullptr) {
inOrderTraversal(root->left);
cout << root->data << " ";
inOrderTraversal(root->right);
}
}
void deleteTree(TreeNode* root) {
if (root != nullptr) {
deleteTree(root->left);
deleteTree(root->right);
delete root;
}
}
int main() {
TreeNode* root = nullptr;
root = insertNode(root, 50);
root = insertNode(root, 30);
root = insertNode(root, 20);
root = insertNode(root, 40);
root = insertNode(root, 70);
root = insertNode(root, 60);
root = insertNode(root, 80);
cout << "In-order traversal: ";
inOrderTraversal(root);
cout << endl;
deleteTree(root);
return 0;
}
Output:
In-order traversal: 20 30 40 50 60 70 80
Application of Binary Tree:
Binary trees have numerous applications in computer science and various fields. Some key applications include:
Data Organization: Binary search trees (BSTs) efficiently organize and store data, making them valuable in databases, file systems, and data storage systems.
Expression Evaluation: Binary trees parse and evaluate mathematical expressions, enabling efficient manipulation of complex expressions.
Huffman Coding: Binary trees play a crucial role in Huffman coding, a data compression technique that reduces overall data size by assigning shorter bit sequences to frequently occurring characters.
Binary Heap: Binary heaps, implemented using binary trees, are fundamental data structures used in priority queues and heap sort algorithms for efficient retrieval of maximum or minimum elements.
Syntax Trees: Binary trees are used in compiler design and natural language processing for syntax analysis and parsing, aiding in processing and understanding the structure of programming or natural language statements.
Decision Trees: Binary decision trees are employed in machine learning and data mining algorithms for classification and regression tasks based on sequential decisions using attribute values.
Game Theory: Binary trees are utilized in game theory to model decision-making processes and strategies, enabling analysis and prediction of optimal moves in games like chess and tic-tac-toe.
Network Routing: Binary trees find applications in network routing algorithms, such as the spanning tree protocol (STP), which creates loop-free trees to ensure efficient and redundant-free data transmission within a network.
Image Processing: Binary trees are used in various image processing tasks, including image compression, segmentation, and feature extraction, providing an efficient way to organize and process image data.
These applications highlight the versatility and importance of binary trees in solving various problems across different domains.