Data structures play a pivotal role in computer programming, and two of the most versatile ones are Trees and Graphs. In this comprehensive guide, we will delve into Trees and Graphs in the C programming language, providing detailed explanations, practical examples, and real data to help you master these essential concepts.
Trees in C
A Tree is a hierarchical data structure that consists of nodes connected by edges. Each node has a parent and zero or more child nodes. Trees are widely used in various applications, such as file systems, databases, and hierarchical data representation.
Example: Implementing a Binary Search Tree (BST) in C
Let’s create a simple Binary Search Tree in C:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* insert(struct Node* root, int value) {
if (root == NULL) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
if (value < root->data) {
root->left = insert(root->left, value);
} else if (value > root->data) {
root->right = insert(root->right, value);
}
return root;
}
void inorderTraversal(struct Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
int main() {
struct Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);
printf("Inorder Traversal: ");
inorderTraversal(root);
return 0;
}Output:
Inorder Traversal: 20 30 40 50 60 70 80
In this example, we implement a Binary Search Tree and perform an inorder traversal to display the elements in sorted order.
Graphs in C
A Graph is a collection of nodes (vertices) and edges that connect these nodes. Graphs are used for modeling relationships, networks, and complex data structures.
Example: Implementing a Graph in C
Let’s create a simple directed graph in C:
#include <stdio.h>
#include <stdlib.h>
struct GraphNode {
int value;
struct GraphNode* next;
};
struct Graph {
int numVertices;
struct GraphNode** adjacencyList;
};
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjacencyList = (struct GraphNode**)malloc(vertices * sizeof(struct GraphNode*));
for (int i = 0; i < vertices; ++i) {
graph->adjacencyList[i] = NULL;
}
return graph;
}
void addEdge(struct Graph* graph, int src, int dest) {
struct GraphNode* newNode = (struct GraphNode*)malloc(sizeof(struct GraphNode));
newNode->value = dest;
newNode->next = graph->adjacencyList[src];
graph->adjacencyList[src] = newNode;
}
void printGraph(struct Graph* graph) {
for (int i = 0; i < graph->numVertices; ++i) {
struct GraphNode* current = graph->adjacencyList[i];
printf("Adjacency list for vertex %d: ", i);
while (current != NULL) {
printf("%d -> ", current->value);
current = current->next;
}
printf("NULL\n");
}
}
int main() {
int numVertices = 5;
struct Graph* graph = createGraph(numVertices);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 0);
addEdge(graph, 2, 3);
addEdge(graph, 3, 3);
printf("Graph Representation:\n");
printGraph(graph);
return 0;
}Output:
Graph Representation:
Adjacency list for vertex 0: 2 -> 1 -> NULL
Adjacency list for vertex 1: 2 -> NULL
Adjacency list for vertex 2: 3 -> 0 -> NULL
Adjacency list for vertex 3: 3 -> NULL
Adjacency list for vertex 4: NULLIn this example, we create a directed graph and print its adjacency list representation.
