DATASTRUCTURE LABmanual

EX NO: 1.
1
TREE TRAVERSAL USING RECURSION
DATE :
AIM:
To implementation of recursive function for tree traversal.
PROCEDURE:
Step1: Start
Step2: To create a node using create node function.
Step3: Read an element (node) using insert node function.
Step4: Using inorder function to arrange elements in the order.
Step4: Print the elements inorder traversal.
Step5: Stop.
SOURCE CODE:
#include<iostream>
using namespace std;
struct node
{
int data;
struct node *left;
struct node
*right;
};
struct node *createnode(int val)
{
struct node *temp=(struct node *)malloc(sizeof(struct node));
temp->data=val;
temp->left=temp-
>right=NULL; return temp;
}
void inorder(struct node *root)
{
if(root!=NULL)
{
inorder(root->left);
cout<<root->data<<"
"; inorder(root->right);
}
}
struct node* insertnode(struct node* node,int val)
{
if(node==NULL)
return
createnode(val);
if(val<node->data)
node->left=insertnode(node->left,val);
else if(val>node->data)
node->right=insertnode(node->right,val);
return node;
}
int main()
{
struct node
*root=NULL;
root=insertnode(root,4);
insertnode(root,5);
insertnode(root,2);
insertnode(root,9);
insertnode(root,1);
insertnode(root,3);
cout<<"inorder traversal of the binary sarch tree is:";
inorder(root);
return 0;
}
OUTPUT
[mca11@localhost mca11]$ gcc tree.cpp -lstdc++

[mca11@localhost mca11]$ ./a.out
inorder traversal of the binary sarch tree is:1 2 3 4 5 9
RESULT:
Thus the program is executed successfully and the output also verified.
EX NO: 1.2
FIBONACCI SERIES USING RECURSION
DATE :
AIM:
To implementation of recursive function for Fibonacci. Series.
PROCEDURE:
Input: Read n value

Output: Prints the nth Fibonacci term
Step1: Start
Step2: Read n value for computing nth term in Fibonacci series
Step3: Calculate the fibonacci function using (fib(x-1)+fib(x-
2)). Step4: Call Fibonacci (x)
Step4: Print the Fibonacci series values.
Step5: Stop
SOURCE CODE:
#include<iostream>
using namespace
std; int fib(int x)
{
if((x==1||x==0))
{return(x);}
else
{
return(fib(x-1)+fib(x-2));
}}
int main()
{
int x,i=0;
cout<<"enter the number of item of
series:"; cin>>x;
cout<<"\n fibinnaci
series:"; while(i<x)
{cout<<" "<<fib(i); i++;}
return 0;
}
OUTPUT
[mca11@localhost mca11]$ gcc funfibo.cpp -lstdc++

Enter the number of item of series:10
fibonacci series: 0 1 1 2 3 5 8 13 21 34
RESULT:
EX NO: 2 ITERATION FUNCTION FOR FIBONACCI
DATE :
AIM
To implementation of iteration function for Fibonacci Series.
PROCEDURE:
Input: Read n value

Output: Prints the nth Fibonacci term
STEP1: Include the required header files (iostream.h and conio.h).
STEP2: Start
STEP3: Initialize the x,y,z values.
STEP4: Create a For loop. In the For loop, the Initialization step is executed and only once in the
whole program. In this step, you can initialize and declare variables for the code. Then the
condition will get evaluated.
STEP5: If the condition is true, then it will execute the code inside the block of For loop. If the
condition is false, it will jump to the code after the For loop without executing the for loop code.
STEP6: After the For loop, the increment statement will be executed. After that again, the condition
will be checked. Loop will get executed if the condition is true, and the loop will repeat itself, i.e. the
body of the loop, an increment statement, and condition. The For loop ends when the condition is
false
STEP7: Print the values

STEP8: Stop
SOURCE CODE
#include<iostream>
using namespace
std; void fib(int
num)
{
int x=0,y=1,z=0;
for(int
i=0;i<num;i++)
{
cout<<x<<"
,"; z=x+y;
x=y
;
y=z
;
}
}
int main()
{
int num;
cout<<"Enter the
number:"; cin>>num;
cout<<"\n The fibonacci
series:"; fib(num);
return 0;
}
OUTPUT
[mca11@localhost mca11]$ gcc loopfibo.cpp -lstdc++
[mca11@localhost mca11]$ ./a.out Enter

the number:10
The fibonacci series:0 ,1 ,1 ,2 ,3 ,5 ,8 ,13 ,21 ,34
RESULT:
Thus the above program was executedsuccessfullyy and output also verified.
EX NO: 3.1
MERGE SORT
DATE :
AIM:
To implementation of Merge Sort in C++.
PROCEDURE:
Step1: Create copies of the L ← subarrays and M ← A[q+1..r].

