Lab Programs:
Week1: a)Write a C++ program to implement the Stack ADT using Array.
#include<iostream.h>
#include<conio.h>
#include<process.h>
#define size 5
template<class T>
class stack
{
public:
T s[size],top;
stack()
{
top=-1;
}
void push();
void pop();
void show();
};
template<class T>
void stack<T>::push()
{
T n;
if(top==size-1)
{
cout<<"\nstack
is overflow";
}
else
{
top++;
cout<<"enter
the value of n:";
cin>>n;
s[top]=n;
cout<<"\nele
is pushed";
}
}
template<class T>
void stack<T>::pop()
{
T dx;
if(top==-1)
{
cout<<"\nstack
is underflow";
}
else
{
dx=s[top];
top--;
cout<<"\n
poped ele is:"<<dx;
}
}
template<class T>
void stack<T>::show()
{
T i;
if(top==-1)
{
cout<<"\nstack
is empty";
}
else
{
cout<<"\nstack ele are:";
for(i=top;i>=0;i--)
{
cout<<"\n"<<s[i];
}
}
}
void main()
{
int ur;
stack <int>s;
while(1)
{
clrscr();
cout<<"\n1.push";
cout<<"\n2.pop";
cout<<"\n3.show";
cout<<"\n4.exit";
cout<<"\nenter ur's choice:";
cin>>ur;
switch(ur)
{
case 1:
s.push();
break;
case 2:
s.pop();
break;
case 3:
s.show();
break;
case 4:
exit(0);
}
getch();
}
}
Week1: b)
#include<iostream.h>
#include<conio.h>
#include<process.h>
#define size 5
template<class T>
class queue
{
public:
T q[size],rear,front;
queue()
{
rear=-1;
front=0;
}
void insert(T n);
void del();
void show();
};
template<class T>
void queue<T>::insert(T n)
{
if(rear==size-1)
{
cout<<"\nqueue
is over flow";
}
else
{
rear++;
q[rear]=n;
cout<<"\n"<<n<<"elemnet
is inserted";
}
}
template<class T>
void queue<T>::del()
{
T dx;
if(rear==-1)
{
cout<<"\nqueue
is under flow";
}
else
if(front==rear)
{
dx=q[front];
front=0;
rear=-1;
cout<<"\n
deleted elemnet is :"<<dx;
}
else
{
dx=q[front];
front++;
cout<<"\n
deleted elemnet is :"<<dx;
}
}
template<class T>
void queue<T>::show()
{
T i;
if(rear==-1)
{
cout<<"\n
queue is empty";
}
else
{
cout<<"\n
queue elements are:";
for(i=front;i<=rear;i++)
{
cout<<"\n"<<q[i];
}
}
}
void main()
{
int ur,n;
queue <int>q1;
while(1)
{
clrscr();
cout<<"\nqueue oprations:";
cout<<"\n1.insert:";
cout<<"\n2.del:";
cout<<"\n3.show:";
cout<<"\n4.exit:";
cout<<"\nenter the ur's choice:";
cin>>ur;
switch(ur)
{
case 1:
cout<<"enter
the element for queue:";
cin>>n;
q1.insert(n);
break;
case 2:
q1.del();
break;
case 3:
q1.show();
break;
case 4:
exit(0);
}
getch();
}
}
Week 2:a)Write a C++ program to implement the Stack ADT using singly linked list.
#include<iostream.h>
#include<conio.h>
#include<process.h>
template<class T>
class node
{
public:
T num;
node <T>*next;
};
template<class T>
class stack
{
public:
node <T>*top;
stack()
{
top=NULL;
}
void push();
void pop();
void show();
};
template<class T>
void stack<T>::push()
{
int n;
node <T>*new1;
cout<<"enter an ele for SLL:";
cin>>n;
new1=new node<T>;
new1->num=n;
new1->next=top;
top=new1;
cout<<"\nnode is pushed";
}
template<class T>
void stack<T>::pop()
{
node <T>*temp;
if(top==NULL)
{
cout<<"\nstack
is empty";
}
else
{
temp=top;
top=top->next;
temp->next=NULL;
cout<<"\n
poped ele is:"<<temp->num;
delete
temp;
}
}
template<class T>
void stack<T>::show()
{
node <T>*temp;
if(top==NULL)
{
cout<<"\nstack
is empty";
}
else
{
temp=top;
cout<<"\nstack
elements are:";
while(temp!=NULL)
{
cout<<"\n"<<temp->num;
temp=temp->next;
}
}
}
void main()
{
int ur;
stack <int>s;
while(1)
{
clrscr();
cout<<"\n1.push";
cout<<"\n2.pop";
cout<<"\n3.show";
cout<<"\n4.exit";
cout<<"\nenter ur's choice:";
cin>>ur;
switch(ur)
{
case 1:
s.push();
break;
case 2:
s.pop();
break;
case 3:
s.show();
break;
case 4:
exit(0);
}
getch();
}
}
Week2:b)Write a C++ program to implement the Queue ADT using singly linked list.
#include<iostream.h>
#include<conio.h>
#include<process.h>
template<class T>
class node
{
public:
T num;
node <T>*next;
};
template<class T>
class queue
{
public:
node <T>*front;
node <T>*rear;
queue()
{
front=NULL;
rear=NULL;
}
void insert();
void del();
void show();
};
template<class T>
void queue<T>::insert()
{
T n;
node <T>*new1;
cout<<"enter an ele for SLL:";
cin>>n;
new1=new node<T>;
new1->num=n;
new1->next=NULL;
if(front==NULL)
{
front=new1;
rear=new1;
}
else
{
rear->next=new1;
rear=new1;
}
cout<<"\nnode is inserted";
}
template<class T>
void queue<T>::del()
{
node <T>*temp;
if(front==NULL)
{
cout<<"\nqueue
is empty";
}
else
if(front==rear)
{
temp=front;
temp->next=NULL;
front=NULL;
rear=NULL;
cout<<"\n
deled ele is:"<<temp->num;
delete
temp;
}
else
{
temp=front;
front=front->next;
temp->next=NULL;
cout<<"\n
deled ele is:"<<temp->num;
delete
temp;
}
}
template<class T>
void queue<T>::show()
{
node <T>*temp;
if(front==NULL)
{
cout<<"\nqueue
is empty";
}
else
{
temp=front;
cout<<"\nqueue
elements are:";
while(temp!=NULL)
{
cout<<"\t"<<temp->num;
temp=temp->next;
}
}
}
void main()
{
int ur;
queue <int>q1;
while(1)
{
clrscr();
cout<<"\n1.insert";
cout<<"\n2.del";
cout<<"\n3.show";
cout<<"\n4.exit";
cout<<"\nenter ur's choice:";
cin>>ur;
switch(ur)
{
case 1:
q1.insert();
break;
case 2:
q1.del();
break;
case 3:
q1.show();
break;
case 4:
exit(0);
}
getch();
}
}
Week 3:
Write C++ programs to implement the deque ADT using a doubly linked list and an Array
Write C++ programs to implement the deque ADT using a doubly linked list and an Array
//write a program to
implement he deque ADT using Array.
|
//write a program to
implement he deque ADT using doubly linked list.
|
#include<iostream.h>
#include<conio.h>
#include<process.h>
#define size 5
class dqueue
{
int rear;
int front;
int dq[size];
public:
dqueue()
{
rear=-1;
front=-1;
}
void
insertrear(int);
void delfront();
void delrear();
void
insertfront(int);
void show();
};
void
dqueue::insertrear(int n)
{
if(rear==size-1)
{
cout<<"\n dqueue is over flow";
}
else
{
rear++;
dq[rear]=n;
if(front==-1)
{
front=0;
}
}
}
void
dqueue::delfront()
{
if(rear==-1&&front==-1)
{
cout<<"\ndqueue is underflow";
}
else
{
int dx;
dx=dq[front];
cout<<"\n deleted elemnt is:"<<dx;
if(front ==rear)
{
front=-1;
rear=-1;
}
else
{
front++;
}
}
}
void
dqueue::delrear()
{
if(rear==-1)
{
cout<<"\n delete is not possible";
}
else
{
int dx;
dx=dq[rear];
cout<<"\ndeleted element is:"<<dx;
if(rear==front)
{
rear=-1;
front=-1;
}
else
{
rear--;
}
}
}
void
dqueue::insertfront(int n)
{
if(front==0&&rear==size-1)
{
cout<<"\ninsertion is not possible";
}
else
{
front--;
dq[front]=n;
}
}
void dqueue::show()
{
if(front==-1&&rear==-1)
{
cout<<"\ndqueue is empty";
}
else
{
for(int i=front;i<=rear;i++)
{
cout<<" "<<dq[i];
}
}
}
void main()
{
dqueue d;
int ur,iur,our,n;
while(1)
{
clrscr();
cout<<"\ndqueueue
opration are:";
cout<<"\n1.input
restricted queue:";
cout<<"\n2.ouput
restricted queue:";
cout<<"\n3.exit";
cout<<"\nenter
user choice:";
cin>>ur;
switch(ur)
{
case 1: while(1)
{
cout<<"\ninput restricted queue operations are:";
cout<<"\n1.insertrear";
cout<<"\n2.delfront";
cout<<"\n3.delrear";
cout<<"\n4.show";
cout<<"\n5.exit";
cout<<"\nenter user choice:";
cin>>iur;
switch(iur)
{
case 1:
cout<<"enter the element for deque:";
cin>>n;
d.insertrear(n);
break;
case 2:
d.delfront();
break;
case 3:
d.delrear();
break;
case 4:
d.show();
break;
case 5:
exit(0);
default:cout<<"invalid entry";
break;
}
}
case 2:
while(1)
{
cout<<"\noutput restricted queue operations are:";
cout<<"\n1.insertfront";
cout<<"\n2.insertrear";
cout<<"\n3.delfront";
cout<<"\n4.show";
cout<<"\n5.exit";
cout<<"\nenter user choice:";
cin>>our;
switch(our)
{
case 1:
cout<<"enter the element for deque:";
cin>>n;
d.insertfront(n);
break;
case 2:
cout<<"enter the element for deque:";
cin>>n;
d.insertrear(n);
break;
case 3:
d.delfront();
break;
case 4:
d.show();
break;
case 5:
exit(0);
default:cout<<"invalid entry";
break;
}
}
case 3:exit(0);
default:cout<<"invalid entry";
break;
}
getch();
}
}
|
#include<iostream.h>
#include<conio.h>
#include<process.h>
class node
{
public:
node *prev;
int num;
node *next;
};
class dequeedll
{
node *root;
node *last;
public:
dequeedll()
{
root=NULL;
last=NULL;
}
void create();
void show();
void f_insert();
void l_insert();
void f_del();
void l_del();
};
void
dequeedll::create()
{
int n;
cout<<"\nEnter
-1 to stop reading values.";
while(1)
{
cout<<"\nEnter
element for dequeedll:";
cin>>n;
if(n==-1)
break;
node *new1;
new1=new node;
new1->num=n;
new1->prev=NULL;
new1->next=NULL;
if(root==NULL)
{
root=new1;
last=new1;
}
else
{
new1->prev=last;
last->next=new1;
last=new1;
}
}
}
void
dequeedll::show()
{
node *temp;
if(root==NULL)
{
cout<<"\nList
is empty.";
}
else
{
temp=root;
while(temp!=NULL)
{
cout<<" "<<temp->num;
temp=temp->next;
}
delete temp;
}
}
void
dequeedll::f_insert()
{
int n;
node *new1;
cout<<"\nEnter
element for new node:";
cin>>n;
new1=new node;
new1->num=n;
new1->next=NULL;
new1->prev=NULL;
root->prev=new1;
new1->next=root;
root=new1;
}
void
dequeedll::l_insert()
{
int n;
node *new1;
cout<<"\nEnter
element for new node:";
cin>>n;
new1=new node;
new1->num=n;
new1->next=NULL;
new1->prev=NULL;
last->next=new1;
new1->prev=last;
last=new1;
}
void
dequeedll::f_del()
{
node *temp;
if(root==last)
{
temp=root;
root=NULL;
last=NULL;
cout<<"\nDeleted
element is "<<temp->num;
delete temp;
}
else
{
temp=root;
root=root->next;
temp->next=NULL;
root->prev=NULL;
cout<<"\nDeleted
element is "<<temp->num;
delete temp;
}
}
void
dequeedll::l_del()
{
node *temp;
if(root==last)
{
temp=last;
root=NULL;
last=NULL;
cout<<"\nDeleted
element is "<<temp->num;
delete temp;
}
else
{
temp=last;
last=last->prev;
temp->prev=NULL;
last->next=NULL;
cout<<"\nDeleted
element is "<<temp->num;
delete temp;
}
}
void main()
{
int ur;
dequeedll d;
while(1)
{
clrscr();
cout<<"\ndequeedll
operations\n";
cout<<"1.Create\n2.F_insert\n3.L_insert\n4.F_delete\n5.L_delete";
cout<<"\n6.Show\n7.Exit";
cout<<"\nEnter
user's choice:";
cin>>ur;
switch(ur)
{
case 1:d.create();
break;
case 2:d.f_insert();
break;
case 3:d.l_insert();
break;
case 4:d.f_del();
break;
case 5:d.l_del();
break;
case 6:d.show();
break;
case 7:exit(0);
default:
cout<<"\nInvalid choice....Try again...!!";
break;
}
getch();
}
}
|
Week: 4 Write a C++ programs to perform the following operations
a) insert an element into a binary search tree
#include<iostream.h>
#include<conio.h>
class node
{
public:
node *left;
int data;
node *right;
};
node *root=NULL;
class bst
{
public:
node * create(int data,node *p)
{
if(!p)
{
p=new node;
p->data=data;
p->left=NULL;
p->right=NULL;
return(p);
}
if(data<p->data)
p->left=create(data,p->left);
else
if(data>p->data)
p->right=create(data,p->right);
return (p);
}
node * del(node *p,node *q)
{
node *temp;
if(p->right !=NULL)
p->right = del(p->right, q);
else
{
dnode = p;
q->data = p->data;
p=p->left;
delete temp;
}
return p;
}
node *deleteNode( node *p,int data)
{
node *t;
if(!p)
{
cout<<"\ndeleted element is not found ";
return (p);
}
else
{
if(data <p->data)
p->left = deleteNode(p->left, data);
else
if(data > p->data)
p->right=deleteNode(p->right,data);
else
{
t=p;
if(t->right==NULL)
{
p=t->left;
delete t;
}
else
if(t->left==NULL)
{
p=t->right;
delete t;
}
else
t->left=del(t->left, t);
}
}
return (p);
}
node * search(node *p,node *q)
{
node *dnode;
if(p->right !=NULL)
p->right = del(p->right, q);
else
{
dnode = p;
q->data = p->data;
p=p->left;
cout<<"\nsearch element is:"<<dnode->data;
}
return p;
}
node *searchNode( node *p,int data)
{
node *t;
if(!p)
{
cout<<"\n search element is not found ";
return (p);
}
else
{
if(data <p->data)
p->left = searchNode(p->left, data);
else
if(data > p->data)
p->right=searchNode(p->right,data);
else
{
t=p;
if(t->right==NULL)
{
p=t->left;
cout<<"\nsearch element is found:"<<t->data;
}
else
if(t->left==NULL)
{
p=t->right;
cout<<"\nsearch element is found:"<<t->data;
}
else
t->left=search(t->left, t);
}
}
return (p);
}
void preorder(node *p)
{
if(p!=NULL)
{
cout<<" "<<p->data;
preorder(p->left);
preorder(p->right);
}
}
void inorder(node *p)
{
if(p!=NULL)
{
inorder(p->left);
cout<<" "<<p->data;
inorder(p->right);
}
}
void postorder(node *p)
{
if(p!=NULL)
{
postorder(p->left);
cout<<" "<<p->data;
postorder(p->right);
}
}
};
void main()
{
int data;
bst d;
node *root =NULL;
clrscr();
while(1)
{
cout<<"\nenter the data for binary search tree:<-1 to exit>?";
cin>>data;
if(data==-1)
break;
root=d.create(data,root);
}
cout<<"\nelements in binary search tree:\n";
cout<<"\npre order:";
d.preorder(root);
cout<<"\nin order:";
d.inorder(root);
cout<<"\npost order:";
d.postorder(root);
getch();
while(1)
{
cout<<"\nenter to be deleted element: <-1 to exit>:";
cin>>data;
if(data==-1)
break;
root=d.deleteNode(root,data);
cout<<"\nTree after deletion: \n";
d.preorder(root);
}
getch();
while(1)
{
cout<<"\nenter to the search element: <-1 to exit>:";
cin>>data;
if(data==-1)
break;
root=d.searchNode(root,data);
}
getch();
}
Week 5:
Write a C++ programs that use recursive functions to traverse the given binary tree
a) Preorder b) Inorder c) Postorder
#include<iostream.h>
#include<conio.h>
template<class T>
struct node
{
node *left;
T data;
node *right;
};
template<class T>
class tree
{
node<T> *root;
public:
void create();
void insert(node<T> *p);
void traverse();
void preorder(node<T> *p);
void inorder(node<T> *p);
void postorder(node<T> *p);
};
template<class T>
void tree<T>::create()
{
T n;
root=NULL;
node<T> *new1;
while(1)
{
cout<<"'enter the data:";
cin>>n;
if(n==-1)
break;
new1 =new node<T>;
new1->data=n;
new1->left=NULL;
new1->right=NULL;
insert(new1);
}
}
template<class T>
void tree<T>::insert(node<T> *p)
{
if(root==NULL)
{
root=p;
}
else
{
node<T> *temp=root;
while(1)
{
if(p->data<temp->data)
{
if(temp->left!=NULL)
{
temp=temp->left;
}
else
{
temp->left=p;
return;
}
}
else
{
if(temp->right!=NULL)
{
temp=temp->right;
}
else
{
temp->right=p;
return;
}
}
}
}
}
template<class T>
void tree<T>::preorder(node<T> *p)
{
if(p!=NULL)
{
cout<<" "<<p->data;
preorder(p->left);
preorder(p->right);
}
}
template<class T>
void tree<T>::inorder(node<T> *p)
{
if(p!=NULL)
{
inorder(p->left);
cout<<" "<<p->data;
inorder(p->right);
}
}
template<class T>
void tree<T>::postorder(node<T> *p)
{
if(p!=NULL)
{
postorder(p->left);
postorder(p->right);
cout<<" "<<p->data;
}
}
template<class T>
void tree<T>::traverse()
{
cout<<"\npreorder:";
preorder(root);
getch();
cout<<"\ninorder:";
inorder(root);
getch();
cout<<"\npostorder:";
postorder(root);
}
void main()
{
clrscr();
tree <int>t;
t.create();
t.traverse();
getch();
}
Week 6:
Write a C++ programs that use non-recursive functions to traverse the given binary tree
a) Preorder b) Inorder c) Postorder
#include<iostream.h>
#include<conio.h>
class node
{
public:
node *left;
int data,flag;
node *right;
};
node *root=NULL;
class Bst
{
public:
node * create(int data,node *p)
{
if(!p)
{
p=new node;
p->data=data;
p->left=NULL;
p->right=NULL;
return(p);
}
if(data<p->data)
p->left=create(data,p->left);
else
if(data>p->data)
p->right=create(data,p->right);
return (p);
}
void non_preorder(node *p);
void non_inorder(node *p);
void non_postorder(node *p);
};
void Bst::non_preorder(node *p)
{
int top=0;
node *s[20],*pt=p;
s[0]=NULL;
while(pt != NULL)
{
cout<<"\t"<<pt->data;
if(pt->right != NULL)
s[++top] = pt->right;
if(pt->left != NULL)
pt = pt->left;
else
pt = s[top--];
}
}
void Bst::non_inorder(node *p)
{
int top=0;
node *s[20],*pt=p;
s[0]=NULL;
while(pt != NULL)
{
s[++top] = pt;
pt = pt->left;
}
pt = s[top--];
while(pt != NULL)
{
cout<<"\t"<<pt->data;
if(pt->right != NULL)
{
pt = pt->right;
while(pt != NULL)
{
s[++top] = pt;
pt = pt->left;
}
}
pt = s[top--];
}
}
void Bst::non_postorder(node *p)
{
node *s[20];
int top=-1;
node *temp=p;
while(temp!=NULL)
{
while(temp!= NULL)
{
top++;
s[top] = temp;
temp = temp->left;
}
label:temp =s[top];
top--;
if(temp->flag==1)
{
cout<<"\t"<<temp->data;
break;
}
else
{
temp->flag=1;
top++;
s[top] = temp;
temp=temp->right;
}
}
if(top>=0)
goto label;
}
void main()
{
int data;
Bst d;
node *root =NULL;
clrscr();
while(1)
{
cout<<"\nenter the data for binary search tree:<-1 to exit>?";
cin>>data;
if(data==-1)
break;
root=d.create(data,root);
}
cout<<"\nelements in binary search tree:\n";
cout<<"\npre order:";
d.non_preorder(root);
cout<<"\nin order:";
d.non_inorder(root);
cout<<"\npost order:";
d.non_postorder(root);
getch();
}
Week: 7 Write a C++ programs for implementation of bfs and dfs for a given graph.
#include<conio.h>
#include<iostream.h>
#include<stdlib.h>
void create(); // For creating a graph
void dfs(); // For Deapth First Search(DFS) Traversal.
void bfs(); // For Breadth First Search(BFS) Traversal.
struct node // Structure for elements in the graph
{
int data,status;
struct node *next;
struct link *adj;
};
struct link // Structure for adjacency list
{
struct node *next;
struct link *adj;
};
struct node *start,*p,*q;
struct link *l,*k;
int main()
{
int choice;
clrscr();
create();
while(1)
{
cout<<"-----------------------";
cout<<"\n1:DFS \n2:BSF \n3:Exit \nEnter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
dfs();
break;
case 2:
bfs();
break;
case 3:
exit(0);
break;
default:
cout<<"Incorrect choice!Re-enter your choice.";
getch();
}
}
return 0;
}
void create() // Creating a graph
{
int n,flag=0;
start=NULL;
cout<<"\nEnter the nodes in the graph(-1 to exit): ";
while(1)
{
cout<<"\nEnter the data \n";
cin>>n;
if(n==-1)
break;
p=new node;
p->data=n;
p->status=0;
p->next=NULL;
p->adj=NULL;
if(flag==0)
{
start=p;
q=p;
flag++;
}
else
{
q->next=p;
q=p;
}
}
p=start;
while(p!=NULL)
{
cout<<"\nEnter the links to "<<p->data<<" (-1 to exit) : ";
flag=0;
while(1)
{
cin>>n;
if(n==-1)
break;
k=new link;
k->adj=NULL;
if(flag==0)
{
p->adj=k;
l=k;
flag++;
}
else
{
l->adj=k;
l=k;
}
q=start;
while(q!=NULL)
{
if(q->data==n)
k->next=q;
q=q->next;
}
}
p=p->next;
}
cout<<"-------------------------";
return;
}
// Deapth First Search(DFS) Traversal.
void bfs()
{
int qu[20],i=1,j=0;
p=start;
while(p!=NULL)
{
p->status=0;
p=p->next;
}
p=start;
qu[0]=p->data;
p->status=1;
while(1)
{
if(qu[j]==0)
break;
p=start;
while(p!=NULL)
{
if(p->data==qu[j])
break;
p=p->next;
}
k=p->adj;
while(k!=NULL)
{
q=k->next;
if(q->status==0)
{
qu[i]=q->data;
q->status=1;
qu[i+1]=0;
i++;
}
k=k->adj;
}
j++;
}
j=0;
cout<<"Breadth First Search Results";
cout<<"---------------------------";
while(qu[j]!=0)
{
cout<<qu[j]<<" ";
j++;
}
getch();
return;
}
// Breadth First Search(BFS) Traversal.
void dfs()
{
int stack[25],top=1;
cout<<"Deapth First Search Results";
cout<<"---------------------------";
p=start;
while(p!=NULL)
{
p->status=0;
p=p->next;
}
p=start;
stack[0]=0;
stack[top]=p->data;
p->status=1;
while(1)
{
if(stack[top]==0)
break;
p=start;
while(p!=NULL)
{
if(p->data==stack[top])
break;
p=p->next;
}
cout<<stack[top]<<" ";
top--;
k=p->adj;
while(k!=NULL)
{
q=k->next;
if(q->status==0)
{
top++;
stack[top]=q->data;
q->status=1;
}
k=k->adj;
}
}
getch();
return;
}
Week: 8 a)Write a C++ program for implementing the Merge Sort
#include<iostream.h>
#include<conio.h>
template<class T>
class mergesort
{
public:
void msort(T *,T,T,T);
void mpass(T *,T ,T);
};
template<class T>
void mergesort<T>::msort(T a[],T first,T size,T last)
{
T temp[20];
T low=first;
T high=size+1;
T k=first;
while((low<=size)&&(high<=last))
{
if(a[low]<=a[high])
{
temp[k]=a[low];
low++;
}
else
{
temp[k]=a[high];
high++;
}
k++;
}
if(low<=size)
{
for(T i=low;i<=size;i++)
{
temp[k]=a[i];
k++;
}
}
else
{
for(T j=high;j<=last;j++)
{
temp[k]=a[j];
k++;
}
}
for(T i=first;i<=last;i++)
{
a[i]=temp[i];
}
}
template<class T>
void mergesort<T>::mpass(T a[],T first,T last)
{
if(first!=last)
{
T mid=(first+last)/2;
mpass(a,first,mid);
mpass(a,mid+1,last);
msort(a,first,mid,last);
}
}
void main()
{
mergesort <int>m1;
clrscr();
int a[20];
int n;
cout<<"enter the value of n:";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"\n enter the"<<i+1<<"element:";
cin>>a[i];
}
cout<<"\n original order:";
for(i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
m1.mpass(a,0,n-1);
cout<<"\n after sorting :";
for(i=0;i<n;i++)
{
coudt<<a[i]<<" ";
}
getch();
}
Week: 8 b)Write a C++ program for implementing the Heap Sort
#include<iostream.h>
#include<conio.h>
template<class T>
class heap
{
T i,j,k,temp;
public:
void heaps(T *,T);
void create(T *,T);
void display(T *,T);
};
template<class T>
void heap<T>::create(T a[],T n)
{
for(k=2;k<=n;k++)
{
i=k;
temp=a[k];
j=i/2;
while((i>1)&&(temp>a[j]))
{
a[i]=a[j];
i=j;
j=i/2;
if(j<1)
j=1;
}
a[i]=temp;
}
}
template<class T>
void heap<T>::heaps(T a[],T n)
{
for(int k=n;k>=2;k--)
{
temp=a[1];
a[1]=a[k];
a[k]=temp;
i=1;
int value=a[1];
j=2;
if((j+1)<k)
if(a[j+1]>a[j])
j++;
while((j<=(k-1))&&(a[j]>value))
{
a[i]=a[j];
i=j;
j=2*i;
if((j+1)<k)
if(a[j+1]>a[j])
j++;
else
if(j>n)
j=n;
a[i]=value;
}
cout<<"\n";
for(i=1;i<=n;i++)
cout<<" "<<a[i];
}
}
template<class T>
void heap<T>::display(T a[],T n)
{
for(i=1;i<=n;i++)
{
cout<<" "<<a[i];
}
}
void main()
{
heap <int>h;
clrscr();
int a[20],n;
cout<<"\nEnter Value of n:";
cin>>n;
for(int i=1;i<=n;i++)
{
cout<<"\nEnter "<<i<<" Element:";
cin>>a[i];
}
cout<<"\n Original order:\n";;
h.display(a,n);
h.create(a,n);
cout<<"\n heap\n";
h.display(a,n);
h.heaps(a,n);
cout<<"\n after sorting:\n";
h.display(a,n);
getch();
}
Week 10:
write a C++ program to per form the following operation
#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 *rotateright(node *);
node *rotateleft(node *);
node *RRrotation(node *);
node *LLrotation(node *);
node *LRrotation(node *);
node *RLrotation(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,ur;
node *root=NULL;
clrscr();
cout<<"\n\t CREATION OF AVL TREE ";
while(1)
{
cout<<"\n\t1.Create\n\t2.Insert\n\t3.Delete\n\t4.Display\n\t5.Exit ";
cout<<"\nEnter ur choice: ";
cin>>ur;
if(ur==-99)
break;
switch(ur)
{
case 1:
cout<<"\nEnter the number of elements: ";
cin>>n;
cout<<"\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;
case 5:
exit(0);
}
}
getch();
}
node *AVL::insert(node *root,int x)
{
if(root==NULL)
{
root=new node;
root->data=x;
root->left=NULL;
root->right=NULL;
}
else
{
if(x>root->data)
{
root->right=insert(root->right,x);
if(BF(root)<=-2)
{
if(x>root->right->data)
root=RRrotation(root);
else
root=RLrotation(root);
}
}
else if(x<root->data)
{
root->left=insert(root->left,x);
if(BF(root)>=2)
{
if(x<root->left->data)
root=LLrotation(root);
else
root=LRrotation(root);
}
}
}
root->ht=height(root);
return(root);
}
node *AVL::delet(node *root,int x)
{
node *p;
if(root==NULL)
return(0);
else
if(x>root->data)
{
root->right=delet(root->right,x);
if(BF(root)>=2)
if(BF(root->left)>=0)
root=LLrotation(root);
else
root=LRrotation(root);
}
else if(x<root->data)
{
root->left=delet(root->left,x);
if(BF(root)<=-2)
if(BF(root->right)<=0)
root=RRrotation(root);
else
root=RLrotation(root);
}
else
{
if(root->right!=NULL)
{
p=root->right;
while(p->left!=NULL)
p=p->left;
root->data=p->data;
root->right=delet(root->right,p->data);
if(BF(root)>=2)
if(BF(root->left)>=0)
root=LLrotation(root);
else
root=LRrotation(root);
}
else
return(root->left);
}
root->ht=height(root);
return(root);
}
int AVL::height(node *root)
{
int LH,RH;
if(root==NULL)
return(0);
if(root->left==NULL)
LH=0;
else
LH=1+root->left->ht;
if(root->right==NULL)
RH=0;
else
RH=1+root->right->ht;
if(LH>RH)
return (LH);
else
return (RH);
}
int AVL::BF(node *root)
{
int LH,RH;
if(root==NULL)
return(0);
if(root->left==NULL)
LH=0;
else
LH=1+root->left->ht;
if(root->right==NULL)
RH=0;
else
RH=1+root->right->ht;
return(LH-RH);
}
node *AVL::rotateleft(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::rotateright(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::LLrotation(node *root)
{
root=rotateright(root);
return(root);
}
node *AVL::RRrotation(node *root)
{
root=rotateleft(root);
return(root);
}
node *AVL::LRrotation(node *root)
{
root->left=rotateleft(root->left);
root=rotateright(root);
return(root);
}
node *AVL::RLrotation(node *root)
{
root->right=rotateright(root->right);
root=rotateleft(root);
return(root);
}
void AVL::preorder(node *root)
{
if(root!=NULL)
{
cout<<" \n"<<root->data<<" [BF= "<<BF(root)<<"]";
preorder(root->left);
preorder(root->right);
}
}
void AVL::inorder(node *root)
{
if(root!=NULL)
{
inorder(root->left);
cout<<" \n"<<root->data<<" [BF= "<<BF(root)<<"]";
inorder(root->right);
}
}
#include<iostream.h>
#include<conio.h>
class node
{
public:
node *left;
int data;
node *right;
};
node *root=NULL;
class bst
{
public:
node * create(int data,node *p)
{
if(!p)
{
p=new node;
p->data=data;
p->left=NULL;
p->right=NULL;
return(p);
}
if(data<p->data)
p->left=create(data,p->left);
else
if(data>p->data)
p->right=create(data,p->right);
return (p);
}
node * del(node *p,node *q)
{
node *temp;
if(p->right !=NULL)
p->right = del(p->right, q);
else
{
dnode = p;
q->data = p->data;
p=p->left;
delete temp;
}
return p;
}
node *deleteNode( node *p,int data)
{
node *t;
if(!p)
{
cout<<"\ndeleted element is not found ";
return (p);
}
else
{
if(data <p->data)
p->left = deleteNode(p->left, data);
else
if(data > p->data)
p->right=deleteNode(p->right,data);
else
{
t=p;
if(t->right==NULL)
{
p=t->left;
delete t;
}
else
if(t->left==NULL)
{
p=t->right;
delete t;
}
else
t->left=del(t->left, t);
}
}
return (p);
}
node * search(node *p,node *q)
{
node *dnode;
if(p->right !=NULL)
p->right = del(p->right, q);
else
{
dnode = p;
q->data = p->data;
p=p->left;
cout<<"\nsearch element is:"<<dnode->data;
}
return p;
}
node *searchNode( node *p,int data)
{
node *t;
if(!p)
{
cout<<"\n search element is not found ";
return (p);
}
else
{
if(data <p->data)
p->left = searchNode(p->left, data);
else
if(data > p->data)
p->right=searchNode(p->right,data);
else
{
t=p;
if(t->right==NULL)
{
p=t->left;
cout<<"\nsearch element is found:"<<t->data;
}
else
if(t->left==NULL)
{
p=t->right;
cout<<"\nsearch element is found:"<<t->data;
}
else
t->left=search(t->left, t);
}
}
return (p);
}
void preorder(node *p)
{
if(p!=NULL)
{
cout<<" "<<p->data;
preorder(p->left);
preorder(p->right);
}
}
void inorder(node *p)
{
if(p!=NULL)
{
inorder(p->left);
cout<<" "<<p->data;
inorder(p->right);
}
}
void postorder(node *p)
{
if(p!=NULL)
{
postorder(p->left);
cout<<" "<<p->data;
postorder(p->right);
}
}
};
void main()
{
int data;
bst d;
node *root =NULL;
clrscr();
while(1)
{
cout<<"\nenter the data for binary search tree:<-1 to exit>?";
cin>>data;
if(data==-1)
break;
root=d.create(data,root);
}
cout<<"\nelements in binary search tree:\n";
cout<<"\npre order:";
d.preorder(root);
cout<<"\nin order:";
d.inorder(root);
cout<<"\npost order:";
d.postorder(root);
getch();
while(1)
{
cout<<"\nenter to be deleted element: <-1 to exit>:";
cin>>data;
if(data==-1)
break;
root=d.deleteNode(root,data);
cout<<"\nTree after deletion: \n";
d.preorder(root);
}
getch();
while(1)
{
cout<<"\nenter to the search element: <-1 to exit>:";
cin>>data;
if(data==-1)
break;
root=d.searchNode(root,data);
}
getch();
}
Week 5:
Write a C++ programs that use recursive functions to traverse the given binary tree
a) Preorder b) Inorder c) Postorder
#include<iostream.h>
#include<conio.h>
template<class T>
struct node
{
node *left;
T data;
node *right;
};
template<class T>
class tree
{
node<T> *root;
public:
void create();
void insert(node<T> *p);
void traverse();
void preorder(node<T> *p);
void inorder(node<T> *p);
void postorder(node<T> *p);
};
template<class T>
void tree<T>::create()
{
T n;
root=NULL;
node<T> *new1;
while(1)
{
cout<<"'enter the data:";
cin>>n;
if(n==-1)
break;
new1 =new node<T>;
new1->data=n;
new1->left=NULL;
new1->right=NULL;
insert(new1);
}
}
template<class T>
void tree<T>::insert(node<T> *p)
{
if(root==NULL)
{
root=p;
}
else
{
node<T> *temp=root;
while(1)
{
if(p->data<temp->data)
{
if(temp->left!=NULL)
{
temp=temp->left;
}
else
{
temp->left=p;
return;
}
}
else
{
if(temp->right!=NULL)
{
temp=temp->right;
}
else
{
temp->right=p;
return;
}
}
}
}
}
template<class T>
void tree<T>::preorder(node<T> *p)
{
if(p!=NULL)
{
cout<<" "<<p->data;
preorder(p->left);
preorder(p->right);
}
}
template<class T>
void tree<T>::inorder(node<T> *p)
{
if(p!=NULL)
{
inorder(p->left);
cout<<" "<<p->data;
inorder(p->right);
}
}
template<class T>
void tree<T>::postorder(node<T> *p)
{
if(p!=NULL)
{
postorder(p->left);
postorder(p->right);
cout<<" "<<p->data;
}
}
template<class T>
void tree<T>::traverse()
{
cout<<"\npreorder:";
preorder(root);
getch();
cout<<"\ninorder:";
inorder(root);
getch();
cout<<"\npostorder:";
postorder(root);
}
void main()
{
clrscr();
tree <int>t;
t.create();
t.traverse();
getch();
}
Week 6:
Write a C++ programs that use non-recursive functions to traverse the given binary tree
a) Preorder b) Inorder c) Postorder
#include<iostream.h>
#include<conio.h>
class node
{
public:
node *left;
int data,flag;
node *right;
};
node *root=NULL;
class Bst
{
public:
node * create(int data,node *p)
{
if(!p)
{
p=new node;
p->data=data;
p->left=NULL;
p->right=NULL;
return(p);
}
if(data<p->data)
p->left=create(data,p->left);
else
if(data>p->data)
p->right=create(data,p->right);
return (p);
}
void non_preorder(node *p);
void non_inorder(node *p);
void non_postorder(node *p);
};
void Bst::non_preorder(node *p)
{
int top=0;
node *s[20],*pt=p;
s[0]=NULL;
while(pt != NULL)
{
cout<<"\t"<<pt->data;
if(pt->right != NULL)
s[++top] = pt->right;
if(pt->left != NULL)
pt = pt->left;
else
pt = s[top--];
}
}
void Bst::non_inorder(node *p)
{
int top=0;
node *s[20],*pt=p;
s[0]=NULL;
while(pt != NULL)
{
s[++top] = pt;
pt = pt->left;
}
pt = s[top--];
while(pt != NULL)
{
cout<<"\t"<<pt->data;
if(pt->right != NULL)
{
pt = pt->right;
while(pt != NULL)
{
s[++top] = pt;
pt = pt->left;
}
}
pt = s[top--];
}
}
void Bst::non_postorder(node *p)
{
node *s[20];
int top=-1;
node *temp=p;
while(temp!=NULL)
{
while(temp!= NULL)
{
top++;
s[top] = temp;
temp = temp->left;
}
label:temp =s[top];
top--;
if(temp->flag==1)
{
cout<<"\t"<<temp->data;
break;
}
else
{
temp->flag=1;
top++;
s[top] = temp;
temp=temp->right;
}
}
if(top>=0)
goto label;
}
void main()
{
int data;
Bst d;
node *root =NULL;
clrscr();
while(1)
{
cout<<"\nenter the data for binary search tree:<-1 to exit>?";
cin>>data;
if(data==-1)
break;
root=d.create(data,root);
}
cout<<"\nelements in binary search tree:\n";
cout<<"\npre order:";
d.non_preorder(root);
cout<<"\nin order:";
d.non_inorder(root);
cout<<"\npost order:";
d.non_postorder(root);
getch();
}
Week: 7 Write a C++ programs for implementation of bfs and dfs for a given graph.
#include<conio.h>
#include<iostream.h>
#include<stdlib.h>
void create(); // For creating a graph
void dfs(); // For Deapth First Search(DFS) Traversal.
void bfs(); // For Breadth First Search(BFS) Traversal.
struct node // Structure for elements in the graph
{
int data,status;
struct node *next;
struct link *adj;
};
struct link // Structure for adjacency list
{
struct node *next;
struct link *adj;
};
struct node *start,*p,*q;
struct link *l,*k;
int main()
{
int choice;
clrscr();
create();
while(1)
{
cout<<"-----------------------";
cout<<"\n1:DFS \n2:BSF \n3:Exit \nEnter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
dfs();
break;
case 2:
bfs();
break;
case 3:
exit(0);
break;
default:
cout<<"Incorrect choice!Re-enter your choice.";
getch();
}
}
return 0;
}
void create() // Creating a graph
{
int n,flag=0;
start=NULL;
cout<<"\nEnter the nodes in the graph(-1 to exit): ";
while(1)
{
cout<<"\nEnter the data \n";
cin>>n;
if(n==-1)
break;
p=new node;
p->data=n;
p->status=0;
p->next=NULL;
p->adj=NULL;
if(flag==0)
{
start=p;
q=p;
flag++;
}
else
{
q->next=p;
q=p;
}
}
p=start;
while(p!=NULL)
{
cout<<"\nEnter the links to "<<p->data<<" (-1 to exit) : ";
flag=0;
while(1)
{
cin>>n;
if(n==-1)
break;
k=new link;
k->adj=NULL;
if(flag==0)
{
p->adj=k;
l=k;
flag++;
}
else
{
l->adj=k;
l=k;
}
q=start;
while(q!=NULL)
{
if(q->data==n)
k->next=q;
q=q->next;
}
}
p=p->next;
}
cout<<"-------------------------";
return;
}
// Deapth First Search(DFS) Traversal.
void bfs()
{
int qu[20],i=1,j=0;
p=start;
while(p!=NULL)
{
p->status=0;
p=p->next;
}
p=start;
qu[0]=p->data;
p->status=1;
while(1)
{
if(qu[j]==0)
break;
p=start;
while(p!=NULL)
{
if(p->data==qu[j])
break;
p=p->next;
}
k=p->adj;
while(k!=NULL)
{
q=k->next;
if(q->status==0)
{
qu[i]=q->data;
q->status=1;
qu[i+1]=0;
i++;
}
k=k->adj;
}
j++;
}
j=0;
cout<<"Breadth First Search Results";
cout<<"---------------------------";
while(qu[j]!=0)
{
cout<<qu[j]<<" ";
j++;
}
getch();
return;
}
// Breadth First Search(BFS) Traversal.
void dfs()
{
int stack[25],top=1;
cout<<"Deapth First Search Results";
cout<<"---------------------------";
p=start;
while(p!=NULL)
{
p->status=0;
p=p->next;
}
p=start;
stack[0]=0;
stack[top]=p->data;
p->status=1;
while(1)
{
if(stack[top]==0)
break;
p=start;
while(p!=NULL)
{
if(p->data==stack[top])
break;
p=p->next;
}
cout<<stack[top]<<" ";
top--;
k=p->adj;
while(k!=NULL)
{
q=k->next;
if(q->status==0)
{
top++;
stack[top]=q->data;
q->status=1;
}
k=k->adj;
}
}
getch();
return;
}
Week: 8 a)Write a C++ program for implementing the Merge Sort
#include<iostream.h>
#include<conio.h>
template<class T>
class mergesort
{
public:
void msort(T *,T,T,T);
void mpass(T *,T ,T);
};
template<class T>
void mergesort<T>::msort(T a[],T first,T size,T last)
{
T temp[20];
T low=first;
T high=size+1;
T k=first;
while((low<=size)&&(high<=last))
{
if(a[low]<=a[high])
{
temp[k]=a[low];
low++;
}
else
{
temp[k]=a[high];
high++;
}
k++;
}
if(low<=size)
{
for(T i=low;i<=size;i++)
{
temp[k]=a[i];
k++;
}
}
else
{
for(T j=high;j<=last;j++)
{
temp[k]=a[j];
k++;
}
}
for(T i=first;i<=last;i++)
{
a[i]=temp[i];
}
}
template<class T>
void mergesort<T>::mpass(T a[],T first,T last)
{
if(first!=last)
{
T mid=(first+last)/2;
mpass(a,first,mid);
mpass(a,mid+1,last);
msort(a,first,mid,last);
}
}
void main()
{
mergesort <int>m1;
clrscr();
int a[20];
int n;
cout<<"enter the value of n:";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"\n enter the"<<i+1<<"element:";
cin>>a[i];
}
cout<<"\n original order:";
for(i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
m1.mpass(a,0,n-1);
cout<<"\n after sorting :";
for(i=0;i<n;i++)
{
coudt<<a[i]<<" ";
}
getch();
}
Week: 8 b)Write a C++ program for implementing the Heap Sort
#include<iostream.h>
#include<conio.h>
template<class T>
class heap
{
T i,j,k,temp;
public:
void heaps(T *,T);
void create(T *,T);
void display(T *,T);
};
template<class T>
void heap<T>::create(T a[],T n)
{
for(k=2;k<=n;k++)
{
i=k;
temp=a[k];
j=i/2;
while((i>1)&&(temp>a[j]))
{
a[i]=a[j];
i=j;
j=i/2;
if(j<1)
j=1;
}
a[i]=temp;
}
}
template<class T>
void heap<T>::heaps(T a[],T n)
{
for(int k=n;k>=2;k--)
{
temp=a[1];
a[1]=a[k];
a[k]=temp;
i=1;
int value=a[1];
j=2;
if((j+1)<k)
if(a[j+1]>a[j])
j++;
while((j<=(k-1))&&(a[j]>value))
{
a[i]=a[j];
i=j;
j=2*i;
if((j+1)<k)
if(a[j+1]>a[j])
j++;
else
if(j>n)
j=n;
a[i]=value;
}
cout<<"\n";
for(i=1;i<=n;i++)
cout<<" "<<a[i];
}
}
template<class T>
void heap<T>::display(T a[],T n)
{
for(i=1;i<=n;i++)
{
cout<<" "<<a[i];
}
}
void main()
{
heap <int>h;
clrscr();
int a[20],n;
cout<<"\nEnter Value of n:";
cin>>n;
for(int i=1;i<=n;i++)
{
cout<<"\nEnter "<<i<<" Element:";
cin>>a[i];
}
cout<<"\n Original order:\n";;
h.display(a,n);
h.create(a,n);
cout<<"\n heap\n";
h.display(a,n);
h.heaps(a,n);
cout<<"\n after sorting:\n";
h.display(a,n);
getch();
}
Week 10:
write a C++ program to per form the following operation
#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 *rotateright(node *);
node *rotateleft(node *);
node *RRrotation(node *);
node *LLrotation(node *);
node *LRrotation(node *);
node *RLrotation(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,ur;
node *root=NULL;
clrscr();
cout<<"\n\t CREATION OF AVL TREE ";
while(1)
{
cout<<"\n\t1.Create\n\t2.Insert\n\t3.Delete\n\t4.Display\n\t5.Exit ";
cout<<"\nEnter ur choice: ";
cin>>ur;
if(ur==-99)
break;
switch(ur)
{
case 1:
cout<<"\nEnter the number of elements: ";
cin>>n;
cout<<"\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;
case 5:
exit(0);
}
}
getch();
}
node *AVL::insert(node *root,int x)
{
if(root==NULL)
{
root=new node;
root->data=x;
root->left=NULL;
root->right=NULL;
}
else
{
if(x>root->data)
{
root->right=insert(root->right,x);
if(BF(root)<=-2)
{
if(x>root->right->data)
root=RRrotation(root);
else
root=RLrotation(root);
}
}
else if(x<root->data)
{
root->left=insert(root->left,x);
if(BF(root)>=2)
{
if(x<root->left->data)
root=LLrotation(root);
else
root=LRrotation(root);
}
}
}
root->ht=height(root);
return(root);
}
node *AVL::delet(node *root,int x)
{
node *p;
if(root==NULL)
return(0);
else
if(x>root->data)
{
root->right=delet(root->right,x);
if(BF(root)>=2)
if(BF(root->left)>=0)
root=LLrotation(root);
else
root=LRrotation(root);
}
else if(x<root->data)
{
root->left=delet(root->left,x);
if(BF(root)<=-2)
if(BF(root->right)<=0)
root=RRrotation(root);
else
root=RLrotation(root);
}
else
{
if(root->right!=NULL)
{
p=root->right;
while(p->left!=NULL)
p=p->left;
root->data=p->data;
root->right=delet(root->right,p->data);
if(BF(root)>=2)
if(BF(root->left)>=0)
root=LLrotation(root);
else
root=LRrotation(root);
}
else
return(root->left);
}
root->ht=height(root);
return(root);
}
int AVL::height(node *root)
{
int LH,RH;
if(root==NULL)
return(0);
if(root->left==NULL)
LH=0;
else
LH=1+root->left->ht;
if(root->right==NULL)
RH=0;
else
RH=1+root->right->ht;
if(LH>RH)
return (LH);
else
return (RH);
}
int AVL::BF(node *root)
{
int LH,RH;
if(root==NULL)
return(0);
if(root->left==NULL)
LH=0;
else
LH=1+root->left->ht;
if(root->right==NULL)
RH=0;
else
RH=1+root->right->ht;
return(LH-RH);
}
node *AVL::rotateleft(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::rotateright(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::LLrotation(node *root)
{
root=rotateright(root);
return(root);
}
node *AVL::RRrotation(node *root)
{
root=rotateleft(root);
return(root);
}
node *AVL::LRrotation(node *root)
{
root->left=rotateleft(root->left);
root=rotateright(root);
return(root);
}
node *AVL::RLrotation(node *root)
{
root->right=rotateright(root->right);
root=rotateleft(root);
return(root);
}
void AVL::preorder(node *root)
{
if(root!=NULL)
{
cout<<" \n"<<root->data<<" [BF= "<<BF(root)<<"]";
preorder(root->left);
preorder(root->right);
}
}
void AVL::inorder(node *root)
{
if(root!=NULL)
{
inorder(root->left);
cout<<" \n"<<root->data<<" [BF= "<<BF(root)<<"]";
inorder(root->right);
}
}
No comments:
Post a Comment