C++ program to implement searching & Sorting on Item record using STL.

Code :
#include<iostream.h>
#include<conio.h>
#include<algorithm>
#include<vector>
using namespace std;
class Item
{
public: char name[10];
int quantity;
int cost;
int code;
bool operator==(const Item &i1)
{
if(code==i1.code)
return 1;
return 0;
}

bool operator<(Item &i1)
{
if(code<i1.code)
return 1;
return 0;
}
};
vector<Item> o1;
void print(Item &i1);
void display();
void insert();
void search();
void dlt();
void main()
{
int ch;
do
{
cout<<”\n***** Menu *****”;
cout<<”\n1.Insert”;
cout<<”\n2.Display”;
cout<<”\n3.Search”;
cout<<”\n4.Sort”;
cout<<”\n5.Delete”;
cout<<”\n6.Exit”;
cout<<”\nEnter your choice:”;
cin>>ch;
switch(ch)
{
case 1: insert();
break;
case 2: display();
break;
case 3: search();
break;
case 4: sort(o1.begin(),o1.end());
break;
case 5: dlt();
break;
case 6: exit(0);
}
}while(ch!=7);
}
void insert()
{
Item i1;
cout<<”\nEnter Item Name:”;
cin>>i1.name;
cout<<”\nEnter Item Quantity:”;
cin>>i1.quantity;
cout<<”\nEnter Item Cost:”;
cin>>i1.cost;
cout<<”\nEnter Item Code:”;
cin>>i1.code;
o1.push_back(i1);
}
void display()
{
for_each(o1.begin(),o1.end(),print);
}
void print(Item &i1)
{
cout<<”\n”;
cout<<”\nItem Name:”<<i1.name;
cout<<”\nItem Quantity:”<<i1.quantity;
cout<<”\nItem Cost:”<<i1.cost;
cout<<”\nItem Code:”<<i1.code;
}
void search()
{
vector<Item>::iterator p;
Item i1;
cout<<”\nEnter Item Code to search:”;
cin>>i1.code;
p=find(o1.begin(),o1.end(),i1);
if(p==o1.end())
cout<<”\nNot found.”;
else
{
cout<<”\nFound.”;
}
}
void dlt()
{
vector<Item>::iterator p;
Item i1;
cout<<”\nEnter Item Code to delete:”;
cin>>i1.code;
p=find(o1.begin(),o1.end(),i1);
if(p==o1.end())
cout<<”\nNot found.”;
else
{
o1.erase(p);
cout<<”\nDeleted.”;
} }

Program to implement dequeue using C++

