CPP Program to implement various operations on a BST
#include<iostream.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
//Queue for level order traversal of the tree
class
queue
{private:
struct node
{ int
data;
node *link;
}*front,*rear;
public:
queue();
void addq(int item);
void display();
~queue();
};
queue::queue()
{ front=rear=NULL;}
void
queue::addq(int item)
{ node *temp;
temp=new node;
temp->data=item;
temp->link=NULL;
if(front==NULL)
{ rear=front=temp;
return;
}
rear->link=temp;
rear=rear->link;
}
void
queue::display()
{ node *temp;
for(temp=front;temp!=NULL;temp=temp->link)
cout<<temp->data<<"
";
}
queue::~queue()
{ if(front==NULL)
return;
node *temp;
while(front!=NULL)
{ temp=front;
front=front->link;
delete temp;
}
}
class
BST
{private:
struct tree
{ tree
*left;
tree *right;
int node;
}*start;
public:
BST();
int isnull();
void insert(int);
void preorder(tree *);
void inorder(tree*);
void postorder(tree*);
void levelorder(tree*,queue *);
tree* del(int,tree*);
int height(tree *);
void nodes(tree *,int *);
tree* min(tree *);
int smallest();
tree* max(tree *);
int biggest();
tree* getstart()
{ return
start;}
};
BST::BST()
{ start=NULL;}
BST::isnull()
{ if(start==NULL)
return 1;
else
return 0;
}
void
BST::insert(int ele)
{ tree *p=start,*parentp;
while(p)
{ parentp=p;
if(ele<p->node)
p=p->left;
else
if(ele>p->node)
p=p->right;
else
{ cout<<ele<<"is a duplicate element. Insertion aborted";
return;
}
}
tree *current=new tree;
current->node=ele;
current->right=current->left=NULL;
if(start==NULL)
start=current;
else
if(ele<parentp->node)
parentp->left=current;
else
parentp->right=current;
return;
}
void
BST::preorder(tree *t)
{ if(t!=NULL)
{ cout<<t->node<<" ";
preorder(t->left);
preorder(t->right);
}
return;
}
void
BST::inorder(tree *t)
{ if(t!=NULL)
{
inorder (t->left);
cout<<t->node<<"
";
inorder (t->right);
}
return;
}
void
BST::postorder(tree *t)
{ if(t!=NULL)
{
postorder (t->left);
postorder(t->right);
cout<<t->node<<"
";
}
return;
}
void
BST::levelorder(tree *t,queue *q)
{ if(t==start)q->addq(start->node);
if(t->left!=NULL)
q->addq(t->left->node);
if(t->right!=NULL)
q->addq(t->right->node);
if(t->left!=NULL)
levelorder(t->left,q);
if(t->right!=NULL)
levelorder(t->right,q);
return;
}
tree*
BST::min(tree *t)
{ if(t==NULL)
return NULL;
else
if(t->left==NULL)
return t;
else
min(t->left);
}
tree*
BST::del(int ele,tree *t)
{ if(t==NULL)
cout<<"the element
"<<ele<<"not found in BST\n";
else
if(ele<t->node)
t->left=del(ele,t->left);
else
if(ele>t->node)
t->right=del(ele,t->right);
else
if((t->left)&&(t->right))
{ tree *temp=this->min(t->right);
t->node=temp->node;
t->right=del(t->node,
t->right);
}
else
{ tree *temp=t;
if(t->left==NULL)
t=
t->right;
else
if(t->right==NULL)
t=
t->left;
delete
temp;
}
return t;
}
int
BST::smallest()
{ tree *t=min(start);
return
t->node;
}
tree*
BST::max(tree *t)
{ if(t==NULL)
return NULL;
else
if(t->right==NULL)
return t;
else
max(t->right);
}
int
BST::biggest()
{ tree *t=max(start);
return t->node;
}
void
BST::nodes(tree *t,int *n)
{ if(t!=NULL)
{ *n=*n+1;
nodes(t->left,n);
nodes(t->right,n);
}
}
int
BST::height(tree *t)
{ if(t==NULL) return 0;
int hl=height( t->left);
int hr=height(t->right);
if(hl>hr)
return ++hl;
else
return ++hr;
}
void
main()
{ int c;
BST t;
while(1)
{ clrscr();
cout<<"\nPerform
the following operations on BST";
cout<<"\n---------------------------------------------------------";
cout<<"\n1.Insert
nodes to BST";
cout<<"\n2.Preorder
traversal of BST";
cout<<"\n3.inorder
traversal of BST";
cout<<"\n4.postorder
traversal of BST";
cout<<"\n5.Levelorder
traversal of BST ";
cout<<"\n6.Delete
a node from BST";
cout<<"\n7.Biggest
and smallest elemnt of the BST";
cout<<"\n8.Height
of the BST";
cout<<"\n9.Nodes
in the BST";
cout<<"\n10.Exit
from the program";
do{
cout<<"\nSelect
your choice (1:10)";
cin>>c;
cout<<" ";
}
while((c<1)||(c>10));
if(c==10)exit(1);
switch(c)
{ case 1 :
clrscr();
int element;
char rep;
do
{ cout<<"\nEnter the element to insert ";
cin>>element;
t.insert(element);
cout<<"\nAdd
More(y/n) ";
cin>>rep;
}while((rep=='Y')||(rep=='y'));
break;
case 2:
clrscr();
cout<<"\nThe
result of preorder traversal is \n";
t.preorder(t.getstart());
break;
case 3 :
clrscr();
cout<<"\nThe
result of inorder traversal is \n";
t.inorder(t.getstart());
break;
case 4:
clrscr();
cout<<"\nThe
result of postorder traversal is \n";
t.postorder(t.getstart());
break;
case 5 :
clrscr();
queue s;
cout<<"\nThe
result of levelorder traversal is \n";
t.levelorder(t.getstart(),&s);
s.display();
break;
case 6:
clrscr();
int e;
char r;
do
{
cout<<"\nEnter
the element to delete ";
cin>>e;
t.del(e,t.getstart());
cout<<"\nDelete
More(y/n) ";
cin>>r;
}while((r=='Y')||(r=='y'));
break;
case 7:
clrscr();
cout<<"\nThe smallest element in the BST is "
<<t.smallest()<<" ";
cout<<"\nThe
biggest element in the BST is " <<t.biggest()<<" ";
break;
case 8:
clrscr();
cout<<"\nThe height of the
tree is "
<<t.height(t.getstart())<<" ";
break;
case 9:
clrscr();
int n=0;
t.nodes(t.getstart(),&n);
cout<<"\nThe
number of elements in the tree is "<<n;
break;
}
cout<<endl<<"Press
any key to continue...";
getch();
}
}
No comments:
Post a Comment