Binary Search Tree Operations Using c

/*
In This Binary Search Tree Operations We Do
=>  Insert Element
=> Delete Element
=>  Find Maximum Element
=> Find Minimum Element
=> Search Element
*/

#include<stdio.h>

#include<conio.h>

#include<alloc.h>

#include<math.h>

#include<time.h>

#define Max 20

struct Node

{

       int val;

       struct Node *lptr;

       struct Node *rptr;

};

int SearchNode(struct Node* n, int x);

struct Node* InsertIntoTree(struct Node* n, int x);

struct Node* DeleteFromTree(struct Node* n, int x);

struct Node* SearchMaxElement(struct Node *n);

struct Node* SearchMinElement(struct Node *n);

void InOrderTraversal(struct Node* n);

void PostOrderTraversal(struct Node* n);

void PreOrderTraversal(struct Node* n);

void main()

{

       struct Node *n=NULL;

       struct Node *Min_Max_Value;

       int i,j,Temp_Val,Flag=1;

       char ch;

       float Traverse_Time;

       clock_t first,second;

       do

       {

        printf("\nMenu....");

        printf("\n1. Insert Element \n2. Delete Element \n3. Find Maximum \n4. Find Minimum \n5. Search Element");

        printf("\n6. InOrder Traversal \n7. PreOrder Traversal \n8. Post Order Traversal \n9. Exit");

        printf("\nEnter Choice : ");

        scanf("%d",&ch);

        clrscr();

        switch(ch)

        {

              case 1:  printf("\nEnter Element to be Inserted : ");

                           scanf("%d",&Temp_Val);

                           n = InsertIntoTree(n,Temp_Val);

                            printf("\nElement Inserted");

                            break;

               case 2: first = clock();

                           printf("\nEnter Element to be deleted : ");

                           scanf("%d",&Temp_Val);

                           n = DeleteFromTree(n,Temp_Val);

                           InOrderTraversal(n);

                           printf("\nElement Deleted");

                           second = clock();

                           Traverse_Time = (second-first)/CLOCKS_PER_SEC;

                           printf("\nTime To Delete Element is %f",Traverse_Time);

                           break;

                case 3: first = clock();

                            Min_Max_Value = SearchMaxElement(n);

                            printf("\nMaximum Element in Tree : %d",Min_Max_Value->val);

                            second = clock();

                            Traverse_Time = (second-first)/CLOCKS_PER_SEC;

                            printf("\nTime To Find Max Element is %f",Traverse_Time);

                            break;

                 case 4: first = clock();

                             Min_Max_Value = SearchMinElement(n);

                             printf("\nMinimum Element in Tree : %d",Min_Max_Value->val);

                             second = clock();

                             Traverse_Time = (second-first)/CLOCKS_PER_SEC;

                             printf("\nTime To Find Min Element is %f",Traverse_Time);

                             break;

                 case 5: first = clock();

                            printf("\nEnter Element to search : ");

                            scanf("%d",&Temp_Val);

                            Flag = SearchNode(n,Temp_Val);

                            if(Flag!=0)

                            printf("\nElement Not Found");

                           else

                           printf("\nElement Found");

                           second = clock();

                           Traverse_Time = (second-first)/CLOCKS_PER_SEC;

                           printf("\nTime To Search Element is %f",Traverse_Time);

                           break;

                case 6: first = clock();

                            printf("\nIn Order Traversal...");

                            InOrderTraversal(n);

                            second = clock();

                            Traverse_Time = (second-first)/CLOCKS_PER_SEC;

                             printf("\nTime To InOrder Traversal is %f",Traverse_Time);

                             break;

                  case 7: first = clock();

                             printf("\nPre Order Traversal...");

                             PreOrderTraversal(n);

                             second = clock();

                             Traverse_Time = (second-first)/CLOCKS_PER_SEC;

                             printf("\nTime To PreOrder Traversal is %f",Traverse_Time);

                             break;

                 case 8: first = clock();

                             printf("\nPost Order Traversal...");

                             PostOrderTraversal(n);

                             second = clock();

                             Traverse_Time = (second-first)/CLOCKS_PER_SEC;

                             printf("\nTime To PostOrder Traversal is %f",Traverse_Time);

                             break;

                            default: exit(0);

                       }

                       printf("\nDo You want to Continue [y/n]...");

       }while(getchar()=='Y' || getchar()=='y');

       getch();

}

int SearchNode(struct Node *n, int x)

{

       if (n->val==x)

           return 0;

       else if(n->lptr==NULL && n->rptr==NULL)

           return 1;

       else if(x < n->val)

              return SearchNode(n->lptr,x);

       else if(x > n->val)

              return SearchNode(n->rptr,x);

}

struct Node *InsertIntoTree(struct Node *n, int x)

{

       struct Node *newNode;

       newNode = (struct Node*)malloc(sizeof(struct Node));

       newNode->val = x;

       newNode->lptr = newNode->rptr = NULL;

       if(n==NULL)

       {

                       n = newNode;

                       n->lptr=NULL;

                       n->rptr=NULL;

       }

       else

       {

                       if(x < n->val)

                                       n->lptr = InsertIntoTree(n->lptr,x);

                       else

                                       n->rptr = InsertIntoTree(n->rptr,x);

       }

       return n;

}

struct Node *DeleteFromTree(struct Node *n, int x)

{

       if(n==NULL)

                       printf("\nNo any element exist in Tree");

       else if(x < n->val)

                       n->lptr = DeleteFromTree(n->lptr,x);

       else if(x > n->val)

                       n->rptr = DeleteFromTree(n->rptr,x);

       else

       {

                       if(n->lptr !=NULL && n->rptr != NULL)

                       {

                                       struct Node *Max_Ele;

                                       Max_Ele = SearchMaxElement(n->lptr);

                                       n->val = Max_Ele->val;

                                       n->lptr = DeleteFromTree(n->lptr,Max_Ele->val);

                       }

                       else

                       {

                                       struct Node *Temp;

                                       Temp = n;

                                       if(n->lptr == NULL)

                                                       n = n->rptr;

                                       else

                                                       n = n->lptr;

                                       free(Temp);

                       }

       }

       return (n);

}

struct Node *SearchMaxElement(struct Node *n)

{

       if (n==NULL || n->rptr == NULL)

                       return n;

       else

                       return SearchMaxElement(n->rptr);

}

struct Node *SearchMinElement(struct Node *n)

{

       if(n==NULL || n->lptr == NULL)

                       return n;

       else

                       return SearchMinElement(n->lptr);

}

void InOrderTraversal(struct Node *n)

{

       struct Node *Cur, *Pre;

       if(n==NULL)

                       return;

       Cur = n;

       while(Cur != NULL)

       {

                       if(Cur->lptr == NULL)

                       {

                                       printf("\t%d",Cur->val);

                                       Cur= Cur->rptr;

                       }

                       else

                       {

                                       Pre = Cur->lptr;

                                       while(Pre->rptr !=NULL && Pre->rptr != Cur)

                                                       Pre = Pre->rptr;

                                       if (Pre->rptr == NULL)

                                       {

                                                       Pre->rptr = Cur;

                                                       Cur = Cur->lptr;

                                       }

                                       else

                                       {

                                                       Pre->rptr = NULL;

                                                       printf("\t%d",Cur->val);

                                                       Cur = Cur->rptr;

                                       }

                       }

       }

}

void PreOrderTraversal(struct Node* n)

{

       if(n!=NULL)

       {

                       printf("\t%d",n->val);

                       PreOrderTraversal(n->lptr);

                       PreOrderTraversal(n->rptr);

       }

}

void PostOrderTraversal(struct Node *n)

{

       if(n!=NULL)

       {

                       PostOrderTraversal(n->lptr);

                       PostOrderTraversal(n->rptr);

                       printf("\t%d",n->val);

       }

}

C Programming of DDA line drawing algorithm

#include<stdio.h>
#include<conio.h>
#include<graphics.h>
#include<ctype.h>
#include<math.h>
#include<stdlib.h>
void draw(int x1,int y1,int x2,int y2);
void main()
{
int x1,y1,x2,y2;
int gdriver=DETECT,gmode,gerror;
initgraph(&gdriver,&gmode,”c:\\tc\\bgi:”);
printf(“\n Enter the x and y value for starting point:\n”);
scanf(“%d%d”,&x1,&y1);
printf(“\n Enter the x and y value for ending point:\n”);
scanf(“%d%d”,&x2,&y2);
printf(“\n The Line is shown below: \n”);
draw(x1,y1,x2,y2);
getch();
}
void draw(int x1,int y1,int x2,int y2)
{
float x,y,xinc,yinc,dx,dy;
int k;
int step;
dx=x2-x1;
dy=y2-y1;
if(abs(dx)>abs(dy))
step=abs(dx);
else
step=abs(dy);
xinc=dx/step;
yinc=dy/step;
x=x1;
y=y1;
putpixel(x,y,1);
for(k=1;k<=step;k++)
{
x=x+xinc;
y=y+yinc;
putpixel(x,y,2);
}
}

C++ Programming of DDA line drawing algorithm

# include <graphics.h>
# include <math.h>
# include <conio.h>
# include <iostream.h>
void DDALine(int x1,int y1,int x2,int y2,int iColor);
void main()
{
    int gDriver=DETECT,gMode;

    int x1,x2,y1,y2,iColor;

    initgraph(&gDriver,&gMode,"c:\\tc\\bgi");
    cleardevice();
    cout<<endl<<"Enter x1  : ";
    cin>>x1;
    cout<<"Enter y1  : ";
    cin>>y1;
    cout<<endl<<"Enter x2  : ";
    cin>>x2;
    cout<<"Enter y2  : ";
    cin>>y2;
    cout<<endl<<"Enter COLOR  : ";
    cin>>iColor;
    cleardevice();
    DDALine(320,1,320,480,12);
    DDALine(1,240,640,240,12);
    circle(320,240,2);
    DDALine(320+x1,240-y1,320+x2,240-y2,iColor%16);
    getch();
}

void DDALine(int x1,int y1,int x2,int y2,int iColor)
{
    float dX,dY,iSteps;
    float xInc,yInc,iCount,x,y;

    dX = x1 - x2;
    dY = y1 - y2;

    if (fabs(dX) > fabs(dY))
    {
        iSteps = fabs(dX);
    }
    else
    {
        iSteps = fabs(dY);
    }

    xInc = dX/iSteps;
    yInc = dY/iSteps;

    x = x1;
    y = y1;
    circle(x,y,1);

    for (iCount=1; iCount<=iSteps; iCount++)
    {
        putpixel(floor(x),floor(y),iColor);
        x -= xInc;
        y -= yInc;
    }
    circle(x,y,1);
    return;
}

C++ Program To Bubble Search

#include<iostream.h>
#include<conio.h>
void main()
{

int a[50];
clrscr();
cout<<"enter no of elements:";
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"a["<<i<<"]:";
cin>>a[i];
}
for(i=0;i<n;i++)
{
cout<<"a["<<i<<"]:"<<a[i]<<endl;
}
for(int j=0;j<n;j++)
{
for(i=0;i<n;i++)
{
if(a[i+1]<a[i])
{
   int temp=a[i+1];
   a[i+1]=a[i];
   a[i]=temp;
}
}
}
for(i=0;i<n;i++)
{
cout<<"a["<<i<<"]:"<<a[i]<<endl;
}
getch();

}

C++ Program To Binary Search

//BINARY SEARCH
#include<iostream.h>
#include<conio.h>

void main()
{
int a[50];
clrscr();
cout<<"enter no of elements:";
int n;
cin>>n;
cout<<"enter in asceding order::";
for(int i=0;i<n;i++)
{
cout<<"a["<<i<<"]:";
cin>>a[i];
}
for(i=0;i<n;i++)
{
cout<<"a["<<i<<"]:"<<a[i]<<endl;
}
cout<<"enter no which you want to saerch:";
int m;
cin>>m;
int fi=0;
int la=n-1;
for(;!(m>a[la]||m<a[fi]);)
{
int mid=(fi+la)/2;

if(m==a[mid])
{
     cout<<"your no at:"<<mid;
     break;
}
else if(m>a[mid])
{
fi=mid+1;
}
else
{
la=mid-1;
}
}

getch();
}

