Program for Binary Search Tree in C++

Program for Binary Search Tree in C++

#include"iostream"
#include<string.h>
using namespace std;

class node
{
public:
int data;
class node  *left;
class node * right;
};

class dict
{
public:
node *root;
void create();
void disp_asc(node *);
void insert(node * root,node *temp);
int search(node *,int);
node* del(node *,int);
node * min(node *);
};

void dict :: create()
{
class node *temp;
int ch;

do
{
temp = new node;
cout<<"\nEnter Data:";
cin>>temp->data;

temp->left = NULL;
temp->right = NULL;

if(root == NULL)
{
root = temp;
}
else
{
insert(root, temp);
}
cout<<"\nDo u want to add more (y=1/n=0):";
cin>>ch;
}
while(ch == 1);

}

void dict ::  insert(node * root,node *temp)
{
if(temp->data < root->data)
{
if(root->left == NULL)
root->left = temp;
else
insert(root->left,temp);
}
else
{
if(root->right == NULL)
root->right = temp;
else
insert(root->right,temp);
}

}

void dict:: disp_asc(node * root)
{
if( root != NULL)
{
disp_asc(root->left);
cout<<"\n Data :"<<root->data;

disp_asc(root->right);
}
}

int dict :: search(node * root,int k)
{
int c=0;
while(root != NULL)
{
c++;
if(k == root->data)
{
cout<<"\nNo of Comparisons:"<<c;
return 1;
}
if(k < root->data)
root = root->left;
if(k > root->data)
root = root->right;
}

return -1;
}
node* dict :: del(node * root,int k)
{
node *temp;

if(root == NULL)
{
cout<<"\nElement No Found";
return root;
}

if (k < root->data)
{
root->left = del(root->left, k);
return root;
}
if (k > root->data)
{
root->right = del(root->right, k);
return root;
}

if (root->right==NULL&&root->left==NULL)
{
temp = root;
delete temp;
return NULL;
}
if(root->right==NULL)
{
temp = root;
root = root->left;
delete temp;
return root;
}
else if(root->left==NULL)
{
temp = root;
root = root->right;
delete temp;
return root;
}
temp = min(root->right);
root->data=temp->data;
root->right = del(root->right, temp->data);
return root;
}

node * dict :: min(node *q)
{
while(q->left != NULL)
{
q = q->left;
}
return q;
}



int main()
{
int ch;
int k;
dict d;
d.root = NULL;
do
{
cout<<"\n \t \t \t \t MENU ";
cout<<"\n \t \t \t \t ==== ";

cout<<"\n1.Create Tree \n2.Display Tree \n3.Search Data \n4.Delete Data \nEnter your choice:";
cin>>ch;

switch(ch)
{
case 1: d.create();
break;
case 2: if(d.root == NULL)
{
cout<<"\nNo any data";
}
else
{
d.disp_asc(d.root);
}
break;
case 3:
if(d.root == NULL)
{
cout<<"\nTree is Empty. First add data then try again ";
}
else
{
cout<<"\nEnter data which u want to search:";
cin>>k;
if( d.search(d.root,k) == 1)
cout<<"\nData Found";
else
cout<<"\nData Not Found";
}
break;
case 4:
if(d.root == NULL)
{
cout<<"\nTree is Empty. First add data then try again ";
}
else
{
cout<<"\nEnter data which u want to delete:";
cin>>k;
if(d.root == NULL)
{
cout<<"\nNo any data";
}
else
{
d.root = d.del(d.root,k);
}
}
}
}
while(ch<=5);
return 0;
}


Output:


  MENU 
  ==== 
1.Create Tree 
2.Display Tree 
3.Search Data 
4.Delete Data 
Enter your choice:1

Enter Data:40

Do u want to add more (y=1/n=0):1

Enter Data:13

Do u want to add more (y=1/n=0):1

Enter Data:50

Do u want to add more (y=1/n=0):1

Enter Data:5

Do u want to add more (y=1/n=0):0

  MENU 
  ==== 
1.Create Tree 
2.Display Tree 
3.Search Data 
4.Delete Data 
Enter your choice:2

 Data :5
 Data :13
 Data :40
 Data :50
  MENU 
  ==== 
1.Create Tree 
2.Display Tree 
3.Search Data 
4.Delete Data 
Enter your choice:3

Enter data which u want to search:5

No of Comparisons:3
Data Found
  MENU 
  ==== 
1.Create Tree 
2.Display Tree 
3.Search Data 
4.Delete Data 
Enter your choice:4

Enter data which u want to delete:40

  MENU 
  ==== 
1.Create Tree 
2.Display Tree 
3.Search Data 
4.Delete Data 
Enter your choice:2

 Data :5
 Data :13
 Data :50
  MENU 
  ==== 
1.Create Tree 
2.Display Tree 
3.Search Data 
4.Delete Data 
Enter your choice: