Notes

EXPERIMENT 8

AIM: Program to illustrate the implementation of different operations on binary search tree.

ALGORITHM:
Insert(node, key)
i) If root == NULL, return the new node to the calling function.
ii) if root=>data < key call the insert function with root=>right and assign the return value in root=>right.
root->right = insert(root=>right,key)
iii) if root=>data > key call the insert function with root->left and assign the return value in root=>left.
root=>left = insert(root=>left,key)
PROGRAM:
# include <iostream> # include <cstdlib> using namespace std;
struct node
{ int info; struct node *left; struct node *right;
}*root; class BST
{ public: void find(int, node **, node **); void insert(node *, node *); void del(int);
void case_a(node *,node *); void case_b(node *,node *); void case_c(node *,node *); void display(node *, int);
BST()
{ root = NULL;
} }; int main()
{ int choice, num; BST bst; node *temp; while (1)

{
cout<<" ------------------- "<<endl; cout<<" Operations on BST"<<endl; cout<<" ------------------- "<<endl; cout<<"1.Insert Element "<<endl; cout<<"2.Delete Element "<<endl; cout<<"3.Display"<<endl; cout<<"4.Quit"<<endl; cout<<"Enter your choice : "; cin>>choice; switch(choice) { case 1:
temp = new node;
cout<<"Enter the number to be inserted : ";
cin>>temp->info; bst.insert(root, temp);
case 2: if (root == NULL)
{ cout<<"Tree is empty, nothing to delete"<<endl; continue; }
cout<<"Enter the number to be deleted : ";
cin>>num; bst.del(num); break;
case 3:
cout<<"Display BST:"<<endl; bst.display(root,1); cout<<endl; break;
case 4:
exit(1);
default:
cout<<"Wrong choice"<<endl;
}
} }
void BST::find(int item, node **par, node **loc)
{ node *ptr, *ptrsave; if (root == NULL)
{
*loc = NULL; *par = NULL; return; }
if (item == root->info)
{
*loc = root; *par = NULL;
return;
if (item < root->info)
ptr = root->left;
else
ptr = root->right;
ptrsave = root; while (ptr != NULL)
{ if (item == ptr->info)
{
*loc = ptr; *par = ptrsave; return; } ptrsave = ptr; if (item < ptr->info)
ptr = ptr->left;
else
ptr = ptr->right;
}
*loc = NULL;
*par = ptrsave; }
void BST::insert(node *tree, node *newnode)
{ if (root == NULL)
{ root = new node; root->info = newnode->info; root->left = NULL; root->right = NULL;
cout<<"Root Node is Added"<<endl; return; }
if (tree->info == newnode->info)
{ cout<<"Element already in the tree"<<endl;
return; }
if (tree->info > newnode->info)
{ if (tree->left != NULL)
{ insert(tree->left, newnode);
} else
{ tree->left = newnode; (tree->left)->left = NULL; (tree->left)->right = NULL;
cout<<"Node Added To Left"<<endl; return;
}

else
{ if (tree->right != NULL)
{ insert(tree->right, newnode);
} else
{ tree->right = newnode; (tree->right)->left = NULL; (tree->right)->right = NULL; cout<<"Node Added To Right"<<endl; return;
}
} }
void BST::del(int item)
{ node *parent, *location; if (root == NULL)
{ cout<<"Tree empty"<<endl; return; } find(item, &parent, &location); if (location == NULL)
{ cout<<"Item not present in tree"<<endl;
return; }
if (location->left == NULL && location->right == NULL) case_a(parent, location);
if (location->left != NULL && location->right == NULL) case_b(parent, location);
if (location->left == NULL && location->right != NULL) case_b(parent, location);
if (location->left != NULL && location->right != NULL)
case_c(parent, location);
free(location); }
void BST::case_a(node *par, node *loc )
{ if (par == NULL)
{ root = NULL; } else
{ if (loc == par->left)
par->left = NULL;
else
par->right = NULL;
}
void BST::case_b(node *par, node *loc)
{ node *child; if (loc->left != NULL)
child = loc->left;
else
child = loc->right;
if (par == NULL)
{ root = child; } else
{ if (loc == par->left) par->left = child;
else
par->right = child;
} }
void BST::case_c(node *par, node *loc)
{ node *ptr, *ptrsave, *suc, *parsuc; ptrsave = loc; ptr = loc->right; while (ptr->left != NULL)
{ ptrsave = ptr; ptr = ptr->left; } suc = ptr; parsuc = ptrsave; if (suc->left == NULL && suc->right == NULL)
case_a(parsuc, suc);
else
case_b(parsuc, suc);
if (par == NULL)
{ root = suc; } else
{ if (loc == par->left)
par->left = suc;
else
par->right = suc;
} suc->left = loc->left; suc->right = loc->right;
}
void BST::display(node *ptr, int level)
{
int i;
if (ptr != NULL)
{ display(ptr->right, level+1);
cout<<endl;
if (ptr == root)
cout<<"Root->: ";
else
{ for (i = 0;i < level;i++) cout<<" ";
} cout<<ptr->info; display(ptr->left, level+1);
} }
OUTPUT:


EXPERIMENT 9

AIM: Program to sort an array of integers in ascending order using a) Quick Sort
b) Heap Sort.
ALGORITHM:
Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left Step 7 − if both step 5 and step 6 does not match swap left and right Step 8 − if left ≥ right, the point where they met is new pivot
PROGRAM:

a) Quick Sort

