My teacher gave us an assignment to code Binary Search Tree . Most of the part is done but I am having trouble with mirror image of binary tree. Teacher told us that we should create a mirror image without altering the original tree. I tried to create it but code also modifies original BST as shown in my output below. I am not getting where it is going wrong. Any help would be appreciated.
My code:
#include<iostream>
using namespace std;
struct node
{
int data;
node *left,*right;
};
class BST
{
node *root,*root1;
public:
int ch;
BST(){ root=NULL; ch=0; }
void create();
void insert(node*,node*);
void disin();
void inorder(node*);
void dispre();
void preorder(node*);
void dispost();
void postporder(node*);
void search();
node* actualsearch(node*,int);
void min();
void max();
void actmin(node*);
void actmax(node*);
void height();
int actheight(node*);
void mirror();
void actmirror(node*);
};
int main()
{
int cho;
BST b;
char choice;
do {
cout<<"\nEnter Your Choice = ";
cout<<"\n1.Insert";
cout<<"\n2.Inorder Traversal";
cout<<"\n3.Preorder Traversal";
cout<<"\n4.Postorder Traversal";
cout<<"\n5.Search an element in tree";
cout<<"\n6.Find Maximum element in tree";
cout<<"\n7.Find Minimum elemnt in tree";
cout<<"\n8.Total No Of Nodes In Longest Path";
cout<<"\n9.Mirror Image = ";
cin>>cho;
switch(cho)
{
case 1:
b.create();
break;
case 2:
cout<<"---------------------------------------------------";
cout<<"\nInorder Treaversal = "<<endl;
b.disin();
cout<<"\n---------------------------------------------------";
break;
case 3:
cout<<"---------------------------------------------------";
cout<<"\nPreorder Treaversal = "<<endl;
b.dispre();
cout<<"\n---------------------------------------------------";
break;
case 4:
cout<<"---------------------------------------------------";
cout<<"\nPostorder Treaversal = "<<endl;
b.dispost();
cout<<"\n---------------------------------------------------";
break;
case 5:
b.search();
cout<<"\n---------------------------------------------------";
break;
case 6:
b.max();
cout<<"\n---------------------------------------------------";
break;
case 7:
b.min();
cout<<"\n---------------------------------------------------";
break;
case 8:
b.height();
cout<<"\n---------------------------------------------------";
break;
case 9:
b.mirror();
cout<<"\n---------------------------------------------------";
break;
}
cout<<"\nDo you want to continue opreations(y/n) = ";
cin>>choice;
}while(choice=='y'||choice=='Y');
return 0;
}
void BST::search()
{
int n;
cout<<"\nEnter element you want to search = ";
cin>>n;
if(root!=NULL)
actualsearch(root,n);
else
cout<<"Tree is empty"<<endl;
}
node* BST::actualsearch(node *current,int n)
{
int dfcount=0;
while(current)
{
if(current->data==n)
{
cout<<"Data Found"<<endl;
dfcount++;
break;
}
else if(n>current->data)
{
current=current->right;
}
else if(n<current->data)
{
current=current->left;
}
}
if(dfcount==0)
cout<<"Data not found!"<<endl;
return NULL;
}
void BST::create()
{
char ans;
node *temp;
do
{
temp=new node;
temp->left=temp->right=NULL;
cout<<"\nEnter no you want to insert = ";
cin>>temp->data;
if(root==NULL)
{
root=temp;
}
else
{
insert(root,temp);
}
cout<<"\nDo You want to continue to insert data(y/n) = ";
cin>>ans;
}while(ans=='y'||ans=='Y');
}
void BST::insert(node *current,node *temp)
{
if(temp->data==current->data)
cout<<"\nDo not add";
else if(temp->data<current->data)
{
if(current->left==NULL)
current->left=temp;
else
insert(current->left,temp);
}
else if(temp->data>current->data)
{
if(current->right==NULL)
current->right=temp;
else
insert(current->right,temp);
}
}
void BST::disin()
{
inorder(root);
}
void BST::inorder(node *T)
{
if(T!=NULL)
{
inorder(T->left);
cout<<T->data<<" ";
inorder(T->right);
}
}
void BST::dispre()
{
preorder(root);
}
void BST::preorder(node *T)
{
if(T!=NULL)
{
cout<<T->data<<" ";
preorder(T->left);
preorder(T->right);
}
}
void BST::dispost()
{
postporder(root);
}
void BST::postporder(node *T)
{
if(T!=NULL)
{
postporder(T->left);
postporder(T->right);
cout<<T->data<<" ";
}
}
void BST::max()
{
if(root!=NULL)
{
actmax(root);
}
}
void BST::min()
{
if(root!=NULL)
{
actmin(root);
}
}
void BST::actmax(node* current)
{
while(current->right!=NULL)
{
current=current->right;
}
cout<<"Largest Number is :"<<current->data<<endl;
}
void BST::actmin(node* current)
{
while(current->left!=NULL)
{
current=current->left;
}
cout<<"Smallest Number is :"<<current->data<<endl;
}
void BST::height()
{
int i=actheight(root);
cout<<"Total No Of Nodes In Longest Path is:"<<i<<endl;
}
int BST::actheight(node* current)
{
if(current==NULL)
{
return 0;
}
else
{
int lh = actheight(current->left);
int rh = actheight(current->right);
if (lh > rh)
return(lh+1);
else return(rh+1);
}
}
void BST::mirror()
{ root1=root;
actmirror(root1);
cout<<"Mirror Image of given tree is Created!"<<endl;
cout<<"\nInorder Travesral Is = "<<endl;
inorder(root1);
cout<<"\nPreorder Travesral Is = "<<endl;
preorder(root1);
cout<<"\nPostorder Travesral Is = "<<endl;
postporder(root1);
}
void BST::actmirror(node* current)
{
node* holder=new node;
if(current==NULL)
{
return ;
}
holder=current->left;
current->left=current->right;
current->right=holder;
actmirror(current->left);
actmirror(current->right);
}
Its output:
Enter Your Choice =
1.Insert
2.Inorder Traversal
3.Preorder Traversal
4.Postorder Traversal
5.Search an element in tree
6.Find Maximum element in tree
7.Find Minimum elemnt in tree
8.Total No Of Nodes In Longest Path
9.Mirror Image = 1
Enter no you want to insert = 5
Do You want to continue to insert data(y/n) = y
Enter no you want to insert = 6
Do You want to continue to insert data(y/n) = y
Enter no you want to insert = 7
Do You want to continue to insert data(y/n) = y
Enter no you want to insert = 2
Do You want to continue to insert data(y/n) = y
Enter no you want to insert = 3
Do You want to continue to insert data(y/n) = n
Do you want to continue opreations(y/n) = y
Enter Your Choice =
1.Insert
2.Inorder Traversal
3.Preorder Traversal
4.Postorder Traversal
5.Search an element in tree
6.Find Maximum element in tree
7.Find Minimum elemnt in tree
8.Total No Of Nodes In Longest Path
9.Mirror Image = 2
---------------------------------------------------
Inorder Treaversal =
2 3 5 6 7
---------------------------------------------------
Do you want to continue opreations(y/n) = y
Enter Your Choice =
1.Insert
2.Inorder Traversal
3.Preorder Traversal
4.Postorder Traversal
5.Search an element in tree
6.Find Maximum element in tree
7.Find Minimum elemnt in tree
8.Total No Of Nodes In Longest Path
9.Mirror Image = 9
Mirror Image of given tree is Created!
Inorder Travesral Is =
7 6 5 3 2
Preorder Travesral Is =
5 6 7 2 3
Postorder Travesral Is =
7 6 3 2 5
---------------------------------------------------
Do you want to continue opreations(y/n) = y
Enter Your Choice =
1.Insert
2.Inorder Traversal
3.Preorder Traversal
4.Postorder Traversal
5.Search an element in tree
6.Find Maximum element in tree
7.Find Minimum elemnt in tree
8.Total No Of Nodes In Longest Path
9.Mirror Image = 2
---------------------------------------------------
Inorder Treaversal =
7 6 5 3 2
---------------------------------------------------
Do you want to continue opreations(y/n) = n
--------------------------------
Process exited after 41 seconds with return value 0
Press any key to continue . . .
Here you can see that even though I used normal Inorder Traversal It doesn't show traversal of original BST rather it shows mirror BST's Traversal.