Step2: Create three pointers i, j and k
1. i maintains current index of L, starting at 1
2. j maintains current index of M, starting at 1
3. k maintains the current index of A[p..q], starting at p.
Step3: until we reach either L or M , Pick the larger among the elements from L and M
and place them in the correct position at A[p..q].
Step4: When we run out of elements either L or M, picking up the remaining elements and put
it A[p..q].
Step5 stop.
SOURCE CODE:
#include<iostream>
using namespace
std;
void swapping(int &a,int &b)
{
int
temp;
temp=a;
a=b;
b=temp;
}
void display(int *array,int size)
{
for(int
i=0;i<size;i++)
cout<<array[i]<<" ";
cout<<endl;
}
void merge(int *array,int l,int m,int r)
{
int
i,j,k,nl,nr;
nl=m-l+1;
nr=r-m;
int larr[nl],rarr[nr];
//fill left and right sun-
arays for(i=0;i<nl;i++)
larr[i]=array[l+i];
for(j=0;j<nr;j++)
rarr[j]=array[m+1+j];
i=0
;
j=0
;
k=l;
//merge temp arrays to real
array while(i<nl&&j<nr)
{
if(larr[i]<=rarr[j])
{
array[k]=larr[i
]; i++;
}
else
{
array[k]=rarr[j]
; j++;
}k++;
}
while(i<nl)//extra element in left array
{
array[k]=larr[i
]; i++;
k++;
}
while(j<nr)
{
array[k]=rarr[j]
; j++;
k++;
}
OUTPUT
[mca37@localhost mca37]$ gcc mergesort.cpp -lstdc++

[mca37@localhost mca37]$
./a.out Enter the number of
elements: 5 Enter elements:
23
44
12
99
5
Array before Sorting: 23 44 12 99 5
Array after Sorting: 5 12 23 44 99
RESULT:
EX NO: 3.2 QUICK SORT
DATE :
AIM:
To implement of Quick Sort in C++.
PROCEDURE:
Step 1 - Consider the first element of the list as pivot (i.e., Element at first position in the
list).
Step 2 - Define two variables i and j. Set i and j to first and last elements of the list
respectively.
Step 3 - Increment i until list[i] > pivot then stop.
Step 4 - Decrement j until list[j] < pivot then stop.
Step 5 - If i < j then exchange list[i] and list[j].
Step 6 - Repeat steps 3,4 & 5 until i > j.
Step 7 - Exchange the pivot element with list[j] element.
SOURCE CODE:
#include<cstdlib>
using namespace
std;
void swap(int *a, int *b)
{
int temp;
temp =
*a;
*a = *b;
*b = temp;
}
Int Partition(int a[], int l, int h)
{
int pivot, index,
i; index = l;
pivot = h;
for(i = l; i < h; i++)
{
if(a[i] < a[pivot])
{
swap(&a[i],
&a[index]); index++;
}
}
swap(&a[pivot],
&a[index]); return index;
}
int RandomPivotPartition(int a[], int l, int h)
{
int pvt, n,
temp; n =
rand();
pvt = l + n%(h-l+1);
swap(&a[h], &a[pvt]);
return Partition(a, l, h);
}
int QuickSort(int a[], int l, int h)
{
int
pindex;
if(l < h) {
pindex = RandomPivotPartition(a, l,
h); QuickSort(a, l, pindex-1);
QuickSort(a, pindex+1, h);
}return 0;
}
int main()
{ int n, i;
cout<<"\nEnter the number of data element to be sorted:
"; cin>>n;
int arr[n];
for(i = 0; i < n; i++)
{
cout<<"Enter element "<<i+1<<":
"; cin>>arr[i];
}
QuickSort(arr, 0, n-1);
cout<<"\nSorted Data
"; for (i = 0; i < n; i++)
cout<<"->"<<arr[i];
return 0;
}
OUTPUT
[mca11@localhost mca11]$ gcc quicksort2.cpp -lstdc++
Enter the number of data element to be sorted: 5

Enter element 1: 3
Enter element 2: 6
Enter element 3: 88
Enter element 4: 22
Enter element 5: 33
Sorted Data ->3->6->22->33->88
RESULT:
EX NO: 4
BINARY SEARCH TREE
DATE :
AIM:
To implement a Binary Search Tree in C++.
PROCEDURE:
Step 1 - Read the search element from the user.

Step 2 - Find the middle element in the sorted list.
Step 3 - Compare the search element with the middle element in the sorted list.
Step4- If both are matched, then display "Given element is found!!!" and terminate the
function.
Step 5-If both are not matched, then check whether the search element is smaller or larger
than the middle element.
Step 6 - If the search element is smaller than middle element, repeat steps 2, 3, 4 and 5 for the
left sublist of the middle element.
Step 7 - If the search element is larger than middle element, repeat steps 2, 3, 4 and 5 for the
right sublist of the middle element.
Step 8 - Repeat the same process until we find the search element in the list or until sublist
contains only one element.
Step 9 - If that element also doesn't match with the search element, then display "Element is
not found in the list!!!" and terminate the function.
SOURCE CODE
#include<iostream> using
namespace std;
int binarySearch(int arr[], int p, int r, int num) { if (p <=
r) {
int mid = (p + r)/2; if (arr[mid] ==
num)
return mid ;
if (arr[mid] > num)
return binarySearch(arr, p, mid-1, num); if (arr[mid] <
num)
return binarySearch(arr, mid+1, r, num);
}
return -1;
}
int main(void) {
int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
int n = sizeof(arr)/ sizeof(arr[0]); int num;
cout << "Enter the number to search: \n"; cin >>
num;
int index = binarySearch (arr, 0, n-1, num); if(index ==
-1){
cout<< num <<" is not present in the array";
}else{
cout<< num <<" is present at index "<< index <<" in the array";
}
return 0;
}
OUTPUT
mca37@localhost mca37]$ gcc bs.cpp -lstdc++
mca37@localhost mca37]$ ./a.out

Enter the number to search:1
1 is present at index 0 in the array [mca37@localhost mca37]$
./a.out
Enter the number to search: 4
4 is not present in the array
RESULT:
EX NO: 5
RED-BLACK TREE
DATE :
AIM:
To create a binary search tree using Red-Black Tree Implementation.
PROCEDURE:
A red-black tree must satisfy these properties:

1. The root is always black.
2. A nil is recognized to be black. This factor that every non-NIL node has two children.
3. Black Children Rule: The children of any red node are black.
4. Black Height Rule: For particular node v, there exists an integer bh (v) such that specific downward path
from v to a nil has correctly bh (v) black real (i.e. non-nil) nodes. Call this portion the black height of v. We
determine the black height of an RB tree to be the black height of its root.
Insertion:
o Insert the new node the way it is done in Binary Search Trees.
o Color the node red
o If an inconsistency arises for the red-black tree, fix the tree according to the type of discrepancy.
Deletion:
First, search for an element to be deleted
o If the element to be deleted is in a node with only left child, swap this node with one containing the largest
element in the left subtree. (This node has no right child).
o If the element to be deleted is in a node with only right child, swap this node with the one containing the
smallest element in the right subtree (This node has no left child).
o If the element to be deleted is in a node with both a left child and a right child, then swap in any of the
above two ways. While swapping, swap only the keys but not the colors.
o The item to be deleted is now having only a left child or only a right child. Replace this node with its sole
child. This may violate red constraints or black constraint. Violation of red constraints can be easily fixed.
o If the deleted node is black, the black constraint is violated. The elimination of a black node y causes any
path that contained y to have one fewer black node.
o Two cases arise:
o The replacing node is red, in which case we merely color it black to make up for the loss of one black node.
o The replacing node is black.
SOURCE CODE:
#include
<bits/stdc++> using
namespace std;
enum Color {RED,
BLACK}; struct Node
{
int data; bool
color;
Node *left, *right, *parent;
// Constructor
Node(int data)
{
this->data = data;
left = right = parent = NULL; this-
>color = RED;
}
};
// Class to represent Red-Black
Tree class RBTree
{
private:
Node *root;
protected:
void rotateLeft(Node *&, Node *&); void
rotateRight (Node *&, Node *&); void
fixViolation (Node *&, Node *&);
// Constructor
public RBTree() { root = NULL; } void insert(const int &n);
void inorder();
void levelOrder();
// A recursive function to do inorder
traversal void inorderHelper(Node *root)
{
if (root == NULL)
return;
inorderHelper(root->left); cout
<< root->data << " ";
inorderHelper(root->right);
}
/* A utility function to insert a new node with given key in BST */
Node* BSTInsert(Node* root, Node *pt)
{
/* If the tree is empty, return a new node */ if
(root == NULL)
return pt;
/* Otherwise, recur down the tree */ if (pt-

>data < root->data)
{
root->left = BSTInsert(root->left, pt); root->left-
>parent = root;
}
else if (pt->data > root->data)
{
root->right = BSTInsert(root->right, pt); root->right-
>parent = root;
}
/* return the (unchanged) node pointer */ return
root;
}
// Utility function to do level order
traversal void levelOrderHelper(Node
*root)
{
if (root == NULL)
return;
std::queue<Node *> q;
q.push(root);
while (!q.empty())
{
Node *temp = q.front(); cout << temp-
>data << " "; q.pop();
if (temp->left != NULL)
q.push(temp->left); if (temp-
>right != NULL)
q.push(temp->right);
}
}
void RBTree::rotateLeft(Node *&root, Node *&pt)
{
Node *pt_right = pt->right; pt-
>right = pt_right->left;
if (pt->right != NULL)
pt->right->parent = pt;
pt_right->parent = pt->parent; if (pt-
>parent == NULL)
root = pt_right;
else if (pt == pt->parent->left)
pt->parent->left = pt_right;
else
pt->parent->right = pt_right;
pt_right->left = pt;
pt->parent = pt_right;
}
void RBTree::rotateRight(Node *&root, Node *&pt)
{
Node *pt_left = pt->left; pt-
>left = pt_left->right;
if (pt->left != NULL)
pt->left->parent = pt;
pt_left->parent = pt->parent;
if (pt->parent == NULL)
root = pt_left;
else if (pt == pt->parent->left)

pt->parent->left = pt_left;
else
pt->parent->right = pt_left;
pt_left->right = pt;
pt->parent = pt_left;
}
// This function fixes violations
// caused by BST insertion
void RBTree::fixViolation(Node *&root, Node *&pt)
{
Node *parent_pt = NULL;
Node *grand_parent_pt = NULL;
while ((pt != root) && (pt->color != BLACK) && (pt->parent-
>color == RED))
{
parent_pt = pt->parent; grand_parent_pt = pt-
>parent->parent;
/* Case : A
Parent of pt is left child of Grand-parent of pt
*/
if (parent_pt == grand_parent_pt->left)
{
Node *uncle_pt = grand_parent_pt->right;
/* Case : 1
The uncle of pt is also red Only
Recoloring required */
if (uncle_pt != NULL && uncle_pt->color ==

{
grand_parent_pt->color = RED;
parent_pt>color = BLACK; uncle_pt-
>color = BLACK;
pt = grand_parent_pt;RED)
}
else
{
/* Case : 2
pt is right child of its parent Left-rotation
required */
if (pt == parent_pt->right)
rotateLe
ft(root,
parent_p
t); pt =
parent_p
t;
parent_pt = pt->parent;
}
/* Case : 3
pt is left child of its parent Right-rotation required */
rotateRight(root, grand_parent_pt); swap(parent_pt->color,
grand_parent_pt->color);
pt = parent_pt;
}
}
/* Case : B
Parent of pt is right child of Grand-
parent of pt */ else
{
Node *uncle_pt = grand_parent_pt->left;
/* Case : 1
The uncle of pt is also red Only
Recoloring required */
if ((uncle_pt != NULL) && (uncle_pt->color == RED))
{
grand_parent_pt->color = RED;
parent_pt->color = BLACK; uncle_pt-
>color = BLACK;
pt = grand_parent_pt;
}
else
{
/* Case : 2
pt is left child of its parent Right-rotation
required */ if (pt == parent_pt->left)
{
rotateRig
ht(root,
parent_pt
); pt =
parent_pt;
parent_pt = pt->parent;
}
/* Case : 3
pt is right child of its parent Left-rotation required */
rotateLeft(root, grand_parent_pt); swap(parent_pt->color,
grand_parent_pt->color);
pt = parent_pt;
}
}
}
root->color = BLACK;
}
// Function to insert a new node with given
data void RBTree::insert(const int &data)
{
Node *pt = new Node(data);
// Do a normal BST insert root =
BSTInsert(root, pt);
// fix Red Black Tree violations
fixViolation(root, pt);
}
// Function to do inorder and level order traversals
void RBTree::inorder() { inorderHelper(root);}
void RBTree::levelOrder() { levelOrderHelper(root);
}
// Driver
Code int
main()
{
RBTree tree;
tree.insert(7);
tree.insert(6);
tree.insert(5);
tree.insert(4);
tree.insert(3);
tree.insert(2);
tree.insert(1);
cout << "Inorder Traversal of Created Tree\n";
tree.inorder();
cout << "\n\nLevel Order Traversal of Created Tree\n";
tree.levelOrder();
return 0;
}
OUTPUT
Inorder Traversal of Created

Tree 1 2 3 4 5 6 7
Level Order Traversal of Created
Tree 6 4 7 2 5 1 3
RESULT
EX NO: 6
HEAP IMPLEMENTATION
DATE :
AIM:
To implement Heap in C++.
PROCEDURE:
1. Let the input array be Initial Array
2. Create a complete binary tree from the arrayComplete binary tree
3. Start from the first index of non-leaf node whose index is given by n/2 - 1.Start from the firston leaf node.
4. Set current element i as largest
5. The index of the left child 2i+1 and right child 2i+2. If left child is greater than current element (i.e. element in
ith index), set leftchild is largest.
6. Otherwise rihgtchils is largest.
7. Swap largest element with current element if necessary.
8. Repeat step 3 – 7 until the subtree also heapified.

SOURCE CODE:
#include
<iostream> using
namespace std;
void min_heap(int *a, int m, int n){
int j, t;
t= a[m];
j = 2 * m; while
(j <= n) {
if (j < n && a[j+1] < a[j]) j = j
+ 1;
if (t < a[j])
break;
else if (t >= a[j]) {
a[j/2] = a[j]; j =
2 * j;
}
}
a[j/2] = t;
return;
}
void build_minheap(int *a, int n) {
int k;
for(k = n/2; k >= 1; k--) {
min_heap(a,k,n);
}
}
int main() {
int n, i;
cout<<"enter no of elements of array\n";
cin>>n;
int a[30];
for (i = 1; i <= n; i++) {
cout<<"enter element"<<" "<<(i)<<endl;
cin>>a[i];
}
build_minheap(a, n);
cout<<"Min Heap\n";
for (i = 1; i <= n; i++) {
cout<<a[i]<<endl;
}
return 0;}
OUTPUT
enter no of elements of array 5

enter element 1
7
enter element 2
6
enter element 3
2
enter element 4
1
enter element 5
4
Min Heap 1
4
2
6
7
RESULT:
EX NO: 7
DATE : FIBONACCI HEAP IMPLEMENTATION
AIM:
To implementation Fibonacci Heap
PROCEDURE:
Insertion
1. Create a new node for the element.

