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

Postfix Evaluation

$$$ POSTFIX EVALUATION $$$

PROGRAM:

#include<iostream>

#include<string.h>

int stack[20],top=-1;

int len,a,b,c,i,x;

char expr[20];

class postfix

{

      public:

      void evaluate()

      {

            len=strlen(expr);

            for(i=0;i<len;i++)

            {

                  if(expr[i]=='+'||expr[i]=='-'||expr[i]=='*'||expr[i]=='/')

                  {

                        b=pop();

                        a=pop();

                        switch(expr[i])

                        {

                              case '+':c=a+b;

                              push(c);

                              break;

                              case '-':c=a-b;

                              push(c);

                              break;

                              case '*':c=a*b;

                              push(c);

                              break;

                              case '/':c=a/b;

                              push(c);

                              break;

                        }

                  }

                  else

                  {

                        cout<<"Enter the value of"<<expr[i]<<":";

                        cin>>x;

                        push(x);

                  }

            }

      }

      void push(int item)

      {

            stack[++top]=item;

      }

      int pop()

      {

            int a;

            a=stack[top];

            top=top-1;

            return a;

      }

};

void main()

{

      postfix p;

      cout<<"$$$ POSTFIX EVALUATION $$$";

      cout<<"\nEnter the postfix expression:";

      cin>>expr;

      p.evaluate();

      cout<<"The resultant value is :"<<stack[top];

}

OUTPUT:

$$$ POSTFIX EVALUATION $$$

Enter the postfix expression: abc+*
Enter the value of a: 10
Enter the value of b: 20
Enter the value of c: 30
The resultant value is : 500

Infix to Postfix Conversion

$$$         Infix to Postfix Conversion           $$$

PROGRAM:

#include<iostream>

#include<string.h>

#include<ctype.h>

#define SIZE 50

char s[SIZE],infix[50],postfix[50],ch,item;

int i=0,k=0,len,top=-1;

class itop

{

      public:

      int convert()

      {

            push('#');

            len=strlen(infix);

            for(i=0;i<len;i++)

            {

                  ch=infix[i];

                  if(isalnum(ch))

                  {

                        postfix[k]=ch;

                        k++;

                  }

                  else if(ch=='(')

                  {

                        push(ch);

                  }

                  else if(ch==')')

                  {

                        while(s[top]!='(')

                        {

                              postfix[k]=pop();

                              k++;

                        }

                        item=pop();

                  }

                  else

                  {

                        while(priority(s[top])>=priority(ch))

                        {

                              postfix[k]=pop();

                              k++;

                        }

                        push(ch);

                  }

            }

            while(s[top]!='#')

            {

                  postfix[k]=pop();

                  k++;

            }

            postfix[k]='\0';

      }

      void push(char a)

      {

            top=top+1;

            s[top]=a;

      }

      char pop()

      {

            char a;

            a=s[top];

            top=top-1;

            return a;

      }

      int priority(char a)

      {

            switch(a)

            {

                  case '#':return 0;

                  case '(':return 1;

                  case '+':return 2;

                  case '-':return 2;

                  case '*':return 3;

                  case '/':return 3;

                  case '^':return 4;

            }

      }

};

void main()

{

      itop ip;

      cout<<"\n\n $$$ INFIX TO POSTFIX CONVERSION $$$ \n\n";

      cout<<"Enter infix expression:\t";

      cin>>infix;

      ip.convert();

      cout<<"Postfix expression is:"<<postfix;

}

OUTPUT:

$$$ INFIX TO POSTFIX CONVERSION $$$

Enter infix expression: (A+B^C)*D+E^5

Postfix expression is: ABC^+D*E5^+

Merge Sort

$$$       MERGE SORT        $$$

PROGRAM:

#include<iostream>

int a[20],temp[20],i,n;

class mergesorting

{

public:

void getdata()

{

      cout<<"\nEnter the array limit:";

      cin>>n;

      cout<<"Enter array elements:";

      for(i=0;i<n;i++)

      {

            cin>>a[i];

      }

}

void mergesort(int a[],int temp[],int n)

{

      msort(a,temp,0,n-1);

}

void msort(int a[],int temp[],int left,int right)

{

      int center;

      if(left<right)

      {

            center=(left+right)/2;

            msort(a,temp,left,center);

            msort(a,temp,center+1,right);

            merge(a,temp,left,center+1,right);

      }

}

void merge(int a[],int temp[],int left,int center,int right)

{

      int i,left_end,num_elements,tmp_pos;

      left_end=center-1;

      tmp_pos=left;

      num_elements=right-left+1;

      while((left<=left_end)&&(center<=right))

      {

            if(a[left]<=a[center])

            {

                  temp[tmp_pos]=a[left];

                  tmp_pos++;

                  left++;

            }

            else

            {

                  temp[tmp_pos]=a[center];

                  tmp_pos++;

                  center++;

            }

      }

      while(left<=left_end)

      {

            temp[tmp_pos]=a[left];

            left++;

            tmp_pos++;

      }

      while(center<=right)

      {

            temp[tmp_pos]=a[center];

            center++;

            tmp_pos++;

      }

      for(i=0;i<=num_elements;i++)

      {

            a[right]=temp[right];

            right--;

      }

}

void putdata()

{

      cout<<"The Sorted elements are:\t";

      for(i=0;i<n;i++)

      {

            cout<<a[i]<<"\t";

      }

}

};

void main()

{

            mergesorting ms;

            cout<<"$$$ MERGE SORT $$$";

            ms.getdata();

            ms.mergesort(a,temp,n);

            ms.putdata();

}

OUTPUT:

$$$ MERGE SORT $$$

Enter the array limit:       8
Enter array elements:    40           20           70           14           60           61           97           30
The Sorted elements are:            14           20           30           40           60           61           70           97