Description :
Deque stands for Double-ended queue.These are sequence containers with dynamic sizes that can be expanded or contracted on both ends.
Code:
#include<deque>     //include deque library
#include<stdio.h>
#include<iostream.h>
using namespace std;
void main()
{
deque <int>dq;
deque <int>::iterator p;
char cc;
int val,ch;
do
{
cout<<”\n\nMENU:”;
cout<<”\n1. Enter element at front\n2. Enter element at Rear\n3. Delet element at front\n4. Delet element at Rear\n5. Disp front element\n6. Disp back element\n7. Display the element of Deque\n\n”;
cout<<”\nEnter choice:”;
cin>>ch;
switch(ch)
{
case 1:
cout<<”\n\nEnter the element to be inserted:”;
cin>>val;
dq.push_front(val);
cout<<”\nElement inserted at front:”<<dq.front();
break;
case 2:
cout<<”\n\nEnter the element to be inserted:”;
cin>>val;
dq.push_back(val);
cout<<”\nElement inserted at rear end:”<<dq.back();
break;
case 3:
cout<<”\nElementto be deleted at front:”<<dq.front();
dq.pop_front();
break;
case 4:
cout<<”\nElement to be deleted at rear:”<<dq.back();
dq.pop_back();
break;
case 5:
cout<<”\nElement at front:”<<dq.front();
break;
case 6:
cout<<”\nElement at rear:”<<dq.back();
break;

case 7:
if(dq.empty()==1)
cout<<”\n\nDEQUE is EMPTY..”;
else
{
cout<<”\n\nDisplaying the elements of DEQUE…\n”;
for(p=dq.begin();p<dq.end();p++)
cout<<” “<<*p<<”\t”;
}
break;
}
cout<<”\n\nCONTINUE MENU:”;
cin>>cc;
}while(cc==’y'); }

C++ code to add binary numbers using STL stack

Description:
Using STL ,the stack header file needs to be included to use this class. The class member functions that are provided are listed below.

• push, pushes an item onto the stack.
• pop, pops an item from the stack but does not give this item to the programmer to use.
• top, gives the programmer a reference to the top of stack item; no change is made to the stack.
• empty, the usual boolean function.
• size, reports the number of items on the stack.

Code:
#include<iostream.h>
#include<vector>
#include<stack>
using namespace std;
stack <int> read();
void display(stack<int> &s);
stack <int>add(stack<int> &s1,stack<int> &s2);
void main()
{
stack<int> s1,s2,s3;
int ch;
do
{
cout<<”\n1.Addition of two binary numbers\n2.Quit”;
cout<<”\nEnter your choice:”;
cin>>ch;
switch(ch)
{
case 1: s1=read();
s2=read();
s3=add(s1,s2);
display(s3);
break;
}
}while(ch!=2);
}
stack<int> read()
{
char a[40];
stack<int> s;
cout<<”\n Enter a binary number: “;
cin>>a;
for(int i=0;a[i]!=’\0′;i++)
{
if(a[i]==’1′)
s.push(1);
else
if(a[i]==’0′)
s.push(0);
}
return s;
}
stack<int> add(stack<int> &s1,stack<int> &s2)
{
stack<int> s;
int sum,carry=0,bit1,bit2;
while(!s1.empty() || !s2.empty())
{
bit1=bit2=0;
if(!s1.empty())
{
bit1=s1.top();
s1.pop();
}
if(!s2.empty())
{
bit2=s2.top();
s2.pop();
}
sum=(bit1+bit2+carry)%2;
carry=(bit1+bit2+carry)/2;
s.push(sum);
}
if(carry==1)
s.push(1);
return s;
}
void display(stack<int> &s)
{
cout<<”\n Sum= “;
while(!s.empty())
{
cout<<s.top();
s.pop();
} }

Program to Implement queue using SLL

Code:
#include<iostream.h>
#include<conio.h>
#include<deque>
using namespace std;

void main()
{
int ch,val;
deque<int> dq;
deque<int>::iterator p;
cout<<”\n1.Inserting at front position\n2.Inserting at rear position”;
cout<<”\n3.Deleting front element\n4.Deleting rear element”;
cout<<”\n5.Display front element\n6.Display rear element\n7.Display whole deque”;
do
{
cout<<”\nEnter your choice:”;
cin>>ch;
switch(ch)
{
case 1:cout<<”\nEnter data:”;
cin>>val;
dq.push_front(val);
break;
case 2:cout<<”\nEnter data:”;
cin>>val;
dq.push_back(val);
break;
case 3:dq.pop_front();
break;
case 4:dq.pop_back();
break;
case 5:cout<<”\nFront:”;
cout<<dq.front();
break;
case 6:cout<<”\nRear:”;
cout<<dq.back();
break;
case 7: if(dq.empty())
cout<<”\nQueue is empty!”;
else
{
for(p=dq.begin();p<dq.end();p++)
cout<<” “<<*p;
}
break;
}
}while(ch!=8);
}

C++ code to Implement direct access file using different collision resolution techniques.

Code :
/* To implement Direct Access File ,Collision handling throgh linear probing with chaining and without replacement.
*/
#include <iomanip.h>
#include <iostream.h>
#include <fstream.h>
#include <conio.h>
#include <string.h>
#define SIZE 10
#define h(x) x%SIZE
struct student
{
int rollno;
char name[20];
float marks;
int status;
int link;
};
class lin_probe
{
char table[30];
fstream tab;
student rec;
public:
lin_probe(char *a);

void displayall();
void insert(student rec1);
void Delete(int rollno);
int search(int rollno);
void display(int recno)
{
int i=recno;
tab.open(table,ios::binary | ios::in | ios::nocreate);
tab.seekg(recno*sizeof(student),ios::beg);
tab.read((char*)&rec,sizeof(student));
if(rec.status==0)
{
cout<<”\n”<<i<<”) “<<rec.rollno<<” “<<rec.name<<” “<<setprecision(2)<<rec.marks;
cout<<” “<<rec.link;
}
else
cout<<”\n”<<i<<”) ***** Empty ********”;
tab.close();
}
void read(int recno)
{
tab.open(table,ios::binary | ios::in );
tab.seekg(recno*sizeof(student),ios::beg);
tab.read((char*) &rec,sizeof(student));
tab.close();
}
void write(int recno)
{
tab.open(table,ios::binary | ios::nocreate | ios::out | ios::in);
tab.seekp(recno*sizeof(student),ios::beg);
tab.write((char*)&rec,sizeof(student));
tab.close();
}
};
void lin_probe::lin_probe(char *a)
{
int i;
strcpy(table,a);
rec.status=1;rec.link=-1;
tab.open(table,ios::binary | ios::out);
tab.close();
for(i=0;i<SIZE;i++)
write(i);
}
void lin_probe::displayall()
{
int i=1,n;
cout<<”\n*********Data File*********\n”;
for(i=0;i<SIZE;i++)
display(i);
}
void lin_probe::insert(student rec1)
{
int n,i,j,start,k;
rec1.status=0;
rec1.link=-1;
start=h(rec1.rollno);
for(i=0;i<SIZE;i++)
{
j=(start+i)%SIZE;
read(j);
if(rec.status==0 && h(rec.rollno)==start)
break;
}
if(i<10)
{
while(rec.link!=-1)
{
j=rec.link;
read(j);
}
for(i=0;i<SIZE;i++)
{
k=(start+i)%SIZE;
read(k);
if(rec.status==1)
{
rec=rec1;
write(k);
read(j);
rec.link=k;
write(j);
return;
}
}
cout<<”\nTable is full “;
}
else
{
for(i=0;i<SIZE;i++)
{
k=(start+i)%SIZE;
read(k);
if(rec.status==1)
{
rec=rec1;
write(k);
return;
}
}
cout<<”\nTable is full “;
}
}
void lin_probe::Delete(int rollno)
{
student rec1;
int recno;
int i,j,start,k;
start=h(rollno);
for(i=0;i<SIZE;i++)
{
j=(start+i)%SIZE;
read(j);
if(rec.status==0 && h(rec.rollno)==start)//synonim found
break;
}
if(i<10)
{
if(rec.rollno==rollno )
{
rec.status=1;
write(j);
}
else
{
while(rec.rollno !=rollno && rec.link!=-1)
{
k=j;
j=rec.link;
read(j);
}
if(rec.rollno==rollno)
{ rec.status=1;
write(j);
int nextlink=rec.link;
read(k);
rec.link=nextlink;
write(k);
}
else
cout<<”\nElement not found”;
}
}
else
cout<<”\nRecord Not Found “;
}
int lin_probe::search(int rollno)
{
int start,i,j;
start=h(rollno);
for(i=0;i<SIZE;i++)
{
j=(start+i)%SIZE;
read(j);
if(rec.status==0 && h(rec.rollno)==start)//synonim found
break;
}
if(i<10)
{
while(rec.rollno !=rollno && rec.link!=-1)
{
j=rec.link;
read(j);
}
if(rec.rollno==rollno)
return(j);
else
return -1;
}
else
return -1;
}
void main()
{
lin_probe object(“table.txt”);
int rollno,op,recno;
student rec1;
clrscr();
do
{
cout<<”\n\n1)Print\n2)Insert\n3)Delete”;
cout<<”\n4)Search\n5)Quit”;
cout<<”\nEnter Your Choice:”;
cin>>op;
switch(op)
{
case 1: object.displayall();
break;
case 2:
cout<<”\nEnter a record to be inserted(roll no,name,marks) : “;
cin>>rec1.rollno>>rec1.name>>rec1.marks;
object.insert(rec1);
break;
case 3:
cout<<”\nEnter the roll no.:”;
cin>>rollno;
object.Delete(rollno);
break;
case 4:
cout<<”\nEnter a roll no. : “;
cin>>rollno;
recno=object.search(rollno);
if(recno>=0)
{
cout<<”\n Record No.: “<<recno;
object.display(recno);
}
else
cout<<”\nRecord Not Found “;
break;
}
}while(op!=5); }