2. Check if the heap is empty.
3. If the heap is empty, set the new node as a root node and mark it min.
4. Else, insert the node into the root list and update min.
Extract Min
It is the most important operation on a fibonacci heap. In this operation, the node with minimum value is
removed from the heap and the tree is re-adjusted.
The following steps are followed:
1. Delete the min node.
2. Set the min-pointer to the next root in the root list.
3. Create an array of size equal to the maximum degree of the trees in the heap before deletion.
4. Do the following (steps 5-7) until there are no multiple roots with the same degree.
5. Map the degree of current root (min-pointer) to the degree in the array.
6. Map the degree of next root to the degree in array.
7. If there are more than two mappings for the same degree, then apply union operation to those roots such
that the min-heap property is maintained (i.e. the minimum is at the root).
SOURCE CODE:
#include <iostream> #include

<cmath> #include <cstdlib>
/*
* Node Declaration
*/
struct node
{
int n;
int degree; node* parent; node*
child; node* left; node* right;
char mark; char C;
};
/*
* Class Declaration
*/
class FibonacciHeap
{
private:
int nH; node *H;
public:
node* InitializeHeap();
int Fibonnaci_link(node*, node*, node*); node
*Create_node(int);
node *Insert(node *, node *); node *Union(node *,
node *); node *Extract_Min(node *); int
Consolidate(node *);
int Display(node *); node *Find(node *, int);
int Decrease_key(node *, int, int); int Delete_key(node
*,int);
int Cut(node *, node *, node *); int Cascase_cut(node
*, node *); FibonacciHeap()
{
H = InitializeHeap();
}
};
/*
* Initialize Heap
*/
node* FibonacciHeap::InitializeHeap()
{
node* np; np = NULL;
return np;
}
/*
* Create Node
*/
node* FibonacciHeap::Create_node(int value)
{
node* x = new node; x->n = value;
return x;
}
/*
* Insert Node
*/
node* FibonacciHeap::Insert(node* H, node* x)
{
x->degree = 0;
x->parent = NULL; x->child = NULL;
x->left = x;
x->right = x; x->mark = 'F';
x->C = 'N';
if (H != NULL)
{
(H->left)->right = x; x->right = H;
x->left = H->left;
H->left = x;
if (x->n < H->n) H = x;
}
else
{
H = x;
}
nH = nH + 1;
return H;
}
/*
* Link Nodes in Fibonnaci Heap*/
int FibonacciHeap::Fibonnaci_link(node* H1, node* y, node* z)
{
(y->left)->right = y->right; (y->right)->left =
y->left; if (z->right == z)
H1 = z;
y->left = y; y->right = y;
y->parent = z;
if (z->child == NULL) z->child = y;
y->right = z->child;
y->left = (z->child)->left; ((z->child)->left)-
>right = y; (z->child)->left = y;
if (y->n < (z->child)->n) z->child = y;
z->degree++;
}
/*
* Union Nodes in Fibonnaci Heap
*/
node* FibonacciHeap::Union(node* H1, node* H2)
{
node* np;
node* H = InitializeHeap(); H = H1;
(H->left)->right = H2; (H2->left)->right
= H; np = H->left;
H->left = H2->left; H2->left = np;
return H;
}
/*
* Display Fibonnaci Heap
*/
int FibonacciHeap::Display(node* H)
{
node* p = H;
if (p == NULL)
{
cout<<"The Heap is Empty"<<endl; return 0;
}
cout<<"The root nodes of Heap are: "<<endl; do
{cout<<p->n; p = p->right; if (p != H)
{
cout<<"-->";
}
}
while (p != H && p->right != NULL); cout<<endl;
}
/*
* Extract Min Node in Fibonnaci Heap
*/
node* FibonacciHeap::Extract_Min(node* H1)
{
node* p; node* ptr; node* z =
H1; p = z;
ptr = z;
if (z == NULL)
return z; node* x; node* np;
x = NULL;
if (z->child != NULL) x = z->child;
if (x != NULL)
{
ptr = x; do
{
np = x->right;
(H1->left)->right = x; x->right = H1;
x->left = H1->left;
H1->left = x;
if (x->n < H1->n) H1 = x;
x->parent = NULL; x = np;
}
while (np != ptr);
}
(z->left)->right = z->right; (z->right)->left =
z->left; H1 = z->right;
if (z == z->right && z->child == NULL) H = NULL;else
{
H1 = z->right;
Consolidate(H1);
}
nH = nH - 1;
return p;
}
/*
* Consolidate Node in Fibonnaci Heap
*/
int FibonacciHeap::Consolidate(node* H1)
{
int d, i;
float f = (log(nH)) / (log(2)); int D = f;
node* A[D];
for (i = 0; i <= D; i++) A[i] = NULL;
node* x = H1; node* y; node* np;
node* pt = x; do
{
pt = pt->right; d = x->degree;
while (A[d] != NULL)
{
y = A[d];
if (x->n > y->n)
{
np = x; x = y; y = np;
}
if (y == H1) H1 = x;
Fibonnaci_link(H1, y, x); if (x->right == x)
H1 = x;
A[d] = NULL;
d = d + 1;
}
A[d] = x;
x = x->right;
}
while (x != H1); H = NULL;for (int
j = 0; j <= D; j++)
{
if (A[j] != NULL)
{
A[j]->left = A[j];
A[j]->right =A[j]; if (H != NULL)
{
(H->left)->right = A[j]; A[j]->right = H;
A[j]->left = H->left;
H->left = A[j];
if (A[j]->n < H->n) H = A[j];
}
else
{
H = A[j];
}
if(H == NULL) H = A[j];
else if (A[j]->n < H->n) H = A[j];
}
}
}
/*
* Decrease key of Nodes in Fibonnaci Heap
*/
int FibonacciHeap::Decrease_key(node*H1, int x, int k)
{
node* y;
if (H1 == NULL)
{
cout<<"The Heap is Empty"<<endl; return 0;
}
node* ptr = Find(H1, x); if (ptr == NULL)
{
cout<<"Node not found in the Heap"<<endl; return 1;
}
if (ptr->n < k)
{
cout<<"Entered key greater than current key"<<endl; return 0;}ptr->n = k;
y = ptr->parent;
if (y != NULL && ptr->n < y->n)
{
Cut(H1, ptr, y); Cascase_cut(H1, y);
}
if (ptr->n < H->n) H = ptr;
return 0;
}
/*
* Cut Nodes in Fibonnaci Heap
*/
int FibonacciHeap::Cut(node* H1, node* x, node* y)
{
if (x == x->right)
y->child = NULL;
(x->left)->right = x->right; (x->right)->left =
x->left; if (x == y->child)
y->child = x->right;
y->degree = y->degree - 1; x->right = x;
x->left = x;
(H1->left)->right = x; x->right = H1;
x->left = H1->left;
H1->left = x;
x->parent = NULL; x->mark = 'F';
}
/*
* Cascade Cutting in Fibonnaci Heap
*/
int FibonacciHeap::Cascase_cut(node* H1, node* y)
{
node* z = y->parent; if (z != NULL)
{
if (y->mark == 'F')
{
y->mark = 'T';
}
else
{
Cut(H1, y, z); Cascase_cut(H1, z);}
}
}
/*
* Find Nodes in Fibonnaci Heap
*/
node* FibonacciHeap::Find(node* H, int k)
{
node* x = H; x->C = 'Y';
node* p = NULL; if (x->n == k)
{
p = x;
x->C = 'N';
return p;
}
if (p == NULL)
{
if (x->child != NULL ) p = Find(x->child, k);
if ((x->right)->C != 'Y' ) p = Find(x->right, k);
}
x->C = 'N';
return p;
}
/*
* Delete Nodes in Fibonnaci Heap
*/
int FibonacciHeap::Delete_key(node* H1, int k)
{
node* np = NULL; int t;
t = Decrease_key(H1, k, -5000); if (!t)
np = Extract_Min(H); if (np != NULL)
cout<<"Key Deleted"<<endl; else
cout<<"Key not Deleted"<<endl; return 0;
}/*
* Main Contains Menu
*/
int main()
{int n, m, l; FibonacciHeap fh; node* p;
node* H;
H = fh.InitializeHeap(); while (1)
{
cout<<" "<<endl;
cout<<"Operations on Binomial heap"<<endl; cout<<" "<<endl;
cout<<"1)Insert Element in the heap"<<endl; cout<<"2)Extract
Minimum key node"<<endl; cout<<"3)Decrease key of a
node"<<endl; cout<<"4)Delete a node"<<endl; cout<<"5)Display
Heap"<<endl; cout<<"6)Exit"<<endl;
cout<<"Enter Your Choice: "; cin>>l;
switch(l)
{
case 1:
cout<<"Enter the element to be inserted: "; cin>>m;
p = fh.Create_node(m); H = fh.Insert(H, p);
break;
case 2:
p = fh.Extract_Min(H); if (p != NULL)
cout<<"The node with minimum key: "<<p->n<<endl; else
cout<<"Heap is empty"<<endl; break;
case 3:
cout<<"Enter the key to be decreased: "; cin>>m;
cout<<"Enter new key value: "; cin>>l;
fh.Decrease_key(H, m, l); break;
case 4:
cout<<"Enter the key to be deleted: "; cin>>m;
fh.Delete_key(H, m); break;
case 5:
cout<<"The Heap is: "<<endl; fh.Display(H);
break;case 6:
exit(1); default:
cout<<"Wrong Choice"<<endl;
}
}
return 0;
}
OUTPUT
$ g++ fibonnaciheap.cpp –lstdc++

