Re: Post ur C/C++ Programs Here
//Program to perform operations on a binary search tree
#include<iostream.h>
#include<conio.h>
struct node
{
int data;
node *left;
node *right;
};
class bstree
{
private:
node *root;
public:
bstree()
{
root=NULL;
}
~bstree()
{
cout<<"\nDestructor called\n";
inorder_destroy(root);
}
node* search(int,node*&)const;
void insert(int);
void del(int);
void traverse()const;
void inorder(node*)const;
void preorder(node*)const;
void postorder(node*)const;
void inorder_destroy(node*);
};
node* bstree::search(int item,node *&parent)const
{
node *ptr=NULL;
parent=NULL;
if(root!=NULL)
{
ptr=root;
parent=NULL;
while(ptr!=NULL)
{
if(item==ptr->data)
return ptr;
parent=ptr;
if(item<ptr->data)
ptr=ptr->left;
else
ptr=ptr->right;
}
}
return ptr;
}
void bstree::insert(int item)
{
node *parent;
if(search(item,parent)!=NULL)
{
cout<<"\nSuch a node already exists\n";
getch();
return;
}
node *temp=new node;
temp->data=item;
temp->left=NULL;
temp->right=NULL;
if(parent==NULL)
{
root=temp;
return;
}
if(item<parent->data)
parent->left=temp;
else
parent->right=temp;
}
void bstree::traverse()const
{
if(root==NULL)
{
cout<<"\nTree empty\n";
getch();
return;
}
cout<<"\nInorder\n\n";
inorder(root);
cout<<"\nPreorder\n\n";
preorder(root);
cout<<"\nPostorder\n\n";
postorder(root);
getch();
}
void bstree::inorder(node *n)const
{
if(n!=NULL)
{
inorder(n->left);
cout<<n->data<<"\t";
inorder(n->right);
}
}
void bstree:
reorder(node *n)const
{
if(n!=NULL)
{
cout<<n->data<<"\t";
preorder(n->left);
preorder(n->right);
}
}
void bstree:
ostorder(node *n)const
{
if(n!=NULL)
{
postorder(n->left);
postorder(n->right);
cout<<n->data<<"\t";
}
}
void bstree::del(int item)
{
node *parent;
if(root==NULL)
{
cout<<"\nTree empty\n";
getch();
return;
}
node *loc=search(item,parent);
if(loc==NULL)
{
cout<<"\nNode not found\n";
getch();
return;
}
node *ptr=NULL;
if(loc->left!=NULL && loc->right!=NULL)
{
ptr=loc->right;
parent=loc;
while(ptr->left!=NULL)
{
parent=ptr;
ptr=ptr->left;
}
loc->data=ptr->data;
loc=ptr;
}
if(loc->left==NULL)
ptr=loc->right;
else if(loc->right==NULL)
ptr=loc->left;
if(parent==NULL)
root=ptr;
else if(loc==parent->left)
parent->left=ptr;
else
parent->right=ptr;
delete loc;
cout<<"\nNode Deleted\n";
getch();
}
void bstree::inorder_destroy(node *r)
{
if(r!=NULL)
{
inorder_destroy(r->left);
del(r->data);
inorder_destroy(r->right);
}
}
int main()
{
bstree b;
int choice,flag=1,item;
while(flag)
{
clrscr();
cout<<"\n\t\t\t1-Insert";
cout<<"\n\t\t\t2-Delete";
cout<<"\n\t\t\t3-Traverse";
cout<<"\n\t\t\t4-Exit";
cout<<"\n\tEnter your choice:-";
cin>>choice;
switch(choice)
{
case 1:
cout<<"\nEnter the item to insert ";
cin>>item;
b.insert(item);
break;
case 2:
cout<<"\nEnter the item to delete ";
cin>>item;
b.del(item);
break;
case 3:
b.traverse();
break;
case 4:
flag=0;
break;
default:
continue;
}
}
getch();
return 0;
}