Example Of Dijkstra's algorithm

C Program to print Product of Digits of a given number

/*
eg. 212=2*1*2=4
eg. 313=3*1*3=9
*/

#include<stdio.h>

#include<conio.h>

void main()

{

 int no,r,pt=1;

 clrscr();

 printf("Enter a no:");

 scanf("%d",&no);

 while(no>0)

 {

  r=no%10;

  pt=pt*r;

  no=no/10;

 }

 printf("Product of Digits= %d",pt);

 getch();

}

C program to sort 10 Array elements in descending order Using Array

# include<stdio.h>
# include<conio.h>
void main()
{
int arr[10];
int i,j,temp;
clrscr();
for(i=0;i<10;i++)
scanf("%d",&arr[i]);
for(i=0;i<9;i++)
{
  for(j=i+1;j<10;j++)
  {
   if(arr[i]<arr[j])
   {
   temp=arr[i];
   arr[i]=arr[j];
   arr[j]=temp;
   }
}
}
printf("\nSorted array elements :\n");
for(i=0;i<10;i++)
printf("%d ",arr[i]) ;
getch();
}

C Program to Reverse print an array

# include<stdio.h>
# include<conio.h>

void main()
{
int arr[10];
int i,j,temp;
clrscr();
for(i=0;i<10;i++)
scanf("%d",&arr[i]);
printf("\nPrinting an sorted array\n");
for(i=9;i>=0;i--)
printf("%d ",arr[i]) ;
getch();
}

C Program to Print Alternate Using Array

# include<stdio.h>
# include<conio.h>
void main()
{
 int arr[10];
 int i,j,temp;
 clrscr();
 for(i=0;i<10;i++)
 scanf("%d",&arr[i]);
 for(i=0;i<10;i+=2)
 printf("%d ",arr[i]) ;
 getch();
}

C Program print alternate element of an array

 /*C Program to print alternate element of an array*/
# include<stdio.h>
# include<conio.h>

void main()
{
int arr[10];
int i,j,temp;
clrscr();
for(i=0;i<10;i++)
scanf("%d",&arr[i]);
for(i=0;i<10;i+=2)
printf("%d ",arr[i]) ;
getch();
}

C Program Accept 10 numbers and no. to search, print its occurrence Using Array

/* Accept 10 numbers and no. to search, print its occurence
 Write a program to accept 10 no’s  and a number to search and print how many times it occurs in array */

# include<stdio.h>
# include<conio.h>

void main()
{
 int arr[10];
 int i,cnt=0,tosearch;
 clrscr();
 /* accepting an array*/
 for(i=0;i<10;i++)
  {
   printf("\n Enter %d number-",i);
   scanf("%d",&arr[i]);
   }
 printf("\nEnter a number to be search-");
 scanf("%d",&tosearch);
 for(i=0;i<10;i++)
 {
  if(arr[i]==tosearch)
    cnt++;
 }
 printf("\n Number occurs %d times",cnt);
 getch();
}

Friend Function Using C++

#include<iostream.h>

class Sample

{

int a;

int b;

public:

void setvalue()

{

a=25;

b=40;

}

friend int avg(Sample s);

};

int avg(Sample s)

{

return(s.a+s.b)/2;

}

Void main()

{

Sample x;

x.setvalue();

cout<<avg(x);

}

************************************

Friend function

With the use of a friend function we can access the private data of a class.

class Abc

{

….

….

public:

….

friend void xyz();/declaration

};

Characteristics of friend function

>It is not in the scope of the class to which it has been declared 

>Since it is not in the scope of the class,it cannot be called using the object of that class

>It can be invoked like a normal function without the help of any object

>But we cannot access the member names directly & has to use an object name & dot operator

 (e.g. A.x)

>Usually it has the objects as arguments