Last Updated on December 14, 2022 by Prepbytes
In this tutorial, we’ll deep dive into the Data Structures in C++ topics majorly on trees and graphs. We know that data structures are very important and play a crucial role in a placement perspective.
Need for Data Structure
As applications are getting complex and data rich, there are three common problems applications face now-a-days.
- Data Search − Consider an inventory of 1 million(106) items of a store. If the application is to search for an item. It has to search for 1 million(106) items every time slowing down the search. As data grows, search will become slower.
- Processor speed − Processor speed although being very high, falls limited if data grows to billion records.
- Multiple requests − As thousands of users can search data simultaneously on a web server,even a very fast server fails while searching the data.
To solve the above problems, data structures come to the rescue. Data can be organized in a data structure in such a way that all items may not be required to be searched and required data can be searched almost instantly.
Tree Data Structure
We read the linear data structures like an array, linked list, stack and queue in which all the elements are arranged in a sequential manner. The different data structures are used for different kinds of data.
A tree is also one of the data structures that represent hierarchical data.
Let’s understand some key points of the Tree data structure.
- A tree data structure is defined as a collection of objects or entities known as nodes that are linked together to represent or simulate hierarchy.
- A tree data structure is a non-linear data structure because it does not store in a sequential manner. It is a hierarchical structure as elements in a Tree are arranged in multiple levels.
- In the Tree data structure, the topmost node is known as a root node. Each node contains some data, and data can be of any type. In the above tree structure, the node contains the name of the employee, so the type of data would be a string.
- Each node contains some data and the link or reference of other nodes that can be called children.
Some basic terms used in Tree data structure.
Let’s consider the tree structure, which is shown below:
In the above structure, each node is labeled with some number. Each arrow shown in the above figure is known as a link between the two nodes.
- Root: The root node is the topmost node in the tree hierarchy. In other words, the root node is the one that doesn’t have any parent. In the above structure, node numbered 1 is the root node of the tree. If a node is directly linked to some other node, it would be called a parent-child relationship.
- Child node: If the node is a descendant of any node, then the node is known as a child node.
- Parent: If the node contains any sub-node, then that node is said to be the parent of that sub-node.
- Sibling: The nodes that have the same parent are known as siblings.
- Leaf Node:- The node of the tree, which doesn’t have any child node, is called a leaf node. A leaf node is the bottom-most node of the tree. There can be any number of leaf nodes present in a general tree. Leaf nodes can also be called external nodes.
- Internal nodes: A node has at least one child node known as an internal
- Ancestor node:- An ancestor of a node is any predecessor node on a path from the root to that node. The root node doesn’t have any ancestors. In the tree shown in the above image, nodes 1, 2, and 5 are the ancestors of node 10.
- Descendant: The immediate successor of the given node is known as a descendant of a node. In the above figure, 10 is the descendant of node 5.
Implementation:
// Binary Tree in C++
#include <stdlib.h>
#include <iostream>
using namespace std;
struct node {
int data;
struct node *left;
struct node *right;
};
// New node creation
struct node *newNode(int data) {
struct node *node = (struct node *)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
// Traverse Preorder
void traversePreOrder(struct node *temp) {
if (temp != NULL) {
cout << " " << temp->data;
traversePreOrder(temp->left);
traversePreOrder(temp->right);
}
}
// Traverse Inorder
void traverseInOrder(struct node *temp) {
if (temp != NULL) {
traverseInOrder(temp->left);
cout << " " << temp->data;
traverseInOrder(temp->right);
}
}
// Traverse Postorder
void traversePostOrder(struct node *temp) {
if (temp != NULL) {
traversePostOrder(temp->left);
traversePostOrder(temp->right);
cout << " " << temp->data;
}
}
int main() {
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
cout << "preorder traversal: ";
traversePreOrder(root);
cout << "\nInorder traversal: ";
traverseInOrder(root);
cout << "\nPostorder traversal: ";
traversePostOrder(root);
}
Data Structures in C++ is an important part of Programming. Get a better understanding of problems by watching these video tutorials created by expert mentors at Prepbytes.
Binary Search Tree(BST):
A binary search tree follows some order to arrange the elements. In a Binary search tree, the value of the left node must be smaller than the parent node, and the value of the right node must be greater than the parent node. This rule is applied recursively to the left and right subtrees of the root.
Let’s understand the concept of Binary search tree with an example.
In the above figure, we can observe that the root node is 40, and all the nodes of the left subtree are smaller than the root node, and all the nodes of the right subtree are greater than the root node.
Similarly, we can see the left child of the root node is greater than its left child and smaller than its right child. So, it also satisfies the property of binary search trees. Therefore, we can say that the tree in the above image is a binary search tree.
Suppose if we change the value of node 35 to 55 in the above tree, check whether the tree will be a binary search tree or not.
In the above tree, the value of the root node is 40, which is greater than its left child 30 but smaller than the right child of 30, i.e., 55. So, the above tree does not satisfy the property of Binary search tree. Therefore, the above tree is not a binary search tree.
Implementation:
// Binary Search Tree operations in C++
#include <iostream>
using namespace std;
struct node {
int key;
struct node *left, *right;
};
// Create a node
struct node *newNode(int item) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// Inorder Traversal
void inorder(struct node *root) {
if (root != NULL) {
// Traverse left
inorder(root->left);
// Traverse root
cout << root->key << " -> ";
// Traverse right
inorder(root->right);
}
}
// Insert a node
struct node *insert(struct node *node, int key) {
// Return a new node if the tree is empty
if (node == NULL) return newNode(key);
// Traverse to the right place and insert the node
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
return node;
}
// Find the inorder successor
struct node *minValueNode(struct node *node) {
struct node *current = node;
// Find the leftmost leaf
while (current && current->left != NULL)
current = current->left;
return current;
}
// Deleting a node
struct node *deleteNode(struct node *root, int key) {
// Return if the tree is empty
if (root == NULL) return root;
// Find the node to be deleted
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
// If the node is with only one child or no child
if (root->left == NULL) {
struct node *temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct node *temp = root->left;
free(root);
return temp;
}
// If the node has two children
struct node *temp = minValueNode(root->right);
// Place the inorder successor in position of the node to be deleted
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
return root;
}
// Driver code
int main() {
struct node *root = NULL;
root = insert(root, 8);
root = insert(root, 3);
root = insert(root, 1);
root = insert(root, 6);
root = insert(root, 7);
root = insert(root, 10);
root = insert(root, 14);
root = insert(root, 4);
cout << "Inorder traversal: ";
inorder(root);
cout << "\nAfter deleting 10\n";
root = deleteNode(root, 10);
cout << "Inorder traversal: ";
inorder(root);
}
Test your data structure skills by taking this Data Structures in C++ Mock Test designed by experienced mentors at Prepbytes.
Graph:
A graph can be defined as a group of vertices and edges that are used to connect these vertices. A graph can be seen as a cyclic tree, where the vertices (Nodes) maintain any complex relationship among them instead of having parent-child relationship.
Directed and Undirected Graph
A graph can be directed or undirected. However, in an undirected graph, edges are not associated with the directions with them. An undirected graph is shown in the above figure since its edges are not attached with any of the directions. If an edge exists between vertex A and B then the vertices can be traversed from B to A as well as A to B.
A undirected graph is shown in the following figure.
In a directed graph, edges form an ordered pair. Edges represent a specific path from some vertex A to another vertex B. Node A is called the initial node while node B is called terminal node.
A directed graph is shown in the following figure.
Graph is represented by two methods:
Adjacency Matrix
An adjacency matrix is a 2D array of V x V vertices. Each row and column represent a vertex.
If the value of any element a [i][j] is 1, it represents that there is an edge connecting vertex i and vertex j.
Implementation:
#include<iostream>
using namespace std;
int vertArr[20][20]; //the adjacency matrix initially 0
int count = 0;
void displayMatrix(int v) {
int i, j;
for(i = 0; i < v; i++) {
for(j = 0; j < v; j++) {
cout << vertArr[i][j] << " ";
}
cout << endl;
}
}
void add_edge(int u, int v) { //function to add edge into the matrix
vertArr[u][v] = 1;
vertArr[v][u] = 1;
}
main(int argc, char* argv[]) {
int v = 6; //there are 6 vertices in the graph
add_edge(0, 4);
add_edge(0, 3);
add_edge(1, 2);
add_edge(1, 4);
add_edge(1, 5);
add_edge(2, 3);
add_edge(2, 5);
add_edge(5, 3);
add_edge(5, 4);
displayMatrix(v);
}
Adjacency List
An adjacency list represents a graph as an array of linked lists.
The index of the array represents a vertex and each element in its linked list represents the other vertices that form an edge with the vertex.
Implementation:
// A simple representation of graph using STL
#include <bits/stdc++.h>
using namespace std;
// A utility function to add an edge in an
// undirected graph.
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
// A utility function to print the adjacency list
// representation of graph
void printGraph(vector<int> adj[], int V)
{
for (int v = 0; v < V; ++v) {
cout << "\n Adjacency list of vertex " << v
<< "\n head ";
for (auto x : adj[v])
cout << "-> " << x;
printf("\n");
}
}
// Driver code
int main()
{
int V = 5;
vector<int> adj[V];
addEdge(adj, 0, 1);
addEdge(adj, 0, 4);
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 1, 4);
addEdge(adj, 2, 3);
addEdge(adj, 3, 4);
printGraph(adj, V);
return 0;
}
Practice makes a coder perfect, so don’t miss to check Graph Competitive Coding Problems created by expert mentors at Prepbytes.
We tried to discuss Data Structures in C++ in this article. We hope this article gives you a better understanding of basics in Data Structures and Algorithms. Prepbytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program that will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.