$ a.out
----------------------------
Operations on Binomial heap
1) Insert Element in the heap

2) Extract Minimum key node
3)Decrease key of a node 4)Delete a
node
5)Display Heap 6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 9

node

node

node

node

node
Enter Your Choice: 5 The Heap
is:
The root nodes of Heap are: 5-->6--
>7-->8-->9

node
The node with minimum key: 5

node
Enter the key to be decreased: 3 Enter
new key value: 1
Node not found in the Heap

node
Enter the key to be decreased: 5 Enter
new key value: 2

node
The node with minimum key: 2

node
(program exited with code: 1)
Press return to continue
RESULT:
EX NO: 8.1
DATE : GRAPH TRAVESALS-BFS
AIM:
To create a graph traversal (BFS) using C++.
PROCEDURE:
BFS (Breadth First Search)
Step 1 - Define a Queue of size total number of vertices in the graph.

Step 2 - Select any vertex as starting point for traversal. Visit that vertex and insert it into the Queue.
Step 3 - Visit all the non-visited adjacent vertices of the vertex which is at front of the Queue and insert them
into the Queue.
Step 4 - When there is no new vertex to be visited from the vertex which is at front of the Queue then delete
that vertex.
Step 5 - Repeat steps 3 and 4 until queue becomes empty.
Step 6 - When queue becomes empty, then produce final spanning tree by removing unused edges from the
graph
SOURCE CODE:
#include<iostream>
#include<list>
using namespace
std; class Graph {
int numVertices;
list<int>*
adjLists; bool*
visited; public:
Graph(int vertices);
void addEdge(int src, int
dest); void BFS(int
startVertex);
}; //
Create a graph with given vertices,
// and maintain an adjacency
list Graph::Graph(int vertices)
{ numVertices = vertices;
adjLists = new list<int>[vertices];
} //
Add edges to the graph
void Graph::addEdge(int src, int dest)
{ adjLists[src].push_back(dest);
adjLists[dest].push_back(src);
} //
BFS algorithm
void Graph::BFS(int startVertex)
{ visited = new
bool[numVertices]; for (int i = 0; i
< numVertices; i++) visited[i] =
false;
list<int> queue;
visited[startVertex] = true;
queue.push_back(startVertex);
list<int>::iterator i;
while (!queue.empty()) {
int currVertex = queue.front();
cout << "Visited " << currVertex << "
"; queue.pop_front();
for (i = adjLists[currVertex].begin(); i != adjLists[currVertex].end(); ++i)
{
int adjVertex = *i;
if (!visited[adjVertex]) {
visited[adjVertex] = true;
queue.push_back(adjVertex);
}
}
}
}
int main()
{
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.BFS(2);
return 0;
}
OUTPUT
[mca11@localhost mca11]$ gcc graphdfs.cpp -lstdc++

Visited 2 Visited 0 Visited 1 Visited
3
RESULT:
EX NO: 8.2
GRAPH TRAVESALS-DFS
DATE :
AIM:
To create a graph traversal(DFS) using C++.
PROCEDURE:
DFS traversal
Step 1 - Define a Stack of size total number of vertices in the graph.

