Last Updated on December 14, 2022 by Prepbytes
In this tutorial, we’ll deep dive into the Data Structures using 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
// Tree traversal in C
#include <stdio.h>
#include <stdlib.h>
struct node {
int item;
struct node* left;
struct node* right;
};
// Inorder traversal
void inorderTraversal(struct node* root) {
if (root == NULL) return;
inorderTraversal(root->left);
printf("%d ->", root->item);
inorderTraversal(root->right);
}
// Preorder traversal
void preorderTraversal(struct node* root) {
if (root == NULL) return;
printf("%d ->", root->item);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// Postorder traversal
void postorderTraversal(struct node* root) {
if (root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ->", root->item);
}
// Create a new Node
struct node* createNode(value) {
struct node* newNode = malloc(sizeof(struct node));
newNode->item = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Insert on the left of the node
struct node* insertLeft(struct node* root, int value) {
root->left = createNode(value);
return root->left;
}
// Insert on the right of the node
struct node* insertRight(struct node* root, int value) {
root->right = createNode(value);
return root->right;
}
int main() {
struct node* root = createNode(1);
insertLeft(root, 2);
insertRight(root, 3);
insertLeft(root->left, 4);
printf("Inorder traversal \n");
inorderTraversal(root);
printf("\nPreorder traversal \n");
preorderTraversal(root);
printf("\nPostorder traversal \n");
postorderTraversal(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: https://ideone.com/g2XMKT
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.
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:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 10
struct Vertex {
char label;
bool visited;
};
//stack variables
int stack[MAX];
int top=-1;
//queue variables
int queue[MAX];
int rear=-1;
int front=0;
int queueItemCount = 0;
//graph variables
//array of vertices
struct Vertex* lstVertices[MAX];
//adjacency matrix
int adjMatrix[MAX][MAX];
//vertex count
int vertexCount = 0;
//stack functions
void push(int item) {
stack[++top]=item;
}
int pop() {
return stack[top--];
}
int peek() {
return stack[top];
}
bool isStackEmpty(){
return top == -1;
}
//queue functions
void insert(int data){
queue[++rear] = data;
queueItemCount++;
}
int removeData(){
queueItemCount--;
return queue[front++];
}
bool isQueueEmpty(){
return queueItemCount == 0;
}
//graph functions
//add vertex to the vertex list
void addVertex(char label){
struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
vertex->label = label;
vertex->visited = false;
lstVertices[vertexCount++] = vertex;
}
//add edge to edge array
void addEdge(int start,int end){
adjMatrix[start][end] = 1;
adjMatrix[end][start] = 1;
}
//display the vertex
void displayVertex(int vertexIndex){
printf("%c ",lstVertices[vertexIndex]->label);
}
//get the adjacent unvisited vertex
int getAdjUnvisitedVertex(int vertexIndex){
int i;
for(i=0; i<vertexCount; i++)
if(adjMatrix[vertexIndex][i]==1 && lstVertices[i]->visited==false)
return i;
return -1;
}
void depthFirstSearch(){
int i;
//mark first node as visited
lstVertices[0]->visited = true;
//display the vertex
displayVertex(0);
//push vertex index in stack
push(0);
while(!isStackEmpty()){
//get the unvisited vertex of vertex which is at top of the stack
int unvisitedVertex = getAdjUnvisitedVertex(peek());
//no adjacent vertex found
if(unvisitedVertex == -1){
pop();
} else {
lstVertices[unvisitedVertex]->visited = true;
displayVertex(unvisitedVertex);
push(unvisitedVertex);
}
}
//stack is empty, search is complete, reset the visited flag
for(i=0;i < vertexCount;i++){
lstVertices[i]->visited = false;
}
}
void breadthFirstSearch(){
int i;
//mark first node as visited
lstVertices[0]->visited = true;
//display the vertex
displayVertex(0);
//insert vertex index in queue
insert(0);
int unvisitedVertex;
while(!isQueueEmpty()){
//get the unvisited vertex of vertex which is at front of the queue
int tempVertex = removeData();
//no adjacent vertex found
while((unvisitedVertex=getAdjUnvisitedVertex(tempVertex)) != -1){
lstVertices[unvisitedVertex]->visited = true;
displayVertex(unvisitedVertex);
insert(unvisitedVertex);
}
}
//queue is empty, search is complete, reset the visited flag
for(i=0;i<vertexCount;i++){
lstVertices[i]->visited = false;
}
}
main() {
int i, j;
for(i=0; i<MAX; i++) // set adjacency
for(j=0; j<MAX; j++) // matrix to 0
adjMatrix[i][j] = 0;
addVertex('A'); //0
addVertex('B'); //1
addVertex('C'); //2
addVertex('D'); //3
addVertex('E'); //4
addVertex('F'); //5
addVertex('G'); //6
/* 1 2 3
* 0 |--B--C--D
* A--|
* |
* | 4
* |-----E
* | 5 6
* | |--F--G
* |--|
*/
addEdge(0, 1); //AB
addEdge(1, 2); //BC
addEdge(2, 3); //CD
addEdge(0, 4); //AC
addEdge(0, 5); //AF
addEdge(5, 6); //FG
printf("Depth First Search: ");
//A B C D E F G
depthFirstSearch();
printf("\nBreadth First Search: ");
//A B E F C G D
breadthFirstSearch();
}
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.