Binary Search Tree

PROGRAM:

#include<iostream>

#include<stdlib.h>
#define NULL 0
typedef struct node
{
                int data;
                struct node*left,*right;
}node;

struct node*root=NULL,*t,*temp;

class bst

{
                public:
                struct node *insert(int x,struct node*t)
                {
                                if(t==NULL)
                                {
                                                t=new node;
                                                t->data=x;
                                                t->left=NULL;
                                                t->right=NULL;
                                }
                                else if(x < t->data)
                                                t->left=insert(x,t->left);
                                else if(x > t->data)
                                                t->right=insert(x,t->right);
                                return t;
                }
 
                void create(int x)
                {
                                t=new node;
                                t->data=x;
                                t->left=NULL;
                                t->right=NULL;
                                root=t;
                }
 
                struct node*del(int x,struct node*t)
                {
                                if(t==NULL)
                                                cout<<"Empty Tree"<<endl;
                                if(x < t->data)
                                                t->left=del(x,t->left);
                                else if(x > t->data)
                                                t->right=del(x,t->right);
                                else if((t->left!=NULL)&&(t->right!=NULL))
                                {
                                                temp=findmin(t->right);
                                                t->data=temp->data;
                                                t->right=del(t->data,t->right);
                                }
                                else
                                {
                                                temp=t;
                                                if(t->left==NULL)
                                                                t=t->right;
                                                else if(t->right==NULL)
                                                                t=t->left;
                                                delete(temp);;
                                }
                                return t;
                }
 
                struct node*findmin(struct node*t)
                {
                                if(t!=NULL)
                                {
                                                while(t->left!=NULL)
                                                                t=t->left;
                                }
                                return t;
                }

                void search(int x,struct node*t)

                {
                                temp=t;
                                while((temp!=NULL)&&(temp->data!=x))
                                {
                                                if(x < temp->data)
                                                                temp=temp->left;
                                                else if(x > temp->data)
                                                                temp=temp->right;
                                }
                                if(temp!=NULL)
                                                cout<<"Found"<<endl;
                                else
                                                cout<<"Not Found"<<endl;
                }
 
                void display(struct node*t)
                {
                                if(t!=NULL)
                                {
                                                display(t->left);
                                                cout<<t->data<<endl;
                                                display(t->right);
                                }
                }
};

 

void main()
{
                int ch,x;
                bst b;
                cout<<"Binary Search Tree\n";
                while(1)
                {
                                Cout<<”Operations are:\n”;
                                cout<<"1.insert\n2.delete\n3.display\n4.search\n5.exit\n";
                                cout<<"enter ur option:";
                                cin>>ch;
                                switch(ch)
                                {
                                                case 1:cout<<"Enter the data:";
                                                cin>>x;
                                                if(root==NULL)
                                                {
                                                                b.create(x);
                                                }
                                                else
                                                {
                                                                b.insert(x,root);
                                                }
                                                break;
 
                                                case 2:cout<<"Enter the data to delete:";
                                                cin>>x;
                                                b.del(x,root);
                                                break;
 
                                                case 3:b.display(root);break;
 
                                                case 4:cout<<"Enter the data to be searched:";
                                                cin>>x;
                                                b.search(x,root);
                                                break;
 
                                                case 5:exit(0);

                                                default:cout<<"Invalid option\n";
                                                break;
                                }
                }
}

 

OUTPUT:

Binary Search Tree

Operations are
1. insert
2. delete
3. display
4. search
5. exit
Enter ur option:1
Enter the data:10

Operations are

1. insert
2. delete
3. display
4. search
5. exit
Enter ur option:1
Enter the data: 20

Operations are

1. insert
2. delete
3. display
4. search
5. exit
Enter ur option:1
Enter the data: 30

Operations are

1. insert
2. delete
3. display
4. search
5. exit
Enter ur option:3
10
20
30
 
Operations are
1. insert
2. delete
3. display
4. search
5. exit
Enter ur option:4
Enter the data to be searched:50
Not Found

Operations are

1. insert
2. delete
3. display
4. search
5. exit
Enter ur option:2
Enter the data to be deleted: 20
 
Operations are
1. insert
2. delete
3. display
4. search
5. exit
Enter ur option:3
10
30
 
Operations are
1. insert
2. delete
3. display
4. search
5. exit
Enter ur option:5