1.BST_operations

File: /home/saiesh/ADS/Assignment No 1/ads1.cpp
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct node
{
int data;
node *left,*right;
}bstnode;
bstnode *root;
class BST
{
public:
BST()
{
root=NULL;
}
bstnode *getnode();
void create();
int maxdepth(bstnode *root);
void min(bstnode *T);
void change(bstnode *root);
bstnode *find(int x);
void inorder(bstnode *T);
};
bstnode *BST::getnode()
{
bstnode *temp;
temp=new bstnode;
cout<<"\nEnter the data:\t";
cin>>temp->data;
temp->left=temp->right=NULL;
return temp;
}
void BST::create()
{
char ans;
bstnode *temp,*ptr;
do
{
temp=getnode();
if(root==NULL)
root=temp;
else
{
ptr=root;
while(1)
{
if(temp->data<ptr->data)
{
if(ptr->left==NULL)
{
ptr->left=temp;
break;
}
else
ptr=ptr->left;
}
else
{
if(ptr->right==NULL)
{
ptr->right=temp;
Page 1 of 6File: /home/saiesh/ADS/Assignment No 1/ads1.cpp
Page 2 of 6
break;
}
else
ptr=ptr->right;
}
}
}
cout<<"Do you want to add more nodes? ";
cin>>ans;
} while(ans=='y'||ans=='Y');
}
int BST::maxdepth(bstnode *root)
{
if(root==NULL)
return 0;
else
{
int ldepth=maxdepth(root->left);
int rdepth=maxdepth(root->right);
if(ldepth>rdepth)
return(ldepth+1);
else
return(rdepth+1);
}
}
void BST::min(bstnode *T)
{
bstnode *ptr;
if(root==NULL)
cout<<"\nTree is empty!";
else
{
ptr=root;
while(1)
{
if(ptr->left==NULL)
{
cout<<"\nThe minimum node is:\t"<<ptr->data;
break;
}
else
ptr=ptr->left;
}
}
}
void BST::change(bstnode *root)
{
bstnode *s;
if(root==NULL)
return;
else
{
s=root->left;
root->left=root->right;
root->right=s;
change(root->left);
change(root->right);
}
}
bstnode *BST::find(int x)
{
bstnode *ptr;File: /home/saiesh/ADS/Assignment No 1/ads1.cpp
Page 3 of 6
ptr=root;
while(ptr!=NULL)
{
if(x==ptr->data)
return ptr;
else if(x<ptr->data)
ptr=ptr->left;
else
ptr=ptr->right;
}
return NULL;
}
void BST::inorder(bstnode *T)
{
if(T!=NULL)
{
inorder(T->left);
cout<<"
"<<T->data;
inorder(T->right);
}
}
int main()
{
bstnode *R,*S;
BST obj;
char ans;
int ch;
do
{
cout<<"\n\t\t\tBinary Search Tree";
cout<<"\n\t\t\t\tMENU";
cout<<"\n1.Insert new node";
cout<<"\n2.Find number of nodes in the longest path";
cout<<"\n3.Minimum data found in tree";
cout<<"\n4.Search a value";
cout<<"\n5.Change a tree so that the roles of the left and right
pointers are swapped at every node";
cout<<"\n6.Exit";
cout<<"\nEnter your choice:\t";
cin>>ch;
switch(ch)
{
case 1: obj.create();
cout<<"\nTree nodes are: ";
obj.inorder(root);
break;
case 2: int a;
a=obj.maxdepth(root);
cout<<"\nNumber of nodes in the longest path:
\t"<<a;
break;
case 3: obj.min(root);
break;
case 4: int a;
cout<<"\nEnter the node you want to search:\t";
cin>>a;
R=obj.find(a);
if(R==NULL)
cout<<"\nNumber not found!";
else
cout<<"\nNumber found!";File: /home/saiesh/ADS/Assignment No 1/ads1.cpp
Page 4 of 6
break;
case 5: obj.change(root);
cout<<"\nAfter roles of the left and right
pointers are swapped at every node: ";
obj.inorder(root);
break;
case 6: exit(0);
}
cout<<"\nDo you want to continue? ";
cin>>ans;
} while(ans=='y'||ans=='Y');
return 0;
}
/*
OUTPUT
saiesh@saiesh :~$ g++ ads1.cpp
saiesh@saiesh :~$ ./a.out
Binary Search Tree
MENU
1.Insert new node
2.Find number of nodes in the longest path
3.Minimum data found in tree
4.Search a value
5.Change a tree so that the roles of the left and right pointers are swapped at
every node
6.Exit
Enter your choice:
1
Enter the data: 7
Do you want to add more nodes? y
Enter the data: 2
Do you want to add more nodes? y
Enter the data: 9
Do you want to add more nodes? y
Enter the data: 0
Do you want to add more nodes? y
Enter the data: 5
Do you want to add more nodes? y
Enter the data: 6
Do you want to add more nodes? y
Enter the data: 8
Do you want to add more nodes? y
Enter the data: 1
Do you want to add more nodes? n
Tree nodes are:
0
1
2
Do you want to continue? y
5
6
7
8
9
Binary Search Tree
MENU
1.Insert new node
2.Find number of nodes in the longest path
3.Minimum data found in tree
4.Search a value
5.Change a tree so that the roles of the left and right pointers are swapped atFile: /home/saiesh/ADS/Assignment No 1/ads1.cpp
every node
6.Exit
Enter your choice:
Page 5 of 6
2
Number of nodes in the longest path:
Do you want to continue? y
4
Binary Search Tree
MENU
1.Insert new node
2.Find number of nodes in the longest path
3.Minimum data found in tree
4.Search a value
5.Change a tree so that the roles of the left and right pointers are swapped at
every node
6.Exit
Enter your choice:
3
The minimum node is:
0
Do you want to continue? y
Binary Search Tree
MENU
1.Insert new node
2.Find number of nodes in the longest path
3.Minimum data found in tree
4.Search a value
5.Change a tree so that the roles of the left and right pointers are swapped at
every node
6.Exit
Enter your choice:
4
Enter the node you want to search:
1
Number found!
Do you want to continue? y
Binary Search Tree
MENU
1.Insert new node
2.Find number of nodes in the longest path
3.Minimum data found in tree
4.Search a value
5.Change a tree so that the roles of the left and right pointers are swapped at
every node
6.Exit
Enter your choice:
4
Enter the node you want to search:
4
Number not found!
Do you want to continue? y
Binary Search Tree
MENU
1.Insert new node
2.Find number of nodes in the longest path
3.Minimum data found in tree
4.Search a value
5.Change a tree so that the roles of the left and right pointers are swapped at
every node
6.Exit
Enter your choice:
5
After roles of the left and right pointers are swapped at every node:
7
6
5
2
1
0
9
8File: /home/saiesh/ADS/Assignment No 1/ads1.cpp
Page 6 of 6
Do you want to continue? y
Binary Search Tree
MENU
1.Insert new node
2.Find number of nodes in the longest path
3.Minimum data found in tree
4.Search a value
5.Change a tree so that the roles of the left and right pointers are swapped at
every node
6.Exit
Enter your choice:
6
saiesh@saiesh :~$ */