CHAPTER 3: DATA STRUCTURE
IN C/C++
D ATA S T R U C T U R E a n d A L G O R I T H M S
M.E. LE THANH TUNG
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.1 Tree in C/C++:
⚬ A tree is a nonlinear hierarchical data
structure that consists of nodes
connected by edges.
⚬ A node is an entity that contains a key or
value and pointers to its child nodes.
⚬ 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.
⚬ The link of any two nodes that can be
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.1 Tree in C/C++:
⚬ Characteristic of tree?
⚬ Root: The root node is the topmost node in the tree hierarchy.
⚬ Child node: the node is a descendant of any node.
⚬ Parent: the node contains any sub-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 which doesn’t have any child node, is called a leaf
node.
⚬ Height: The height of a node is the number of edges from the node to the
deepest leaf. The height of a Tree is the height of the root node.
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.1 Tree in C/C++:
⚬ Types of tree – based on the number of children:
⚬ Binary tree
⚬ Terary tree
⚬ N-ary tree
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.1 Tree in C/C++:
⚬ Types of tree – based on the node values:
⚬ Binary search tree:
⚬ The left subtree of a node contains only
nodes with keys lesser than the node’s
key.
⚬ The right subtree of a node contains
only nodes with keys greater than the
node’s key.
⚬ The left and right subtree each must also
be a binary search tree.
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.1 Tree in C/C++:
⚬ Types of tree – based on the node
values:
⚬ AVL tree (AVL - Adelson-Velsky and
Landis):
⚬ AVL tree is a self-balancing Binary Search
Tree (BST)
⚬ The difference between heights of left
and right subtrees for any node cannot
be more than one.
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.1 Tree in C/C++:
⚬ Types of tree – based on the node
values:
⚬ B-Tree (Balanced tree):
⚬ B-Tree tree is a self-balancing Binary
Search Tree (BST)
⚬ Each node can contain more than one
key and can have more than two
children.
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.1 Tree in C/C++:
⚬ Tree function/operations?
⚬ Insertion: insert an element depending on the location (in the
rightmost, in the leftmost, inserting the element in the first empty
position available).
⚬ Searching: It is a simple process to search in a binary tree to check if
the current node value matches the required value. The process can be
repeated to the right and left subtrees with a recursive algorithm until a
match is found.
⚬ Deleting: When we delete a node, complications may occur to the right
and left children. A deleted node is a leaf node that occurs. Thus, the
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.1 Tree in C/C++:
⚬ Tree implementation in C:
⚬ The binary tree is implemented using the structure (linked list).
⚬ Each node will contain three elements, the data variable, and the 2
pointer variables. The node will point to NULL if it doesn't point to
any children.
⚬ The data of each node contains the assigned value, and the next
points to the node containing the next item.
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.1 Tree in C/C++:
#include <stdio.h>
// Creating tree
struct node {
int data;
struct node *left;
struct node *right;
};
// Create a new Node
struct node* create(int value)
{
struct node* newNode = (struct node *)malloc(sizeof(struct node));
newNode->item = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.1 Tree in C/C++:
#include <stdio.h>
// Insert on the left of the node
struct node* insertLeft(struct node* root, int value)
{
root->left = create(value);
return root->left;
}
// Insert on the right of the node
struct node* insertRight(struct node* root, int value)
{
root->right = create(value);
return root->right;
}
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.2 Graph in C/C++:
⚬ A Graph is a non-linear data structure consisting of vertices (or
nodes) and edges( lines or arcs that connect any two nodes).
⚬ In a graph, more than one edges are allowed between vertices.
Graphs can also have loops, therefore, they do not have a root
node.
⚬ Graphs follow the network model.
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.2 Graph in C/C++:
⚬ Characteristic of graph?
⚬ Vertice (Node): the fundamental units of a graph. Each node typically
represents an entity or an object and may contain additional information
associated with it.
⚬ Edge: Edges are the connections between pairs of nodes. They represent
relationships between the entities represented by the nodes.
⚬ Degree of node: The degree of a node is the number of edges incident to
it.
⚬ Path: A sequence of nodes connected by edges. A path can be simple (no
node is repeated) or may contain repeated nodes, forming a cycle.
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.2 Graph in C/C++:
⚬ Types of graph :
⚬ Directed graph: A graph in which edges
have a direction, i.e., the edges have
arrows indicating the direction of traversal.
Example: A web page graph where links
between pages are directional.
⚬ Un-Directed graph: A graph in which
edges have no direction, i.e., the edges do
not have arrows indicating the direction of
traversal. Example: A social network graph
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.2 Graph in C/C++:
⚬ Types of graph :
⚬ Weighted graph: A graph in which edges have weights or costs
associated with them. Example: A road network graph where the
weights can represent the distance between two cities.
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.2 Graph in C/C++:
⚬ Types of graph :
⚬ Completed graph: A graph with n vertices is called a complete
graph if the degree of each vertex is n-1, that is, one vertex is
attached with n-1 edges or the rest of the vertices in the graph. A
complete graph is also called Full Graph.
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.2 Graph in C/C++:
⚬ Graph function/operations?
⚬ Add: adding a node or a edge.
⚬ Remove: removing a node and its along with all its incident edges or an
edge between two nodes.
⚬ Search:
⚬ Depth-First Search (DFS): Traverses the graph depthwise,
exploring as far as possible along each branch before backtracking.
⚬ Breadth-First Search (BFS): Traverses the graph level by level,
exploring all neighbor nodes before moving to the next level.
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.2 Graph in C/C++:
⚬ Graph implementation in C – using Adjacency Matrix:
⚬ An adjacency matrix: is a square matrix of N x N size where N is
the number of nodes in the graph and it is used to represent the
connections between the edges of a graph.
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.2 Graph in C/C++:
#include <stdio.h>
// Creating graph
struct graph {
int ver;
int edge;
int adjmatrix[100][100];
};
// Add an edge
void addEdge(struct graph *graph, int src, int dest)
{
if (src>=0 && src < graph->ver && dest>=0 && dest < graph->ver)
{
graph->adjmatrix[src][dest] = 1;
graph->edge++;
}
else printf("Invalid edge!\n");
}
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.2 Graph in C/C++:
⚬ Graph implementation in C – using Adjacency List:
⚬ An 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.
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.2 Graph in C/C++:
#include <stdio.h>
// Define structure for a node in the adjacency list
struct Node {
int value;
struct Node* next;
};
// Define structure for the adjacency list
struct AdjList {
struct Node* head;
};
// Define structure for the graph
struct Graph {
int vertices;
struct AdjList* array;
};
3 . 2 N O N - L I N E A R D ATA S T R U C T U R E S :
• 3.2.2 Graph in C/C++:
#include <stdio.h>
// Function to create a new node and add egde to graph
struct Node* createNode(int v) {
struct Node* newNode = (struct Node*)malloc(sizeof(Node));
newNode->value = v;
newNode->next = NULL;
return newNode;
}
void addEdge(int src, int dest)
{
struct Node* newNode = createNode(dest);
newNode->next = AdjList[src];
AdjList[src] = newNode;
newNode = createNode(src);
newNode->next = AdjList[dest];
AdjList[dest] = newNode;
}
DATA STRUCTURE &
ALGORITHMS
THANKS YO U