Step 2 - Select any vertex as starting point for traversal. Visit that vertex and push it on to the
Stack.
Step 3 - Visit any one of the non-visited adjacent vertices of a vertex which is at the top of stack
and push it on to the stack.
Step 4 - Repeat step 3 until there is no new vertex to be visited from the vertex which is at the top
of the stack.
Step 5 - When there is no new vertex to visit then use back tracking and pop one vertex from the
stack.
Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty.
Step 7 - When stack becomes Empty, then produce final spanning tree by removing unused edges
from the graph
SOURCE CODE
#include
<iostream>
#include<vector>
using namespace
std;
int main()
{
cout << " ===== Program to demonstrate the DFS Traversal on a Graph, in CPP ===== \n\n";
//variable declaration
int cost[10][10], i, j, k, n, e, top, v, stk[10], visit[10], visited[10];
cout << "Enter the number of vertices in the Graph: ";
cin >> n;
cout << "\nEnter the number of edges in the Graph : ";
cin >> e;
cout << "\nEnter the start and end vertex of the edges: \n";
for (k = 1; k <= e; k++)
{
cin >> i >> j;
cost[i][j] = 1;
}
cout << "\nEnter the initial vertex to start the DFS traversal with: ";
cin >> v;
cout << "\nThe DFS traversal on the given graph is : \n";
cout << v << " ";
//As we start with the vertex v, marking it visited to avoid visiting again
visited[v] = 1;
k = 1;
//The DFS Traversal Logic
while (k < n)
{
for (j = n; j >= 1; j--)
{
if (cost[v][j] != 0 && visited[j] != 1 && visit[j] != 1)
{
visit[j] = 1;
//put all the vertices that are connected to the visited vertex into a stack stk[top]
= j;
top++;
}
}
//output all the connected vertices one at a time v =

stk[--top];
cout << v << " ";
k++;
//as v is visited so it is not a valid candidate to visit in future so visit[v]=0 and visited[v]=1
visit[v] = 0;
//to mark it visited
visited[v] = 1;
}
cout << "\n\n\n";
return 0;
}
OUTPUT
[mca11@localhost mca11]$ gcc graphbfs.cpp -lstdc++
Enter the number of vertices in the Graph:4 Enter

the number of edges in the Graph:4
Enter the start and end vertex of the edges: 1
2
1
3
3
4
Enter the initial vertex to start the DFS traversal with:1 The
DFS traversal on the given graph is :
1234
RESULT:
EX NO:9
SPANNING TREE IMPLEMENTATION
DATE :
AIM:
To create a Spanning Tree Implementation using C++.
PROCEDURE:
Step 1: Choose any vertex as a starting vertex.

Step 2: Pick an edge connecting any tree vertex and fringe vertex (adjacent vertex to visited vertex)
having the minimum edge weight.
Step 3: Add the selected edge to MST only if it doesn't form any closed cycle.
Step 4: Keep repeating steps 2 and 3 until the fringe vertices exist.
Step 5: End.
SOURCE CODE:
#include<iostream>
using namespace
std;
// Number of vertices in the
graph const int V=6;
// Function to find the vertex with minimum key
value int min_Key(int key[], bool visited[])
{
int min = 999, min_index; // 999 represents an Infinite value
for (int v = 0; v < V; v++) {

if (visited[v] == false && key[v] < min) {
// vertex should not be visited min =
key[v];
min_index = v;
}
}
return min_index;
}
// Function to print the final MST stored in
parent[] int print_MST(int parent[], int
cost[V][V])
{
int minCost=0;
cout<<"Edge \tWeight\n";
for (int i = 1; i< V; i++) {
cout<<parent[i]<<" - "<<i<<" \t"<<cost[i][parent[i]]<<" \n";
minCost+=cost[i][parent[i]];
}
cout<<"Total cost is"<<minCost;
}
// Function to find the MST using adjacency cost matrix
representation void find_MST(int cost[V][V])
{
int parent[V], key[V];
bool visited[V];
// Initialize all the arrays
for (int i = 0; i< V; i++) {
key[i] = 999; // 99 represents an Infinite value
visited[i] = false;
parent[i]=-1;
}
key[0] = 0; // Include first vertex in MST by setting its key vaue to 0.
parent[0] = -1; // First node is always root of MST
// The MST will have maximum V-1 vertices
for (int x = 0; x < V - 1; x++)
{
// Finding the minimum key vertex from the
//set of vertices not yet included in MST int
u = min_Key(key, visited);
visited[u] = true; // Add the minimum key vertex to the MST
// Update key and parent arrays for
(int v = 0; v < V; v++)
{
// cost[u][v] is non zero only for adjacent vertices of u
// visited[v] is false for vertices not yet included in MST
// key[] gets updated only if cost[u][v] is smaller than key[v]
if (cost[u][v]!=0 && visited[v] == false && cost[u][v] < key[v])
{
parent[v] = u; key[v] =
cost[u][v];
}
}
}
// print the final MST
print_MST(parent, cost);
}
// main
function int
main()
{
int cost[V][V];
cout<<"Enter the vertices for a graph with 6 vetices";
for (int i=0;i<V;i++)
{
for(int j=0;j<V;j++)
{
cin>>cost[i][j];
}
}
find_MST(cost);
return 0;
OUTPUT
[mca37@localhost mca37]$ gcc s.cpp -lstdc++
Enter the vertices for a graph with 6

vetices 0 4 0 0 0 2
406003
060301
003020
000204
231040
Edge Weight
5-1 3
5-2 1
2-3 3
3-4 2
0-5 2
Total cost is 11
RESULT:
.
EX NO:10.1
DATE : SHORTEST PATH ALGORITHMS -DIJKSTRA ALGORITHM
AIM:
To create a Dijkstra's Algorithm using C++.
PROCEDURE
1. Convert any problem to its graph equivalent representation.
2. Maintain a list of unvisited vertices. Assign a vertex as “source” and also allocate a maximum
possible cost (infinity) to every other vertex. The cost of the source to itselfwill be zero as it
actually takes nothing to go to itself.
3. In every step of the algorithm, it tries to minimize the cost for each vertex.
4. For every unvisited neighbor (V2, V3) of the current vertex (V1) calculate the new cost from V1.
5. The new cost of V2 is calculated as :
Minimum( existing cost of V2 , (sum of cost of V1 + the cost of edge from V1 to V2) )
7. When all the neighbors of the current node are visited and cost has been calculated,
mark the current node V1 as visited and remove it from the unvisited list.
8. Select next vertex with smallest cost from the unvisited list and repeat from step 4.
9. The algorithm finally ends when there are no unvisited nodes left.
SOURCE CODE:
#include<iostream>
#include<climits> using
namespace std;
int miniDist(int distance[], bool Tset[]) // finding minimum distance
{
int minimum=INT_MAX,ind;
for(int k=0;k<6;k++)
{
if(Tset[k]==false && distance[k]<=minimum)
{
minimum=distance[k]; ind=k;
}
}
return ind;
}
void DijkstraAlgo(int graph[6][6],int src) // adjacency matrix
{
int distance[6]; // // array to calculate the minimum distance for each node bool
Tset[6];// boolean array to mark visited and unvisited for each node
for(int k = 0; k<6; k++)
{
distance[k] = INT_MAX; Tset[k] =
false;
}
distance[src] = 0; // Source vertex distance is set 0
for(int k = 0; k<6; k++)

{
int m=miniDist(distance,Tset); Tset[m]=true;
for(int k = 0; k<6; k++)
{
// updating the distance of neighbouring vertex
if(!Tset[k] && graph[m][k] && distance[m]!=INT_MAX &&
distance[m]+graph[m][k]<distance[k])
distance[k]=distance[m]+graph[m][k];
}
}
cout<<"Vertex\t\tDistance from source vertex"<<endl;
for(int k = 0; k<6; k++)
{
char str=65+k; cout<<str<<"\t\t\t"<<distance[k]<<endl;
}}
int main()
{
int graph[6][6]={
{0, 1, 2, 0, 0, 0},
{1, 0, 0, 5, 1, 0},
{2, 0, 0, 2, 3, 0},
{0, 5, 2, 0, 2, 2},
{0, 1, 3, 2, 0, 1},
{0, 0, 0, 2, 1, 0}};
DijkstraAlgo(graph,0);
return 0;
}
OUTPUT
[mca37@localhost mca37]$ gcc dij.cpp -lstdc++
Verte Distance from source

x vertex
A 0
B 1
C 2
D 4
E 2
F 3
RESULT:
EX NO:10.2 SHORTEST PATH ALGORITHM BELLMAN
DATE : FORD ALGORITHM
AIM:
To create a Bellman Ford Algorithm using C++.
PROCEDURE:
1) Initializing the source vertex with distance to itself as 0 and all other vertices as
infinity.Creating the array with size N
2) Calculate the shortest distance from the source vertex. Following this process for N-
1times where N is the number of vertices in the graph
3) For relaxing the path lengths for the vertices for each edge m-n:
o if distance[n] > distance[m] + weight of edge mn, then