#include <iostream> using namespace std; void quick_sort(int[],int,int); int partition(int[],int,int);
int main() { int a[50],n,i;
cout<<"How many elements want to be entered :"; cin>>n;
cout<<"nEnter array elements:"; for(i=0;i<n;i++) cin>>a[i]; quick_sort(a,0,n-1); cout<<"nArray after sorting:"; for(i=0;i<n;i++)
cout<<a[i]<<" "; return 0; } void quick_sort
(int a[],int l,int u) { int j;
if(l<u)
{ j=partition(a,l,u); quick_sort(a,l,j-1); quick_sort(a,j+1,u);
}
} int partition(int a[],int l,int u) {
int v,i,j,temp; v=a[l]; i=l;
j=u+1; do
{ do
i++;
while(a[i]<v&&i<=u); do
j--;
while(v<a[j]);
if(i<j) {
temp=a[i];
a[i]=a[j];
a[j]=temp; }
} while(i<j); a[l]=a[j]; a[j]=v; return(j);
}

OUTPUT:


b) Heap Sort

Algorithm :

1. Call the buildMaxHeap() function on the list. Also referred to as heapify(), this builds a heap from a list in O(n) operations.
2. Swap the first element of the list with the final element. Decrease the considered range of the list by one.
3. Call the siftDown() function on the list to sift the new first element to its appropriate index in the heap. 4. Go to step (2) unless the considered range of the list is one element.

#include <iostream>
#include<conio.h>
#include<stdlib.h>

#define MAX_SIZE 5 using namespace std; void heap_sort(); void heap_adjust(int, int); int arr_sort[MAX_SIZE], t, a;
int main()
{
int i;
cout << "Simple C++ Heap Sort Example - Functions and Arrayn";
cout << "nEnter " << MAX_SIZE << " Elements for Sorting : " << endl; for (i = 0; i < MAX_SIZE; i++) cin >> arr_sort[i];
cout << "nYour Data :"; for (i = 0; i < MAX_SIZE; i++) { cout << "t" << arr_sort[i];
} heap_sort();
cout << "nnSorted Data :";
for (i = 0; i < MAX_SIZE; i++) { cout << "t" << arr_sort[i];
} getch(); }
void heap_sort() { for (int i = MAX_SIZE / 2 - 1; i >= 0; i--) heap_adjust(MAX_SIZE, i);
for (int i = MAX_SIZE - 1; i >= 0; i--) { t = arr_sort[0]; arr_sort[0] = arr_sort[i]; arr_sort[i] = t; heap_adjust(i, 0);
cout << "nHeap Sort Iteration : " << i; for (a = 0; a < MAX_SIZE; a++) { cout << "t" << arr_sort[a];
}
} } void heap_adjust(int n, int i) {
int large = i, left = 2 * i + 1, right = 2 * i + 2; if (left < n && arr_sort[left] > arr_sort[large]) large = left;
if (right < n && arr_sort[right] > arr_sort[large])
large = right;
if (large != i) {
t = arr_sort[i];


arr_sort[i] = arr_sort[large]; arr_sort[large] = t; heap_adjust(n, large);
}
}

OUTPUT :


EXPERIMENT 10

AIM: Program to illustrate the traversal of graph using
a) breadth-first search. b) depth-first search
a) BFS
ALGORITHM:
Step 1: SET STATUS = 1 (ready state) for each node in G
Step 2: Enqueue the starting node A and set its STATUS = 2
(waiting state)
Step 3: Repeat Steps 4 and 5 until
QUEUE is empty
Step 4: Dequeue a node N. Process it and set its STATUS = 3 (processed state).
Step 5: Enqueue all the neighbours of
N that are in the ready state (whose STATUS = 1) and set
their STATUS = 2
(waiting state)
[END OF LOOP]
Step 6: EXIT

PROGRAM:
#include<iostream> using namespace std; int main()
{ static int adj[10][10]; int n,edges,src_vert,dest_vert,i,j,q; int start,status[10],queue[15],f,r,w,k=0,bfs[10]; cout<<"Enter number of vertices and edges in graph :n "; cin>>n>>edges; cout<<"Input source and destination vertices of edges :n"; for(i=1;i<=edges;i++)
{ cin>>src_vert>>dest_vert; adj[src_vert][dest_vert]=1;
} cout<<"Adjacency matrix nn"; for(i=1;i<=n;i++)
{ for(j=1;j<=n;j++) cout<<adj[i][j]<<" "; cout<<endl; } cout<<endl;
cout<<"Enter the starting vertex :";
cin>>start; for(i=1;i<=n;i++) status[i]=0; f=r=-1; f=r=0; queue[f]=start; status[start]=1; while(f!=-1)
{ w=queue[f];
if(f==r) f=r=-1; else
f++;
status[w]=2; bfs[k]=w; k++;
for(j=1;j<=n;j++)
{ if(adj[w][j]!=0 && status[j]==0)
{ queue[++r]=j; if(r==0)
f=0; status[j]=1;

}
} }
cout<<"BFS traversal of given graph :n";
for(q=0;q<k;q++)
{ cout<<bfs[q]<<"t";
} return 0;
}

OUTPUT:

b) DFS Algorithm
Step 1: SET STATUS = 1 (ready state) for each node in G
Step 2: Push the starting node A on the stack and set its STATUS = 2 (waiting state)
Step 3: Repeat Steps 4 and 5 until STACK is empty
Step 4: Pop the top node N. Process it and set its STATUS = 3 (processed state)
Step 5: Push on the stack all the neighbours of N that are in the ready state (whose
STATUS = 1) and set their
STATUS = 2 (waiting state)
[END OF LOOP]
Step 6: EXIT Program :
#include<iostream> using namespace std;
int main()
{ static int adj[10][10]; int n,edges,src_vert,dest_vert; int start,status[10],stack[10]; int top=-1;
int i,j;
int w,k=0,dfs[10];
cout<<"Enter number of vertices and edges in graph :n "; cin>>n>>edges; cout<<"Input source and destination vertices of edges :n"; for(i=1;i<=edges;i++)
{ cin>>src_vert>>dest_vert; adj[src_vert][dest_vert]=1;
}
cout<<"Adjacency matrix nn"; for(i=1;i<=n;i++)
{ for(j=1;j<=n;j++) cout<<adj[i][j]<<" ";
cout<<endl;
} cout<<endl;

cout<<"Enter the starting vertex :"; cin>>start; for(i=1;i<=n;i++)
status[i]=0; stack[++top]=start; status[start]=1; while(top!=-1)
{ w=stack[top]; top=top-1; status[w]=2; dfs[k]=w; k++; for(j=1;j<=n;j++)
{ if(adj[w][j]!=0 && status[j]==0)
{ stack[++top]=j; status[j]=1;
}
} }
cout<<"DFS traversal of given graph :n"; for(i=0;i<k;i++)
{ cout<<dfs[i]<<"t";
} return 0;
}

OUTPUT: