#include<iostream>
using namespace std;
struct node{
int info;
node *left,*right;
}*root=NULL;
struct Queue{
node* data;
Queue *link;
}*front=NULL,*rear=NULL;
void AddNode(int item)
{
node *temp=new node;
temp->info=item;
temp->left=NULL;
temp->right=NULL;
if(root==NULL)
{
root=temp;
}
else
{
node *ptr1=NULL;
node *ptr=root;
while(ptr!=NULL)
{
ptr1=ptr;
if(ptr->info<item)
{
ptr=ptr->right;
}
else
{
ptr=ptr->left;
}
}
if(ptr1->info<item)
{
ptr1->right=temp;
}
else
{
ptr1->left=temp;
}
}
}
void Inorder(node *root)
{
if(root!=NULL)
{
Inorder(root->left);
cout<<root->info<<"t";
Inorder(root->right);
}
}
void Preorder(node *root)
{
if(root!=NULL)
{
cout<<root->info<<"t";
Preorder(root->left);
Preorder(root->right);
}
}
void Postorder(node *root)
{
if(root!=NULL)
{
Postorder(root->left);
Postorder(root->right);
cout<<root->info<<"t";
}
}
void Insert(node* item)
{
Queue *ptrr=new Queue;
ptrr->data=item;
ptrr->link=NULL;
if(front==NULL)
{
front=rear=ptrr;
}
else
{
rear->link=ptrr;
rear=ptrr;
}
}
node* Delete()
{
node* item=front->data;
if(front!=NULL)
{
front=front->link;
return item;
}
else
{
return 0;
}
}
int Levelorder(node *root)//level oreder traversal
{
node *t=root;
if(!t)
{
return 0;
}
Insert(t);
while(front!=NULL)
{
t=Delete();
cout<<t->info<<"t";
if(t->left)
{
Insert(t->left);
}
if(t->right)
{
Insert(t->right);
}
}
}
void search(node *root,int item)
{
node *temp=root;
if(temp==NULL)
{
cout<<"nthere is no element in the treen";
}
else
{
while(temp)
{
if(temp->info==item)
{
cout<<"nitem is available in the treen";
break;
}
else if(temp->info<item)
{
temp=temp->right;
}
else
{
temp=temp->left;
}
if(temp==NULL)
{
cout<<"nItem is not available in the treen";
}
}
}
}
void Del(int item)
{
node *ptr,*par;
node *par_replacement,*replacement;
node *childptr;
par=NULL;
ptr=root;
int is_left=0;
while(ptr!=NULL)
{
if(item==ptr->info)
{
break;
}
else if(item<ptr->info)
{
par=ptr;
is_left=1;
ptr=ptr->left;
}
else
{
par=ptr;
is_left=0;
ptr=ptr->right;
}
}
if(ptr==NULL)
{
cout<<"nnode with value "<<item<<" does not exist in the treen";
}
else if((ptr->left==NULL)&&(ptr->right==NULL))
{
if(par==NULL)
{
free(root);
}
else
{
free(ptr);
if(is_left)
{
par->left=NULL;
}
else
{
par->right=NULL;
}
}
}
else if((ptr->right==NULL)||(ptr->left==NULL))
{
if(ptr->left!=NULL)
{
childptr=ptr->left;
}
else
{
childptr=ptr->right;
}
if(par==NULL)
{
root=childptr;
free(ptr);
}
else
{
if(is_left)
{
par->left=childptr;
}
else
{
par->right=childptr;
}
free(ptr);
}
}
else
{
par_replacement=ptr;
replacement=ptr->left;
is_left=1;
while(replacement->right!=NULL)
{
par_replacement=replacement;
replacement=replacement->right;
is_left=0;
}
ptr->info=replacement->info;
if(is_left)
{
ptr->left=replacement->left;
free(replacement);
}
else
{
par_replacement->right=replacement->left;
free(replacement);
}
}
}
int main()
{
int item,choice;
while(1)
{
cout<<"n1. Add a Valuen2. Inorder Traversaln3. Preorder Traversaln4. Postorder Traversaln";
cout<<"5. Levelorder Traversaln6. Find Elemetsn7. Deleten8. Exitn";
cout<<"nEnter Your Choice";
cin>>choice;
switch(choice)
{
case 1:
cout<<"nENter the value to be addedd";
cin>>item;
AddNode(item);
break;
case 2:
Inorder(root);
cout<<"n";
break;
case 3:
Preorder(root);
cout<<"n";
break;
case 4:
Postorder(root);
cout<<"n";
break;
case 5:
Levelorder(root);
cout<<"n";
break;
case 6:
cout<<"Enter the number to be searched";
cin>>item;
search(root,item);
break;
case 7:
cout<<"Enter the element you want to delete";
cin>>item;
Del(item);
break;
case 8:
exit(0);
}
}
return 0;
}
0 Comments