o distance[n] = distance[m] + weight of edge mn
4) Even after minimizing the path lengths for each vertex after N-1 times, if we can still relax the
path length where distance[n] > distance[m] + weight of edge mn then we can say that the graph
contains the negative edge cycle.
SOURCE CODE:
#include<iostream>
#define MAX 10
using namespace
std;
typedef struct edge
{
int src;
int dest;
int wt;
}edge;
void bellman_ford(int nv,edge e[],int src_graph,int ne)
{
int u,v,weight,i,j=0;
int dis[MAX];
/* initializing array 'dis' with 999. 999 denotes infinite distance */
for(i=0;i<nv;i++)
{
dis[i]=999;
}
/* distance of source vertex from source vertex is o */
dis[src_graph]=0;
/* relaxing all the edges nv - 1 times */
for(i=0;i<nv-1;i++)
{
for(j=0;j<ne;j++)
{
u=e[j].src;
v=e[j].dest;
weight=e[j].wt;
if(dis[u]!=999 && dis[u]+weight < dis[v])
{
dis[v]=dis[u]+weight;
}
}}
/* checking if negative cycle is present */
for(j=0;j<ne;j++)
{
u=e[j].src;
v=e[j].dest;
weight=e[j].wt;
if(dis[u]+weight < dis[v])
{
cout<<"\n\nNEGATIVE CYCLE PRESENT..!!\n";
return;
}
}
cout<<"\nVertex"<<" Distance from source";
for(i=1;i<=nv;i++)
{
cout<<"\n"<<i<<"\t"<<dis[i];
}
}
int main()
{
int nv,ne,src_graph;
edge e[MAX];
cout<<"Enter the number of vertices: ";
cin>>nv;
/* if you enter no of vertices: 5 then vertices will be 1,2,3,4,5. so while gi
ving input enter source and destination vertex accordingly */ 20,1 46%
printf("Enter the source vertex of the graph: ");
cin>>src_graph;
cout<<"\nEnter no. of edges: ";
cin>>ne;
for(int i=0;i<ne;i++)
{
cout<<"\nFor edge "<<i+1<<"=>";
cout<<"\nEnter source vertex :";
cin>>e[i].src;
cout<<"Enter destination vertex :";
cin>>e[i].dest;
cout<<"Enter weight :";
cin>>e[i].wt;
}
bellman_ford(nv,e,src_graph,ne);
return 0;
}
OUTPUT
[mca37@localhost mca37]$ gcc b.cpp -lstdc++
vertices: 4
Enter the source vertex of the graph:
1 Enter no. of edges: 4
RESULT:
EX NO:11 MATRIX CHAIN MULTIPLICATION
DATE :
AIM:
To create a Matrix Chain Multiplication using C++.
ALGORITHM:
MATRIX-CHAIN-ORDER (p)
1. n length[p]-1
2. for i ← 1 to n
3. do m [i, i] ← 0
4. for l ← 2 to n // l is the chain length
5. do for i ← 1 to n-l + 1
6. do j ← i+ l -1
7. m[i,j] ← ∞
8. for k ← i to j-1
9. do q ← m [i, k] + m [k + 1, j] + pi-1 pk pj
10. If q < m [i,j]
11. then m [i,j] ← q
12. s [i,j] ← k
13. return m and s.

SOURCE CODE:
#include<iostream>
using namespace
std;
int matOrder(int array[], int n){
int minMul[n][n]; //holds the number of scalar multiplication needed
for (int i=1; i<n; i++)
minMul[i][i] = 0; //for multiplication with 1 matrix, cost is 0
for (int length=2; length<n; length++){ //find the chain length starting from 2 for
(int i=1; i<n-length+1; i++){
int j = i+length-1;
minMul[i][j] = INT_MAX; //set to infinity for
(int k=i; k<=j-1; k++){
//store cost per multiplications
int q = minMul[i][k] + minMul[k+1][j] + array[i-1]*array[k]*array[j]; if (q <
minMul[i][j])
minMul[i][j] = q;
}
}
}
return minMul[1][n-1];
}
int main(){
int arr[] = {1, 2, 3, 4};
int size = 4;
cout << "Minimum number of matrix multiplications: "<<matOrder(arr, size);
}
OUTPUT
Minimum number of matrix multiplications: 18
RESULT:
EX NO:12.1
ACTIVITY SELECTION IMPLEMENTATION
DATE :
AIM:
To implement activity selection problem using C++.
PROCEDURE
Input - A list of activity, and the number of elements in the list.

Output - The order of activities how the have been chosen.
Begin
initially sort the given activity List set i := 1
display the i-th activity //in this case it is the first activity for j := 1 to n-1 do
if start time of act[j] >= end of act[i] then display the jth activity
i := j
done End
SOURCE CODE:
#include<iostream>
#include<algorithm
> using namespace
std; struct Activitiy{
int start, end;
};
bool comp(Activitiy act1, Activitiy act2){
return (act1.end < act2.end);
}
void maxActivity(Activitiy act[], int n){
//sort activities using compare function
sort(act, act+n, comp);
cout << "Selected Activities are: " << endl;
int i = 0;// first activity as 0 is selected
cout << "Activity: " << i << " , Start: " <<act[i].start << " End: " << act[i].end <<endl;
for (int j = 1; j < n; j++){ //for all other activities
if (act[j].start >= act[i].end){ //when start time is >= end time, print the activity
cout << "Activity: " << j << " , Start: " <<act[j].start << " End: " << act[j].end <<endl; i = j;
}
}
}
int main()
{
Activitiy actArr[] = {{5,9},{1,2},{3,4},{0,6},{5,7},{8,9}};
int n = 6;
maxActivity(actArr,n);
return 0;
}
OUTPUT
[mca37@localhost mca37]$ gcc activity.cpp -

lstdc++ [mca37@localhost mca37]$ ./a.out
Selected Activities are:
Activity: 0 , Start: 1 End: 2
RESULT:
EX NO:12.2 HUFFMAN CODING IMPLEMENTATION
DATE :
AIM:
To create a Huffman Coding Algorithm using C++.
PROCEDURE
1. Calculate the frequency of each character in the string. Frequency of string
2. Sort the characters in increasing order of the frequency. These are stored in a priorityqueue
Q.Characters sorted according to the frequency
3. Make each unique character as a leaf node.
4. Create an empty node Z. Assign the minimum frequency of the left child of Z and second the
minimum frequency of the right child of Z .set the value of z as sum of the above two frequencies.
5. Remove these two minimum frequencies from Q and add the sum into the list of frequencies.
6. Insert node z into a tree.
7. Repeat steps 3 to 5 for all the characters. Repeat steps 3 to 5 for all the characters. Repeatsteps 3 to 5
for all the characters.
8. For each non-leaf node, assign 0 to the left edge and 1 to the right edge
Huffman Coding Algorithm
create a priority queue Q consisting of each unique character.sort

then in ascending order of their frequencies.
for all the unique characters:create
a newNode
extract minimum value from Q and assign it to leftChild of newNode extract
minimum value from Q and assign it to rightChild of newNode
calculate the sum of these two minimum values and assign it to the value of newNodeinsert this
newNode into the tree
return rootNode
SOURCE CODE:
#include
<iostream>
#include <vector>
#include <queue>
#include <string>
class
Huffman_Codes
{
struct New_Node
{
char data;
size_t freq;
New_Node* left;
New_Node* right;
New_Node(char data, size_t freq) : data(data),
freq(freq),
left(NULL),
right(NULL
)
{}
~New_Node()
{
delete left;
delete right;
}
};
struct compare
{
bool operator()(New_Node* l, New_Node* r)
{
return (l->freq > r->freq);
}
};
New_Node* top;
void print_Code(New_Node* root, string str)

{
if(root == NULL)
return;
if(root->data == '$')
{
print_Code(root->left, str + "0");
print_Code(root->right, str + "1");
}
if(root->data != '$')
{
cout << root->data <<" : " << str << "\n";
print_Code(root->left, str + "0");
print_Code(root->right, str + "1");
}
}
public:
Huffman_Codes() {};
~Huffman_Codes()
{
delete top;
}
void Generate_Huffman_tree(vector<char>& data, vector<size_t>& freq, size_t size)
{
New_Node* left;
New_Node* right;
priority_queue<New_Node*, vector<New_Node*>, compare > minHeap;
for(size_t i = 0; i < size; ++i)
{
minHeap.push(new New_Node(data[i], freq[i]));
}
while(minHeap.size() != 1)
{
left =
minHeap.top();
minHeap.pop();
right =
minHeap.top();
minHeap.pop();
top = new New_Node('$', left->freq + right->freq);

top->left = left;
top->right = right;
minHeap.push(top);
}
print_Code(minHeap.top(), "");
}
};
int main()
{
int n, f;
char ch;
Huffman_Codes set1;
vector<char> data;
vector<size_t> freq;
cout<<"Enter the number of elements \n";
cin>>n;
cout<<"Enter the characters \n";
for (int i=0;i<n;i++)
{
cin>>ch;
data.insert(data.end(),
ch);
}
cout<<"Enter the frequencies \n";
for (int i=0;i<n;i++)
{
cin>>f;
freq.insert(freq.end(),
f);
}
size_t size = data.size();

set1.Generate_Huffman_tree(data, freq, size);
return 0;
}
OUTPUT
[mca37@localhost mca37]$ gcc huff.cpp -lstdc++

elements
7
Enter the
characters a e i o u
st
RESULT:

DATASTRUCTURE LABmanual

Uploaded by

Copyright:

Available Formats

DATASTRUCTURE LABmanual

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DATASTRUCTURE LABmanual

Uploaded by

Copyright:

Available Formats

EX NO: 1.

To implementation of recursive function for tree traversal.

[mca11@localhost mca11]$ gcc tree.cpp -lstdc++

To implementation of recursive function for Fibonacci. Series.

Input: Read n value

[mca11@localhost mca11]$ gcc funfibo.cpp -lstdc++

[mca11@localhost mca11]$ ./a.out

Input: Read n value

STEP7: Print the values

[mca11@localhost mca11]$ gcc loopfibo.cpp -lstdc++

[mca11@localhost mca11]$ ./a.out Enter

To implementation of Merge Sort in C++.

Step1: Create copies of the L ← subarrays and M ← A[q+1..r].

[mca37@localhost mca37]$ gcc mergesort.cpp -lstdc++

Array before Sorting: 23 44 12 99 5

Array after Sorting: 5 12 23 44 99

To implement of Quick Sort in C++.

[mca11@localhost mca11]$ gcc quicksort2.cpp -lstdc++

[mca11@localhost mca11]$ ./a.out

Enter the number of data element to be sorted: 5

Sorted Data ->3->6->22->33->88

To implement a Binary Search Tree in C++.

Step 1 - Read the search element from the user.

mca37@localhost mca37]$ ./a.out

To create a binary search tree using Red-Black Tree Implementation.

A red-black tree must satisfy these properties:

/* Otherwise, recur down the tree */ if (pt-

else if (pt == pt->parent->left)

if (uncle_pt != NULL && uncle_pt->color ==

Inorder Traversal of Created

To implement Heap in C++.

1. Let the input array be Initial Array

2. Create a complete binary tree from the arrayComplete binary tree

4. Set current element i as largest

6. Otherwise rihgtchils is largest.

7. Swap largest element with current element if necessary.

8. Repeat step 3 – 7 until the subtree also heapified.

enter no of elements of array 5

To implementation Fibonacci Heap

1. Create a new node for the element.

2. Set the min-pointer to the next root in the root list.

6. Map the degree of next root to the degree in array.

#include <iostream> #include

$ g++ fibonnaciheap.cpp –lstdc++

1) Insert Element in the heap

Operations on Binomial heap

1) Insert Element in the heap

Operations on Binomial heap

1) Insert Element in the heap

Operations on Binomial heap

1) Insert Element in the heap

Operations on Binomial heap

1) Insert Element in the heap

Operations on Binomial heap

1) Insert Element in the heap

Operations on Binomial heap

1) Insert Element in the heap

Operations on Binomial heap