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 AT A 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 called edge.
3 . 2 N O N - L I N E A R D AT A 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.
⚬ Depth: The depth of a node is the number of edges from the root to the node.
⚬ Degree of a Node: is the total number of branches of that node.
3 . 2 N O N - L I N E A R D AT A 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 AT A 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 AT A 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 AT A 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 AT A 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 deletion process of a node includes:
Checking if the root is NULL; Searching for an item in the left and right subtree and
recursing it; Deleting the root node of a tree.
3 . 2 N O N - L I N E A R D AT A 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 AT A 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 AT A 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 AT A 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 AT A 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.
⚬ Cycle: A cycle in a graph is a path that starts and ends at the same node. Graphs can be
cyclic or acyclic depending on whether they contain cycles or not.
3 . 2 N O N - L I N E A R D AT A 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 where friendships are not directional..
3 . 2 N O N - L I N E A R D AT A 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 AT A 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 AT A 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 AT A 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 AT A 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 AT A 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 AT A 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 AT A 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 YOU
