SEARCH TREE ADT - BINARY SEARCH TREE

SOURCE CODE:

“Tree.h” File:

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
struct node
{
   int data;
   struct node *left;
   struct node *right;
};
typedef struct node *ptrToNode;
typedef ptrToNode TREE;
typedef ptrToNode POSITION;

POSITION createnode(int x)
{
   POSITION P;
   P=(struct node*)malloc(sizeof(struct node));
   if(P==NULL)
      printf("\n\n FATAL ERROR");
   else
   {
      P->data=x;
      P->left=P->right=NULL;
   }
   return P;
}
void MakeEmpty(TREE T)
{
   if(T!=NULL)
   {
      MakeEmpty(T->left);
      MakeEmpty(T->right);
      free(T);
   }
}
TREE Insert(int x,TREE T)
{
   if(T==NULL)
      T=createnode(x);
   else if(x<T->data)
      T->left=Insert(x,T->left);
   else if(x>T->data)
      T->right=Insert(x,T->right);
   else
      printf("\n Element is already present in the tree");
   return T;
}


POSITION Find(int x,TREE T)
{
   if(T==NULL)
      return NULL;
   else if(x<T->data)
      return Find(x,T->left);
   else if(x>T->data)
      return Find(x,T->right);
   else
      return T;
}
POSITION Findmin(TREE T)
{
   if(T==NULL)
      return NULL;
   else if(T->left==NULL)
      return T;
   else
      return Findmin(T->left);
}
POSITION Findmax(TREE T)
{
   if(T==NULL)
      return NULL;
   else if(T->right==NULL)
      return T;
   else
      return Findmax(T->right);
}
TREE Delete(int x,TREE T)
{
   POSITION temp;
   if(T==NULL)
      printf("\n Element is not found");
   else if(x<T->data)
      T->left=Delete(x,T->left);
   else if(x>T->data)
      T->right=Delete(x,T->right);
   else if(T->left&&T->right)
   {
      temp=Findmin(T->right);
      T->data=temp->data;
      T->right=Delete(T->data,T->right);
   }
   else
   {
      temp=T;
      if(T->left==NULL)
     T=T->right;
      else if(T->right==NULL)
     T=T->left;
  free(temp);

   }
   return T;
}
void Display(TREE T)
{
   if(T!=NULL)
   {
      Display(T->left);
      printf("\n%d",T->data);
      Display(T->right);
   }
}

“Tree.c” File:

#include"tree.h"
void main()
{
TREE T=NULL;
POSITION P=NULL;
int ch,x;
clrscr();
printf("\n1.create \n2.Insert \n3.Delete \n4.MakeEmpty \n5.Find \n6.Findmin \n7.Findmax \n8.Display \n9.Exit");
A:
printf("\n Enter Ur choice:\t");
scanf("%d",&ch);
switch(ch)
{
case 1:
    if(T==NULL)
    {
       printf("\n Enter the Element:\t");
       scanf("%d",&x);
       T=createnode(x);
    }
    break;
case 2:
    if(T==NULL)
       printf("\n Tree is not yet created");
    else
    {
       printf("\n Enter the element to insert:\t");
       scanf("%d",&x);
       T=Insert(x,T);
    }
    break;
case 3:
    if(T==NULL)
       printf("\n Tree is not yet created");
    else
    {

       printf("\n Enter the element to delete:\t");
       scanf("%d",&x);
       T=Delete(x,T);
    }
    break;
case 4:
    if(T==NULL)
       printf("\n Tree is not yet created");
    else
    {
       MakeEmpty(T);
       T=NULL;
       printf("\n Tree is empty now");
    }
    break;
case 5:
    if(T==NULL)
       printf("\n Tree is not yet created");
    else
    {
       printf("\n Enter the element to find");
       scanf("%d",&x);
       P=Find(x,T);
       if(P==NULL)
          printf("\n Element is not found in the tree");
       else
          printf("\n Element is found in the tree");
    }
    break;
case 6:
    if(T==NULL)
       printf("\n Tree is not yet created");
    else
    {
       P=Findmin(T);
       printf("\n Minimun element in the Tree is %d",P->data);
    }
    break;
case 7:
    if(T==NULL)
       printf("\n Tree is not yet created");
    else
    {
       P=Findmax(T);
       printf("\n Maximum element in the Tree is %d",P->data);
    }
    break;
case 8:
    if(T==NULL)
       printf("\n Tree is not yet created");
    else
       Display(T);
    break;
case 9:
    exit(0);
default:
    printf("\n Ur Option is Wrong");
}
goto A;
}

OUTPUT:

1.create
2.Insert
3.Delete
4.MakeEmpty
5.Find
6.Findmin
7.Findmax
8.Display
9.Exit
Enter Ur choice:       1
Enter the Element:     20

Enter Ur choice:       2
Enter the element to insert:   15

Enter Ur choice:       2
Enter the element to insert:   30

Enter Ur choice:       2
Enter the element to insert:   10

Enter Ur choice:       2
Enter the element to insert:   25

Enter Ur choice:       2
Enter the element to insert:   40

Enter Ur choice:       2
Enter the element to insert:   35

Enter Ur choice:       2
Enter the element to insert:   31

Enter Ur choice:       8
10
15
20
25
30
31
35
40

Enter Ur choice:       5
Enter the element to find30
Element is found in the tree

Enter Ur choice:       6
Minimun element in the Tree is 10


Enter Ur choice:       7
Maximum element in the Tree is 40

Enter Ur choice:       3
Enter the element to delete:   20

Enter Ur choice:       8
10
15
25
30
31
35
40

Enter Ur choice:       3
Enter the element to delete:   40

Enter Ur choice:       8
10
15
25
30
31
35

Enter Ur choice:       7
Maximum element in the Tree is 35

Enter Ur choice:       4
Now Tree becomes Empty

Enter Ur choice:       2
Tree is not yet created

Enter Ur choice:       9
Previous
Next Post »

If you still didn't find what you're looking for, you can search this website below: