Write a program to implement the recursive function for tree

traversal. /* first recur on left child */

#include <iostream> printInorder(node->left);
using namespace std;
struct Node { /* then print the data of node */
int data; cout << node->data << " ";
struct Node *left, *right;
}; /* now recur on right child */
printInorder(node->right);
//Utility function to create a new tree node }
Node* newNode(int data) /* Driver program to test above functions*/
{ int main()
Node* temp = new Node; {
temp->data = data; struct Node* root = newNode(1);
temp->left = temp->right = NULL; root->left = newNode(2);
return temp; root->right = newNode(3);
} root->left->left = newNode(4);
void printPostorder(struct Node* node) root->left->right = newNode(5);
{
if (node == NULL) cout << "\nPreorder traversal of binary tree is \n";
return; printPreorder(root);

// first recur on left subtree cout << "\nInorder traversal of binary tree is \n";
printPostorder(node->left); printInorder(root);

// then recur on right subtree cout << "\nPostorder traversal of binary tree is \n";
printPostorder(node->right); printPostorder(root);

// now deal with the node return 0;

cout << node->data << " "; }
}
/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct Node* node)
{
if (node == NULL)
return;

Write a program to implement the recursive function for fibonacci. }

#include <iostream> };
using namespace std;
int fib(int x) { void preorder(Node* root)
if((x==1)||(x==0)) { {
return(x);
if (root == nullptr) {
}else {
return(fib(x-1)+fib(x-2)); return;
} }
}
int main() { cout << root->data << " ";
int x , i=0; preorder(root->left);
cout << "Enter the number of terms of series : ";
cin >> x; preorder(root->right);
cout << "\nFibonnaci Series : "; }
while(i < x) {
cout << " " << fib(i); int main()
i++; {
}
Node* root = new Node(1);
return 0;
} root->left = new Node(2);
root->right = new Node(3);
Write a program to implement for tree traversal preorder using root->left->left = new Node(4);
iteration function
#include <iostream> root->right->left = new Node(5);

using namespace std; root->right->right = new Node(6);

struct Node root->right->left->left = new Node(7);

{ root->right->left->right = new Node(8);

int data; preorder(root);

Node *left, *right; return 0;

Node(int data) }

{
this->data = data;
this->left = this->right = nullptr;
 Write a program to implement for tree traversal Inorder using int main()
iteration function {
#include <iostream> Node* root = new Node(11);
#include <stack> root->left = new Node(12);
using namespace std; root->right = new Node(13);
struct Node root->left->left = new Node(14);
{ root->right->left = new Node(15);
int data; root->right->right = new Node(16);
Node *left, *right; root->right->left->left = new Node(17);
Node(int data) root->right->left->right = new Node(18);
{ inorderIterative(root);
this->data = data; return 0;
this->left = this->right = nullptr; }
}
};
void inorderIterative(Node* root)
{
stack<Node*> stack;
Node* curr = root;
while (!stack.empty() || curr != nullptr)
{
if (curr != nullptr)
{
stack.push(curr);
curr = curr->left;
}
else {
curr = stack.top();
stack.pop();
cout << curr->data << " ";
curr = curr->right;
}
}
}

Write a program to implement for tree traversal Postorder using }

iteration function }
#include <iostream> int main()
#include <stack> { Node* root = new Node(1);
using namespace std; root->left = new Node(2);
struct Node root->right = new Node(3);
{ root->left->left = new Node(4);
int data; root->right->left = new Node(5);
Node *left, *right; root->right->right = new Node(6);
Node(int data) root->right->left->left = new Node(7);
{ root->right->left->right = new Node(8);
this->data = data; postorderIterative(root);
this->left = this->right = nullptr; return 0;
} }
};
void postorderIterative(Node* root)
{
if (root == nullptr) {
return;
}
stack<Node*> s;
s.push(root);
stack<int> out;
while (!s.empty())
{
Node* curr = s.top();
s.pop();
out.push(curr->data);
if (curr->left) {
s.push(curr->left);
}
if (curr->right) {
s.push(curr->right);
}
}
while (!out.empty())
{ cout << out.top() << " ";
out.pop();
Write a program to implement the iteration function for fibonacci. j = mid + 1;
#include <iostream> while (i <= mid && j <= high) {
using namespace std; if (arr[i] < arr[j]) {
void fib(int num) { c[k] = arr[i];
int x = 0, y = 1, z = 0; k++;
for (int i = 0; i < num; i++) { i++; }
cout << x << " "; else {
z = x + y; c[k] = arr[j];
x = y; k++;
y = z; j++; }
} } while (i <= mid) {
} c[k] = arr[i];
int main() { k++;
int num; i++; }
cout << "Enter the number : "; while (j <= high) {
cin >> num; c[k] = arr[j];
cout << "\nThe fibonacci series : " ;fib(num); k++;
return 0; j++;
} }for (i = low; i < k; i++) {
Write a program to implement Merge Sort. arr[i] = c[i];
#include <iostream> }
using namespace std; }int main()
void merge(int *,int, int , int ); {
void merge_sort(int *arr, int low, int high){ int myarray[30], num;
int mid; cout<<"Enter number of elements to be sorted:";
if (low < high){ cin>>num;
//divide the array at mid and sort independently using merge sort cout<<"Enter "<<num<<" elements to be sorted:";
mid=(low+high)/2; for (int i = 0; i < num; i++) { cin>>myarray[i];
merge_sort(arr,low,mid); }
merge_sort(arr,mid+1,high); merge_sort(myarray, 0, num-1);
//merge or conquer sorted arrays cout<<"Sorted array\n";
merge(arr,low,high,mid); for (int i = 0; i < num; i++)
}} {
void merge(int *arr, int low, int high, int mid){ cout<<myarray[i]<<"\t";
int i, j, k, c[50]; }
i = low; }
k = low;

Write a program to implement Quick Sort. }

#include<iostream> int main() {
#include<cstdlib> int n, i;
using namespace std; cout<<"\nEnter the number of data element to be sorted: ";
void swap(int *a, int *b) { cin>>n;
int temp; int arr[n];
temp = *a; for(i = 0; i < n; i++) {
*a = *b; cout<<"Enter element "<<i+1<<": ";
*b = temp; cin>>arr[i];
} }
int Partition(int a[], int l, int h) { QuickSort(arr, 0, n-1);
int pivot, index, i; cout<<"\nSorted Data ";
index = l; for (i = 0; i < n; i++)
pivot = h; cout<<"->"<<arr[i];
for(i = l; i < h; i++) { return 0;
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;
BST OPERATIONS: else if (key > root->key)
#include <iostream> root->right = deleteNode(root->right, key);
using namespace std; else {
struct node { if (root->left == NULL) {
int key; struct node *temp = root->right;
struct node *left, *right; free(root);
}; return temp;
struct node *newNode(int item) { } else if (root->right == NULL) {
struct node *temp = (struct node *)malloc(sizeof(struct node)); struct node *temp = root->left;
temp->key = item; free(root);
temp->left = temp->right = NULL; return temp;
return temp; }
} struct node *temp = minValueNode(root->right);
void inorder(struct node *root) { root->key = temp->key;
if (root != NULL) { root->right = deleteNode(root->right, temp->key);
inorder(root->left); }
cout << root->key << " -> "; return root;
inorder(root->right); }
} int main() {
} struct node *root = NULL;
struct node *insert(struct node *node, int key) { root = insert(root, 8);
if (node == NULL) return newNode(key); root = insert(root, 3);
if (key < node->key) root = insert(root, 1);
node->left = insert(node->left, key); root = insert(root, 6);
else root = insert(root, 7);
node->right = insert(node->right, key); root = insert(root, 10);
return node; root = insert(root, 14);
} root = insert(root, 4);
struct node *minValueNode(struct node *node) { cout << "Inorder traversal: ";
struct node *current = node; inorder(root);
while (current && current->left != NULL) cout << "\nAfter deleting 10\n";
current = current->left; root = deleteNode(root, 10);
return current; cout << "Inorder traversal: ";
} inorder(root);
struct node *deleteNode(struct node *root, int key) { }
if (root == NULL) return root;
if (key < root->key)
root->left = deleteNode(root->left, key);

Write a program to implement Heap. hT.pop_back();

#include <iostream> for (int i = size / 2 - 1; i >= 0; i--)
#include <vector> {
using namespace std; heapify(hT, i);
}
void swap(int *a, int *b) }
{ void printArray(vector<int>&hT)
int temp = *b; {
*b = *a; for (int i = 0; i < hT.size(); ++i)
*a = temp; cout<< hT[i] <<" ";
} cout<<"\n";
void heapify(vector<int>&hT, int i) }
{
int size = hT.size(); int main()
int largest = i; {
int l = 2 * i + 1; vector<int> heapTree;
int r = 2 * i + 2; insert(heapTree, 3);
if (l < size && hT[l] > hT[largest]) insert(heapTree, 4);
void deleteNode(vector<int>&hT, int num) insert(heapTree, 9);
{ insert(heapTree, 5);
int size = hT.size(); insert(heapTree, 2);
int i;
for (i = 0; i < size; i++) cout<<"Max-Heap array: ";
{ printArray(heapTree);
if (num == hT[i])
break; deleteNode(heapTree, 4);
}
swap(&hT[i], &hT[size - 1]); cout<<"After deleting an element: ";

printArray(heapTree);
}
Write a program
#include <cstdlib>to implement the Fibonacci Heap. void display(struct node* mini)
#include <iostream> {
#include <malloc.h> node* ptr = mini;
using namespace std; if (ptr == NULL)
struct node { cout << "The Heap is Empty" << endl;
node* parent; else {
node* child; cout << "The root nodes of Heap are: " << endl;
node* left; do {
node* right; cout << ptr->key;
int key; ptr = ptr->right;
}; if (ptr != mini) {
struct node* mini = NULL; cout << "-->";
void insertion(int val) }
{ } while (ptr != mini && ptr->right != NULL);
struct node* new_node = (struct node*)malloc(sizeof(struct node)); }
new_node->key = val; }
new_node->parent = NULL; int main()
new_node->child = NULL; {
new_node->left = new_node; insertion(8);
new_node->right = new_node; insertion(11);
insertion(6);
if (mini != NULL) {
insertion(19);
(mini->left)->right = new_node;
insertion(5);
new_node->right = mini;
insertion(15);
new_node->left = mini->left;
insertion(20);
mini->left = new_node;
display(mini);
if (new_node->key < mini->key)
return 0;
mini = new_node;
}
}
else {
mini = new_node;
}
}

Write a program to implementthe Breath First Search {

#include<iostream.h> visit[j]=1;
using namespace std; qu[rear++]=j;
int cost[10][10],i,j,k,v,n,qu[10],front,rear,visit[10],visited[10]; }
int main() v=qu[front++];
{ cout<<v<<" ";
int m; k++;
cout<<"Enter number of vertices:"; visit[v]=0;
cin>>n; visited[v]=1;
cout<<"Enter number of edges:"; }
cin>>m; }
cout<<"\nEdges\n";
for(k=1;k<=m;k++)
{
cin>>i>>j;
cost[i][j]=1;
}
cout<<"Enter initial vertex to traverse from:";
cin>>v;
cout<<"Visited vertices:";
cout<<v<<" ";
visited[v]=1;
k=1;
while(k<n)
{
for(j=1;j<=n;j++)
if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)
Write a program to implement the Spanning tree void Graph::kruskal() {
#include <algorithm> int i, uRep, vRep;
#include <iostream> sort(G.begin(), G.end()); // increasing weight
#include <vector> for (i = 0; i < G.size(); i++) {
using namespace std; uRep = find_set(G[i].second.first);
vRep = find_set(G[i].second.second);
#define edge pair<int, int> if (uRep != vRep) {
T.push_back(G[i]); // add to tree
class Graph { union_set(uRep, vRep); } }
private: }
vector<pair<int, edge>> G; // graph void Graph::print() {
vector<pair<int, edge>> T; // mst cout<<"Edge :"
int *parent; <<" Weight"<<endl;
int V; // number of vertices/nodes in graph for (int i = 0; i < T.size(); i++) {
public: cout<< T[i].second.first <<" - "<< T[i].second.second <<" : "
Graph(int V); << T[i].first;
void AddWeightedEdge(int u, int v, int w); cout<<endl; }
int find_set(int i); }
void union_set(int u, int v); int main() {
void kruskal(); Graph g(6);
void print(); g.AddWeightedEdge(0, 1, 4);
};Graph::Graph(int V) { g.AddWeightedEdge(0, 2, 4);
parent = new int[V]; g.AddWeightedEdge(1, 2, 2);
for (int i = 0; i < V; i++) g.AddWeightedEdge(1, 0, 4);
parent[i] = i; g.AddWeightedEdge(2, 0, 4);
G.clear(); g.AddWeightedEdge(2, 1, 2);
T.clear(); g.AddWeightedEdge(2, 3, 3);
}void Graph::AddWeightedEdge(int u, int v, int w) { g.AddWeightedEdge(2, 5, 2);
G.push_back(make_pair(w, edge(u, v))); g.AddWeightedEdge(2, 4, 4);
} int Graph::find_set(int i) { g.AddWeightedEdge(3, 2, 3);
// If i is the parent of itself g.AddWeightedEdge(3, 4, 3);
if (i == parent[i]) g.AddWeightedEdge(4, 2, 4);
return i; g.AddWeightedEdge(4, 3, 3);
else g.AddWeightedEdge(5, 2, 2);
return find_set(parent[i]); g.AddWeightedEdge(5, 4, 3);
} g.kruskal();
void Graph::union_set(int u, int v) { g.print();
parent[u] = parent[v]; return 0;
} }
Write a program to implement the Dijikstra Algorithm int m=minimumDist(dist,Tset);
#include<iostream> Tset[m]=true;
#include<climits> for(int i = 0; i<6; i++)
using namespace std; {
int minimumDist(int dist[], bool Tset[]) if(!Tset[i] && graph[m][i] && dist[m]!=INT_MAX && dist[m]+graph[m]
{ [i]<dist[i])
int min=INT_MAX,index; dist[i]=dist[m]+graph[m][i];
for(int i=0;i<6;i++) }
{ }
if(Tset[i]==false && dist[i]<=min) cout<<"Vertex\t\tDistance from source"<<endl;
{ for(int i = 0; i<6; i++)
min=dist[i]; {
index=i; char str=65+i;
} cout<<str<<"\t\t\t"<<dist[i]<<endl;
} }
return index; }
} int main()
void Dijkstra(int graph[6][6],int src) {
{ int graph[6][6]={
int dist[6]; {0, 10, 20, 0, 0, 0},
bool Tset[6]; {10, 0, 0, 50, 10, 0},
for(int i = 0; i<6; i++) {20, 0, 0, 20, 33, 0},
{ {0, 50, 20, 0, 20, 2},
dist[i] = INT_MAX; {0, 10, 33, 20, 0, 1},
Tset[i] = false; {0, 0, 0, 2, 1, 0}};
} Dijkstra(graph,0);
dist[src] = 0; return 0;
for(int i = 0; i<6; i++) }
{
 Write a program to implement the Bellman’s ford Algorithm Write a program to implement the Matrix chain Multiplication
#include <bits/stdc++.h> #include <bits/stdc++.h>
using namespace std; using namespace std;
void BellmanFord(int graph[][3], int V, int E, int MatrixChainOrder(int p[], int i, int j)
int src) {
{ if (i == j)
int dis[V]; return 0;
for (int i = 0; i < V; i++) int k;
dis[i] = INT_MAX; int min = INT_MAX;
dis[src] = 0; int count;
for (int i = 0; i < V - 1; i++) { for (k = i; k < j; k++)
for (int j = 0; j < E; j++) { {
if (dis[graph[j][0]] != INT_MAX && dis[graph[j][0]] + graph[j][2] < count = MatrixChainOrder(p, i, k)
dis[graph[j][1]]) + MatrixChainOrder(p, k + 1, j)
dis[graph[j][1]] = dis[graph[j][0]] + graph[j][2]; + p[i - 1] * p[k] * p[j];
}} if (count < min)
for (int i = 0; i < E; i++) { min = count;
int x = graph[i][0]; }
int y = graph[i][1];
int weight = graph[i][2];
if (dis[x] != INT_MAX &&
min = count;
dis[x] + weight < dis[y])
}
cout << "Graph contains negative"
return min;
" weight cycle"
}
<< endl;}
int main()
cout << "Vertex Distance from Source" << endl;
{
for (int i = 0; i < V; i++)
int arr[] = { 1, 2, 3, 5, 3 };
cout << i << "\t\t" << dis[i] << endl;}
int n = sizeof(arr) / sizeof(arr[0]);
int main(){
cout << "Minimum number of multiplications is "
int V = 5;
<< MatrixChainOrder(arr, 1, n - 1);
int E = 8;
}
int graph[][3] = { { 0, 1, -1 }, { 0, 2, 4 },
{ 1, 2, 3 }, { 1, 3, 2 },
{ 1, 4, 2 }, { 3, 2, 5 },
{ 3, 1, 1 }, { 4, 3, -3 } };
BellmanFord(graph, V, E, 0);
return 0;}

Write a program to implement the Huffman code

#include<iostream> void huffmanCoding(string str){
#include<queue> priority_queue<node> qu;
#include<string> int frequency[256];
using namespace std; for(int i = 0; i<256; i++)
struct node{ frequency[i] = 0; //clear all frequency
int freq; for(int i = 0; i<str.size(); i++){
char data; frequency[int(str[i])]++; //increase frequency
const node *child0, *child1; }
node(char d, int f = -1){ //assign values in the node for(int i = 0; i<256; i++){
data = d; if(frequency[i]){
freq = f; qu.push(node(i, frequency[i]));
child0 = NULL; }
child1 = NULL; }
} while(qu.size() >1){
node(const node *c0, const node *c1){ node *c0 = new node(qu.top()); //get left child and remove from queue
data = 0; qu.pop();
freq = c0->freq + c1->freq; node *c1 = new node(qu.top()); //get right child and remove from queue
child0=c0;
child1=c1;
}
bool operator<( const node &a ) const {
//< operator performs to find priority in queue qu.pop();
return freq >a.freq; qu.push(node(c0, c1));
} }
void traverse(string code = "")const{ cout << "The Huffman Code: "<<endl;
if(child0!=NULL){ qu.top().traverse();
child0->traverse(code+'0'); //add 0 with the code as left child }
child1->traverse(code+'1'); //add 1 with the code as right child main(){
}else{ string str = "ACCEBFFFFAAXXBLKE";
cout << "Data: " << data<< ", Frequency: "<<freq << ", Code: " << huffmanCoding(str);
code<<endl; }
}
}
};
4.BINARY TREE INSERTION: else
#include<iostream> q.push(temp->right);
#include<queue> }
using namespace std; }
struct node { void traversal(struct node *root) {
int data; if(root == NULL)
struct node *left, *right; return;
}; traversal(root->left);
struct node *newnode(int data) { cout << root->data << " ";
struct node *node; traversal(root->right);
node = (struct node*)malloc(sizeof(struct node)); }
node->data = data; int main() {
node->left = NULL; struct node* root = newnode(1);
node->right = NULL; root->left = newnode(10);
return node; root->left->left = newnode(20);
} root->right = newnode(34);
void insert(struct node *root, int data) { int key = 12;
struct node *temp; insert(root, key);
queue<struct node*>q; cout << endl;
q.push(root); cout << "Inorder traversal after insertion: ";
while(!q.empty()) traversal(root);
{ }
temp = q.front();
q.pop();
if(temp->left == NULL) {
temp->left = newnode(data);
break;
}
else
q.push(temp->left);
if(temp->right == NULL) {
temp->right = newnode(data);
break;
}

2.BUBBLE SORT: 1.FLOYD WARSHALL:

#include <iostream> #include <iostream>
using namespace std; using namespace std;
void bubbleSort(int array[], int size) { #define nV 4
for (int step = 0; step < size; ++step) { #define INF 999
for (int i = 0; i < size - step; ++i) { void printMatrix(int matrix[][nV]);
if (array[i] > array[i + 1]) { void floydWarshall(int graph[][nV]) {
int temp = array[i]; int matrix[nV][nV], i, j, k;
array[i] = array[i + 1]; for (i = 0; i < nV; i++)
array[i + 1] = temp; for (j = 0; j < nV; j++)
} }}} matrix[i][j] = graph[i][j];
void printArray(int array[], int size) { for (k = 0; k < nV; k++) {
for (int i = 0; i < size; ++i) { for (i = 0; i < nV; i++) {
cout << " " << array[i]; for (j = 0; j < nV; j++) {
} if (matrix[i][k] + matrix[k][j] < matrix[i][j])
cout << "\n"; matrix[i][j] = matrix[i][k] + matrix[k][j];
} }}}
int main() { printMatrix(matrix);
int data[] = {-2, 45, 0, 11, -9}; }
int size = sizeof(data) / sizeof(data[0]); void printMatrix(int matrix[][nV]) {
bubbleSort(data, size); for (int i = 0; i < nV; i++) {
cout << "Sorted Array in Ascending Order:\n"; for (int j = 0; j < nV; j++) {
printArray(data, size); if (matrix[i][j] == INF)
} printf("%4s", "INF");
else
printf("%4d", matrix[i][j]);
}
printf("\n");
}}
int main() {
int graph[nV][nV] = {{0, 3, INF, 5},
{2, 0, INF, 4},
{INF, 1, 0, INF},
{INF, INF, 2, 0}};
floydWarshall(graph);
}