Program for Implementation of AVL tree in C++

Description :
AVL is named so by   its two inventors,.Adelson-Velskii  and Landis.
In AVL tree,the height of the two child subtrees of any node differ by at most one. If at any time they differ by more than one, rebalancing is done to restore this property.

Code  :
#include<iostream.h>
#include<conio.h>
#include<alloc.h>
# include<stdlib.h>
class node
{
public:
int data;
struct node *left,*right;
int ht;
};

class AVL
{
node *root;
int height(node *);
node *rotate_right(node *);
node *rotate_left(node *);
node *RR(node *);
node *LL(node *);
node *LR(node *);
node *RL(node *);
int BF(node *);
public:
AVL()
{
root=NULL;
}
node *insert(node *,int);
node *delet(node *,int);
void preorder (node *);
void inorder(node *);
};
void main()
{
AVL A;
int x,n,i,choice;
node *root=NULL;
clrscr();
cout<<”\n\n\t\t\t\t\t\t\t\t\t\t\t\t…. CREATION OF AVL TREE ….”;
do
{
cout<<”\n\n MENU: “;
cout<<”\n\n\t1.Create\n\n\t2.Insert\n\n\t3.Delete\n\n\t4.Display\n\n\t5.Exit “;
cout<<”\n\nEnter the choice: “;
cin>>choice;
switch(choice)
{
case 1:
cout<<”\n\nEnter the number of elements: “;
cin>>n;
cout<<”\n\nEnter tree data: “;
for(i=0;i<n;i++)
{
cin>>x;
root=A.insert(root,x);
}
break;
case 2:
cout<<”\n\nEnter the data to be insert: “;
cin>>x;
A.insert(root,x);
break;
case 3:
cout<<”\n\nEnter a data which u have to delete: “;
cin>>x;
A.delet(root,x);
break;
case 4:
cout<<”\n\nPreorder Display:\n\n”;
A.preorder(root);
cout<<”\n\nInorder Display:\n\n”;
A.inorder(root);
break;
}
}while(choice!=5);
getch();
}
node *AVL::insert(node *T,int x)
{
if(T==NULL)
{
T=new node;
T->data=x;
T->left=NULL;
T->right=NULL;
}
else
{
if(x>T->data)
{
T->right=insert(T->right,x);
if(BF(T)==-2)
{
if(x>T->right->data)
T=RR(T);
else
T=RL(T);
}
}
else if(x<T->data)
{
T->left=insert(T->left,x);
if(BF(T)==2)
{
if(x<T->left->data)
T=LL(T);
else
T=LR(T);
}
}
}
T->ht=height(T);
return(T);
}
node *AVL::delet(node *T,int x)
{
node *p;
if(T==NULL)
return(0);
else
if(x>T->data)
{
T->right=delet(T->right,x);
if(BF(T)==2)
if(BF(T->left)>=0)
T=LL(T);
else
T=LR(T);
}
else if(x<T->data)
{
T->left=delet(T->left,x);
if(BF(T)==-2)
if(BF(T->right)<=0)
T=RR(T);
else
T=RL(T);
}
else
{
if(T->right!=NULL)
{
p=T->right;
while(p->left!=NULL)
p=p->left;
T->data=p->data;
T->right=delet(T->right,p->data);
if(BF(T)==2)
if(BF(T->left)>=0)
T=LL(T);
else
T=LR(T);
}
else
return(T->left);
}
T->ht=height(T);
return(T);
}
int AVL::height(node *T)
{
int LH,RH;
if(T==NULL)
return(0);
if(T->left==NULL)
LH=0;
else
LH=1+T->left->ht;
if(T->right==NULL)
RH=0;
else
RH=1+T->right->ht;
if(LH>RH)
return (LH);
else
return (RH);
}
int AVL::BF(node *T)
{
int LH,RH;
if(T==NULL)
return(0);
if(T->left==NULL)
LH=0;
else
LH=1+T->left->ht;
if(T->right==NULL)
RH=0;
else
RH=1+T->right->ht;
return(LH-RH);
}
node *AVL::rotate_left(node *x)
{
node *y;
y=x->right;
x->right=y->left;
y->left=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}
node *AVL::rotate_right(node *x)
{
node *y;
y=x->left;
x->left=y->right;
y->right=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}
node *AVL::LL(node *T)
{
T=rotate_right(T);
return(T);
}
node *AVL::RR(node *T)
{
T=rotate_left(T);
return(T);
}
node *AVL::LR(node *T)
{
T->left=rotate_left(T->left);
T=rotate_right(T);
return(T);
}
node *AVL::RL(node *T)
{
T->right=rotate_right(T->right);
T=rotate_left(T);
return(T);
}
void AVL::preorder(node *root)
{
node *T=root;
if(T!=NULL)
{
cout<<” \n”<<T->data<<” [BF= "<<BF(T)<<"]“;
preorder(T->left);
preorder(T->right);
}
}
void AVL::inorder(node *root)
{
node *T=root;
if(T!=NULL)
{
inorder(T->left);
cout<<” \n”<<T->data<<” [BF= "<<BF(T)<<"]“;
inorder(T->right);
} }

Program to implement B tree in c++

Code :
#include<iostream.h>
#include<conio.h>
#define MAX 5
class node;
typedef struct pair
{
int key;
node *next;
}pair;
class node
{
public:
node *father;
int noofkeys;
pair data[MAX];
node *first;
node();
void insert_in_node(pair x);
pair splitnode(pair x);
int leaf_node();
node *nextindex(int x);
void display();
};
void node::display()
{
int i;
cout<<”(“;
for(i=0;i<noofkeys;i++)
cout<<data[i].key<<” “;
cout<<”)”;
}
node* node::nextindex(int x)
{
if(x<data[0].key)
return first;
for(int i=0;i<noofkeys;i++)
{
if(x<=data[i].key)
return (data[i-1].next);
}
return (data[i-1].next);
}
int node::leaf_node()
{
if(data[0].next==NULL)
return 1;
return 0;
}
void node::insert_in_node(pair mypair)
{
int i;
for(i=noofkeys-1;i>=0 && data[i].key>mypair.key;i–)
data[i+1]=data[i];
data[i+1]=mypair;
noofkeys++;
}
pair node::splitnode(pair x)
{
node *T;
pair mypair;
int i,j,centre;
centre=(noofkeys-1)/2;
T=new node;
if(x.key>data[centre].key) //Divide the node in two parts(original and T)
{
for(i=centre+1,j=0;i<=noofkeys;i++,j++)
T->data[j]=data[i];
T->noofkeys=noofkeys-centre-1;
noofkeys=noofkeys-T->noofkeys;
T->insert_in_node(x);
T->first=T->data[0].next;
T->father=father;
mypair.key=T->data[0].key;
mypair.next=T;
//Delete the first key from node T
for(i=1;i<T->noofkeys;i++)
T->data[i-1]=T->data[i];
T->noofkeys–;
}
else
{
for(i=centre,j=0;i<noofkeys;i++,j++)
T->data[j]=data[i];
T->noofkeys=noofkeys-centre;
noofkeys=noofkeys-T->noofkeys;
insert_in_node(x);
T->father=father;
mypair.key=T->data[0].key;
mypair.next=T;
//Delete the first key from node T
for(i=1;i<T->noofkeys;i++)
T->data[i-1]=T->data[i];
T->noofkeys–;
}
return(mypair);
}
node::node()
{
for(int i=0;i<=MAX;i++)
data[i].next=NULL;
noofkeys=0;
father=NULL;
first=NULL;
}
class btree
{
int mkeys;
node *root;
public:
btree(int n)
{
mkeys=n;
root=NULL;
}
void insert(int x);
void displaytree();
};

void btree::insert(int x)
{
int index;
pair mypair;
node *p,*q;
mypair.key=x;
mypair.next=NULL;
if(root==NULL)
{
root = new node;
root->insert_in_node(mypair);
}
else
{
p=root;
while(!(p->leaf_node()))
p=p->nextindex(x);
if(p->noofkeys < mkeys-1)
p->insert_in_node(mypair);
else
{
mypair=p->splitnode(mypair);
while(1)
{
if(p==root)
{
q=new node;
q->data[0]=mypair;
q->first=root;
q->father=NULL;
q->noofkeys=1;
root=q;
q->first->father=q;
q->data[0].next->father=q;
return;
}
else
{
p=p->father;
if(p->noofkeys < mkeys)
{
p->insert_in_node(mypair);
return;
}
else
mypair=p->splitnode(mypair);
}
}
}
}
}
class Q
{
node *data[60];
int R,F;
public:
Q()
{
R=F=0;
}
int empty()
{
if(R==F)
return 1;
else
return 0;
}
node *deque()
{
return data[F++];
}
void enque(node *x)
{
data[R++]=x;
}
void makeempty()
{
R=F=0;
}
};
void btree::displaytree()
{
Q q1,q2;
node *p;
q1.enque(root);
while(!q1.empty())
{
q2.makeempty();
cout<<”\n”;
while(!q1.empty())
{
p=q1.deque();
p->display();cout<<” “;
if(!p->leaf_node())
{
q2.enque(p->first);
for(int i=0;i<p->noofkeys;i++)
q2.enque(p->data[i].next);
}
}
q1=q2;
}
}
void main()
{
int n,i,x,op;
node *p;
clrscr();
cout<<”\nmaximum number of keys in a node ? :”;
cin>>n;
btree b(n);
do
{
cout<<”\n\n1)Insert\n2)Print\n3)Quit”;
cout<<”\nEnter your choice : “;
cin>>op;
switch(op)
{
case 1: cout<<”\nEnter a data : “;
cin >> x;
b.insert(x);
break;
case 2:
b.displaytree();
break;
}
}while(op!=3); }

C++ code to generate minimum spanning tree using Prim’s algorithm.

Description :
It works as follows:

1. Create a tree containing a single vertex that is  chosen arbitrarily from the graph.
2. Create a set containing all the edges in the graph.Loop until every edge in the set connects two vertices in the tree.
3. Remove from the set an edge with minimum weight that connects a vertex in the tree with a vertex not in the tree.
4.  Add that edge to the tree.

Code :
#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include<process.h>
#include<stdlib.h>
class prims
{
private:
int a[10][10],spantree[10][10],n;
int visit[20],from[20],dist[20];
public:
void dir();
void span();
}c;
void prims::dir()
{
int v1,v2,i,j,w;
char ch;
cout<<”\n\nEnter Number of nodes: “;
cin>>n;
do
{
cout<<”\n\nEnter the Source vertex: “;
cin>>v1;
cout<<”\nEnter The Destination Vertex: ” ;
cin>>v2;
cout<<”\nEnter The Weight Of Edge: “;
cin>>w;
a[v1][v2]=w;
a[v2][v1]=w;
cout<<”\n\nDo You Want To Continue?(Y/N): ” ;
flushall();
cin>>ch;
}while(ch==’y'||ch==’Y');
getch();
}
void prims::span()
{
int u,v,y,i,ne,mindist,j,mincost;
ne=0;
mincost=0;
cout<<”\nEnter Your Starting vertex: “;
cin>>v;
visit[v]=1;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(a[i][j]==0)
a[i][j]=9999;
}
}
for(i=0;i<n;i++)
{
dist[i]=a[0][i];
}
while(ne<=n-1)
{
mindist=9999;
for(i=0;i<n;i++)
{
if((visit[i]==0)&&(dist[i]<mindist))
{
v=i;
mindist=dist[i];
}
}
u=from[v];
spantree[u][v]=dist[v];
spantree[v][u]=dist[v];
visit[v]=1;
ne++;
for(i=1;i<n;i++)
{
if((visit [i]==0)&&(a[i][v]<dist[i]))
{
dist[i]=a[i][v];
from[i]=v;
}
}
mincost+=mindist;
}
mincost=mincost-9999;
cout<<”\nMinimum Spanning Tree is:\n”;
for(i=0;i<n;i++)
{
cout<<”\n”;
for(j=0;j<n;j++)
{
cout<<”\t”<<spantree[i][j];
}
}
cout<<”\n\nMinimum cost of Spanning tree is: ” <<mincost;
getch();
}
void main()
{
int ch;
char f;
clrscr();
cout<<”\n\n\t\t\t\t\t\t\t\t\t\t\t…. Minimum Cost Spanning Tree Using Prim’s Algorithm ….”;
do
{
cout<<”\n\n MENU: “;
cout<<”\n\n\t1.Create Graph\n\n\t2.Find Minimum Cost Spanning Tree\n\n\t3.Exit”;
cout<<”\n\nEnter Your Choice: ” ;
cin>>ch;
switch(ch)
{
case 1:
c.dir();
getch();
break;
case 2:
c.span();
break;
case 3:
exit(0);
break;
default:
cout<<”\n\nPlease Enter Valid choice.”;
break;
}
flushall();
cout<<”\n\nDo You Want To Continue To main Program?(Y/N): ” ;
cin>>f;
}while(f==’Y’ || f==’y');
getch(); }

C++ code to Represent graph using adjacency list and perform DFS and BFS

Code :
#define infinity 9999
#define MAX 20
#include<conio.h>
#include<iostream.h>
#include<stdlib.h>
class Q
{
int data[30];
int R,F;
public:
Q()
{
R=F=-1;
}
void init()
{
R=F=-1;
}
int empty()
{
if(R==-1)
return 1;
return 0;
}
void insert(int x)
{
if(empty())
R=F=0;
else
R=R+1;
data[R]=x;
}
int Delete()
{
int x=data[F];
if(R==F)
R=F=-1;
else
F=F+1;
return(x);
}
};
struct node
{
node *next;
int vertex;
};
class graph
{
int visited[MAX];
node *G[20];
int n;
void insert(int vi,int vj);
void DFS1(int);
public:
graph()
{
n=0;
}
void readgraph();
void BFS(int);
void DFS(int);
};
void graph::DFS(int start)
{
for(int i=0;i<n;i++)
visited[i]=0;
DFS1(start);
}
void graph::BFS(int v)
{
int i,w;
Q q;
node *p;
for(i=0;i<n;i++)
visited[i]=0;
q.insert(v);
cout<<” “<<v;
visited[v]=1;
while(!q.empty())
{
v=q.Delete();
for(p=G[v];p!=NULL;p=p->next)
{
w=p->vertex;
if(visited[w]==0)
{
q.insert(w);
visited[w]=1;
cout<<” “<<w;
}
}
}
}
void graph::DFS1(int i)
{
node *p;
cout<<” “<<i;
p=G[i];
visited[i]=1;
while(p!=NULL)
{
i=p->vertex;
if(!visited[i])
DFS1(i);
p=p->next;
}
}
void graph::readgraph()
{
int i,vi,vj,no_of_edges;
cout<<”\n\nEnter number of vertices: “;
cin>>n;
for(i=0;i<n;i++)
G[i]=NULL;
cout<<”\n\nEnter number of edges: “;
cin>>no_of_edges;
for(i=0;i<no_of_edges;i++)
{
cout<<”\n\nEnter an edge(u,v): “;
cin>>vi>>vj;
insert(vi,vj);
insert(vj,vi);
}
}
void graph::insert(int vi,int vj)
{
node *p,*q;
q=new node ;
q->vertex=vj;
q->next=NULL;
if(G[vi]==NULL)
G[vi]=q;
else
{
p=G[vi];
while(p->next!=NULL)
p=p->next;
p->next=q;
}
}
void main()
{
int choice,start,n;
graph g1;
clrscr();
cout<<”\n\n\t\t\t\t\t\t\t\t\t\t\t\t…. BFS & DFS Of Graph …. “;
cout<<”\n\nÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ”;
do
{
cout<<”\nÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ”;
cout<<”\n\n MENU: “;
cout<<”\n\n\t1.Create a graph\n\n\t2.BFS\n\n\t3.DFS\n\n\t4.Exit”;
cout<<”\nÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ”;
cout<<”\n\nEnter Your Choice: “;
cin >>choice;
switch(choice)
{
case 1:
g1.readgraph();
break;
case 2:
cout<<”\n\nEnter starting Vertex: “;
cin>>start;
cout<<”\n\nBFS of graph is:\n\n”;
g1.BFS(start);
break;
case 3:
cout<<”\n\nEnter starting Vertex: “;
cin>>start;
cout<<”\n\nDFS of graph is:\n\n”;
g1.DFS(start);
break;
}
}while(choice!= 4);
}

C++ code to Create in-order threaded binary tree and perform traversals

Description :
A Threaded Binary Tree is a binary tree in which every node that does not have a right child has a THREAD (link) to its INORDER successor. Due to the use of this threading ,we avoid the recursive method of traversing a Tree, which makes use of stacks and consumes a lot of memory and time.

Code :
/* Create a TBT and perform traversals */
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
struct tbtnode
{
int data;
tbtnode *left,*right;
int lbit,rbit,flag;
};

class TBT
{
tbtnode *root;
tbtnode *presuc(tbtnode *t);
tbtnode *insuc(tbtnode *t);
tbtnode *postsuc(tbtnode *t);
tbtnode * father(tbtnode *t);
void TBT::create1(tbtnode *fatherof,int leftorright);
public:
TBT()
{
root=new tbtnode;
root->lbit=0;
root->rbit=1;
root->left=root->right=root;
}
void preorder();
void inorder();
void postorder();
void create();
};
void main()
{
TBT tbt;
int choice;
clrscr();
cout<<”\n\n\t\t\t\t\t\t\t\t\t\t\t\t…. THREADED BINARY TREE ….”;
cout<<”\n\nÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ”;
do
{
cout<<”\nÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ”;
cout<<”\n\n MENU: “;
cout<<”\n\n\t1.Create\n\n\t2.Preorder Traversal\n\n\t3.Inorder Traversal\n\n\t4.Postorder Traversal\n\n\t5.Exit”;
cout<<”\nÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ”;
cout<<”\n\nEnter your choice: “;
cin>>choice;
switch(choice)
{
case 1: tbt.create();break;
case 2: tbt.preorder();break;
case 3: tbt.inorder();break;
case 4: tbt.postorder();break;
}
}while(choice!=5);
getch();
}
void TBT::create1(tbtnode *fatherof,int leftorright)//leftorright=0 for left child
{
tbtnode *p;
int x;
cout<<”\n\nEnter a data (-1 for no data): “;
cin >> x;
if(x==-1)
return ;
p=new tbtnode;
p->data=x;
if(leftorright==0)
{
p->flag=0;
p->lbit=fatherof->lbit;
p->left=fatherof->left;
fatherof->left=p;
fatherof->lbit=1;
p->rbit=0;
p->right=fatherof;
}
else
{
p->flag=1;
p->rbit=fatherof->rbit;
p->right=fatherof->right;
fatherof->right=p;
fatherof->rbit=1;
p->lbit=0;
p->left=fatherof;
}
cout<<”\n\n\tEnter left child of “<<x;
create1(p,0);
cout<<”\n\n\tEnter right child of “<<x;
create1(p,1);
}
void TBT:: create()
{
create1(root,0);
}
tbtnode * TBT::presuc(tbtnode *t)
{
if(t->lbit==1)
return(t->left);
if(t->rbit==1)
return(t->right);
while(t->rbit==0)
t=t->right;
return(t->right);
}
void TBT::preorder()
{
tbtnode *t;
t=root->left;
cout <<”\n\n”;
while(t!=root)
{
cout<<” “<<t->data;
t=presuc(t);
}
}
tbtnode * TBT::insuc(tbtnode *t)
{
if(t->rbit==1)
{
t=t->right;
while(t->lbit==1)
t=t->left;
return(t);
}
else
return(t->right);
}
void TBT::inorder()
{
tbtnode *t;
t=root->left;
cout<<”\n\n”;
while(t->lbit==1)
t=t->left;
while(t!=root)
{
cout<<” “<<t->data;
t=insuc(t);
}
}
tbtnode * TBT::postsuc(tbtnode *t)
{
if(t->flag==0)
{
t=father(t);
if(t->rbit==0)
return(t);
else
{
if(t==t->right)
return(t);
t=t->right;
while(t->lbit==1 || t->rbit==1)
if(t->lbit==1)
t=t->left;
else
t=t->right;
return(t);
}
}
else
return(father(t));
}
void TBT::postorder()
{
tbtnode *t;
t=root->left;
while(t->lbit==1 || t->rbit==1)
if(t->lbit==1)
t=t->left;
else
t=t->right;
while(t!=root)
{
cout<<” “<<t->data;
t=postsuc(t);
}
}
tbtnode * TBT::father(tbtnode *t)
{
if(t->flag==0)
{
while(t->rbit==1)
t=t->right;
return(t->right);
}
else
{
while(t->lbit==1)
t=t->left;
return(t->left);
} }

Data Structures- Program in C++ to find height,mirror image,leaf nodes of binary search tree

Description:
A binary search tree has following properties :

1. The left subtree of a node contains only nodes with keys less than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. Both the left and right subtrees must also be binary search trees.
4. There must be no duplicate nodes.

Code :

#include<iostream.h>
#include<conio.h>
#include<alloc.h>
#include<stdio.h>
typedef struct node
{
int data;
struct node *left;
struct node *right;
}node;

class bst
{
public:
node *root;
void create();
void insert(node *root,node *New);
void bfs(node *root);
void inorder(node *root);
int count(node *root);
node* mirror(node *temp);
int height(node *temp);
int max(int v1,int v2);
};
void bst::create()
{
int count,i;
node *New;
root=NULL;
cout<<”\n\nEnter the number of nodes: “;
cin>>count;
for(i=0;i<count;i++)
{
New=(node*)malloc(sizeof(node));
New->left=NULL;
New->right=NULL;
cout<<”\nEnter the data: “;
cin>>New->data;
if(root==NULL)
root=New;
else
insert(root,New);
}
}
void bst::insert(node *root,node *New)
{
if(New->data < root->data)
if(root->left==NULL)
root->left=New;
else
insert(root->left,New);
if(New->data > root->data)
if(root->right==NULL)
root->right=New;
else
insert(root->right,New);
}
node* bst::mirror(node *temp)
{
node *temp1;
if(temp==NULL)
return NULL;
else
{
temp1=temp->left;
temp->left=mirror(temp->right);
temp->right=mirror(temp1);
return temp;
}
}
void bst::inorder(node *root)
{
node *temp;
temp=root;
if(temp!=NULL)
{
inorder(temp->left);
cout<<” “<<temp->data;
inorder(temp->right);
}
}
class q
{
node *data[30];
int r,f;
public:
q()
{
r=f=-1;
}
int empty()
{
if(r==-1)
return 1;
return 0;
}
void insert(node *p)
{
if(empty())
r=f=0;
else
r=r+1;
data[r]=p;
}
node *del()
{
node *p=data[f];
if(r==f)
r=f=-1;
else
f=f+1;
return p;
}
};
void bst::bfs(node *root)
{
q q1;
node *temp3;
if(root==NULL)
{
cout<<”\n\nTree is empty.”;
return ;
}
q1.insert(root);
while(!q1.empty())
{
temp3=q1.del();
if(temp3)
{
cout<<” “<<temp3->data;
if(temp3->left)
q1.insert(temp3->left);
if(temp3->right)
q1.insert(temp3->right);
}
else
break;
}
}
int bst::height(node *temp)
{
if(temp==NULL)
return 0;
if(temp->left==NULL && temp->right==NULL)
return 0;
return(max(height(temp->left),height(temp->right))+1);
}
int bst::max(int v1,int v2)
{
if(v1 > v2)
return v1;
else
return v2;
}
int bst::count(node *root)
{
int cnt;
node *temp2;
temp2=root;
if(temp2==NULL)
return 0;
if(temp2->left==NULL && temp2->right==NULL)
return 1;
cnt=count(temp2->left) + count(temp2->right);
return cnt;
}
void main()
{
int ch,cnt,ht;
char ans;
bst a;
clrscr();
cout<<”\n\n\t\t\t\t\t\t\t\t\t\t……OPERATIONS ON BINARY SEARCH TREE……”;
do
{
cout<<”\n\nMENU: “;
cout<<”\n\n1.Create BST\n\n2.Display\n\n3.Counting leaf nodes\n\n4.BFS\n\n5.Mirror\n\n6.Height”;
cout<<”\n\nEnter your choice: “;
cin>>ch;
switch(ch)
{
case 1:
a.create();
break;
case 2:
cout<<”\n\nInorder: “;
a.inorder(a.root);
break;
case 3:
cnt=a.count(a.root);
cout<<”\n\nNumber of leaf nodes: “<< cnt;
break;
case 4:
cout<<”\n\nBFS: “;
a.bfs(a.root);
break;
case 5:
cout<<”\n\nMirror Image: “;
a.mirror(a.root);
a.inorder(a.root);
break;
case 6:
ht=a.height(a.root);
cout<<”\n\nHeight of the tree: “<< ht;
break;
}
cout<<”\n\nDo you want to continue?(y/n): “;
fflush(stdin);
cin>>ans;
}while(ans==’y’ || ans==’Y');
getch(); }

Data Structures Program to create a binary tree and perform recursive and non-recursive traversals

Description :
A binary tree is a data structure in which each node has at most two child nodes called  as “left” and “right”. The tree has a header, which contains a link to a designated node (the root node). The root node has no parent.


Code :
#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include<alloc.h>
typedef struct node
{
int data;
struct node *left;
struct node *right;
}node;
class tree
{
public:
node *root;
tree()
{
root=NULL;
}

node* create();
void insert(node *root,node *New);
void inorder(node *root);
void preorder(node *root);
void postorder(node* root);
void nonrec_inorder(node *root);
void nonrec_preorder(node *root);
void nonrec_postorder(node* root);
};
class stack
{
node *data[30];
int top;
public:
stack()
{
top=-1;
}
int empty()
{
if(top==-1)
return 1;
return 0;
}
void push(node *root)
{
data[++top]=root;
}
node *pop()
{
return (data[top--]);
}
};
void main()
{
char ch;
int choice;
tree o;
clrscr();
cout<<”\n\n\t\t\t\t\t\t\t\t\t\t……BINARY TREE TRAVERSALS……”;
do
{
cout<<”\n\nMENU: “;
cout<<”\n\n1.Create\n\n2.Inorder(Recursive)\n\n3.Preorder(Recursive)\n\n4.Postorder(Recursive)\n\n5.Inorder(Non-Recursive)\n\n6.Preorder(Non-Recursive)\n\n7.Postorder(Non-Recursive)” ;
cout<<”\n\nEnter Your Choice: “;
fflush(stdin);
cin>>choice;
switch(choice)
{
case 1:
o.create();
break;
case 2 :
cout<<”\nInorder Recursive Traversal: “;
o.inorder(o.root);
break;
case 3 :
cout<<”\nPreorder Recursive Traversal: “;
o.preorder(o.root);
break;
case 4 :
cout<<”\nPostorder Recursive Traversal: “;
o.postorder(o.root);
break;
case 5 :
cout<<”\nInorder Non-Recursive Traversal: “;
o.nonrec_inorder(o.root);
break;
case 6:
cout<<”\nPreorder Non-Recursive Traversal: “;
o.nonrec_preorder(o.root);
break;
case 7:
cout<<”\nPostorder Non-Recursive Traversal: “;
o.nonrec_postorder(o.root);
break;
default:
cout<<”\n\nPlease Enter Correct Choice.”;
}
cout<<”\n\nDo You Want To Continue?(y/n): “;
fflush(stdin);
cin>>ch;
}while(ch==’y’ || ch==’Y');
getch();
}
node* tree::create()
{
node *New;
char ans;
do
{
New=new node;
New->left=NULL;
New->right=NULL;
cout<<”\n\nEnter the data: “;
cin>>New->data;
if(root==NULL)
{
root=New;
}
else
{
insert(root,New);
}
cout<<”\nDo you want to create more nodes?(y/n): ” ;
fflush(stdin);
cin>>ans;
}while(ans==’y’ || ans==’Y');
return root;
}
void tree::insert(node *root,node *New)
{
char ch1;
cout<<”\n\nInsert in left subtree or right subtree of “<<root->data<<” ?(l/r): “;
fflush(stdin);
cin>>ch1;
if(ch1==’l’ || ch1==’L')
{
if(root->left==NULL)
{
root->left=New;
}
else
{
insert(root->left,New);
}
}
if(ch1==’r’ || ch1==’R')
{
if(root->right==NULL)
{
root->right=New;
}
else
{
insert(root->right,New);
}
}
}
void tree::inorder(node *root)
{
node *temp;
temp=root;
if(temp!=NULL)
{
inorder(temp->left);
cout<<” “<<temp->data;
inorder(temp->right);
}
}
void tree::preorder(node *root)
{
node *temp;
temp=root;
if(temp!=NULL)
{
cout<<” “<<temp->data;
preorder(temp->left);
preorder(temp->right);
}
}
void tree::postorder(node *root)
{
node *temp;
temp=root;
if(temp!=NULL)
{
postorder(temp->left);
postorder(temp->right);
cout<<” “<<temp->data;
}
}
void tree::nonrec_inorder(node *root)
{
stack s;
node *temp=root;
cout<<”\t”;
while(temp!=NULL)
{
s.push(temp);
temp=temp->left;
}
while(!s.empty())
{
temp=s.pop();
cout<<” “<<temp->data;
temp=temp->right;
while(temp!=NULL)
{
s.push(temp);
temp=temp->left;
}
}
}
void tree::nonrec_preorder(node *root)
{
stack s;
node *temp=root;
cout<<”\t”;
while(temp!=NULL)
{
cout<<” ” <<temp->data;
s.push(temp);
temp=temp->left;
}
while(!s.empty())
{
temp=s.pop();
temp=temp->right;
while(temp!=NULL)
{
cout<<” “<<temp->data;
s.push(temp);
temp=temp->left;
}
}
}
void tree::nonrec_postorder(node *root)
{
stack s,s1;
node *temp=root;
cout<<”\t”;
while(temp!=NULL)
{
s.push(temp);
s1.push(NULL);
temp=temp->left;
}
while(!s.empty())
{
temp=s.pop();
if(s1.pop()==NULL)
{
s.push(temp);
s1.push((node *)1);
temp=temp->right;
while(temp!=NULL)
{
s.push(temp);
s1.push(NULL);
temp=temp->left;
}
}
else
cout<<” “<<temp->data;
} }