C Program to implement Binary Search Tree

#include
#include
#include
typedef int ElementType;
struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
SearchTree MakeEmpty( SearchTree T );
Position Find( ElementType X, SearchTree T );
Position FindMin( SearchTree T );
Position FindMax( SearchTree T );
SearchTree Insert( ElementType X, SearchTree T );
SearchTree Delete( ElementType X, SearchTree T );
ElementType Retrieve( Position P );
void display(SearchTree T);
struct TreeNode
{
ElementType Element;
SearchTree Left;
SearchTree Right;
};
SearchTree MakeEmpty( SearchTree T )
{
if( T != NULL )
{
MakeEmpty( T->Left );
MakeEmpty( T->Right );
free( T );
}
return NULL;
}
Position Find( ElementType X, SearchTree T )
{
if( T == NULL )
return NULL;
if( X <>Element )
return Find( X, T->Left );
else
if( X > T->Element )
return Find( X, T->Right );
else
return T;
}
Position FindMin( SearchTree T )
{
if( T == NULL )
return NULL;
else
if( T->Left == NULL )
return T;
else
return FindMin( T->Left );
}
Position FindMax( SearchTree T )
{
if( T != NULL )
while( T->Right != NULL )
T = T->Right;

return T;
}


SearchTree Insert( ElementType X, SearchTree T )
{
/* 1*/ if( T == NULL )
{
/* Create and return a one-node tree */
/* 2*/ T =(struct TreeNode *) malloc( sizeof( struct TreeNode ) );
/* 3*/ if( T == NULL )
/* 4*/ printf( "Out of space!!!" );
else
{
/* 5*/ T->Element = X;
/* 6*/ T->Left = T->Right = NULL;
}
}
else
/* 7*/ if( X <>Element )
/* 8*/ T->Left = Insert( X, T->Left );
else
/* 9*/ if( X > T->Element )
/*10*/ T->Right = Insert( X, T->Right );
/* Else X is in the tree already; we'll do nothing */

/*11*/ return T; /* Do not forget this line!! */
}
SearchTree Delete( ElementType X, SearchTree T )
{
Position TmpCell;

if( T == NULL )
printf( "Element not found" );
else
if( X <>Element ) /* Go left */
T->Left = Delete( X, T->Left );
else
if( X > T->Element ) /* Go right */
T->Right = Delete( X, T->Right );
else /* Found element to be deleted */
if( T->Left && T->Right ) /* Two children */
{
/* Replace with smallest in right subtree */
TmpCell = FindMin( T->Right );
T->Element = TmpCell->Element;
T->Right = Delete( T->Element, T->Right );
}
else /* One or zero children */
{
TmpCell = T;
if( T->Left == NULL ) /* Also handles 0 children */
T = T->Right;
else if( T->Right == NULL )
T = T->Left;
free( TmpCell );
}

return T;
}

ElementType Retrieve( Position P)
{
return P->Element;
}
void display(SearchTree T)
{

printf("%d\t",T->Element);
if(T->Left!=NULL)
display(T->Left);
if(T->Right!=NULL)
display(T->Right);
}

#include

main( )
{
SearchTree T;
Position P;
int a; int f,b;
int n;
T = MakeEmpty( NULL );
while(1)
{
printf("\nenter ur choice 1.insert 2.find 3.find min and max 4.delete 5.display 6.exit\n");
scanf("%d",&n);
switch(n)
{
case 1:
printf("enter the element\n");
scanf("%d",&a);
T = Insert( a, T );
break;
case 2:
printf("enter the element to found\n");
scanf("%d",&f);
printf("the element is found it is%d",Retrieve(Find(f,T)));
break;
case 3:

printf( "Min is %d, Max is %d\n", Retrieve( FindMin( T ) ),
Retrieve( FindMax( T ) ) );
break;
case 4:

printf("to delete an element..enter the element");
scanf("%d",&b);
Delete(b,T);
break;
case 5:
display(T);
break;
case 6:
exit(0);
break;
default:
printf("invaid choice\n");
}
}
}

OUTPUT:


enter ur choice 1.insert 2.find 3.find min and max 4.delete 5.display 6.exit
1
enter the element
1

enter ur choice 1.insert 2.find 3.find min and max 4.delete 5.display 6.exit
1
enter the element
2

enter ur choice 1.insert 2.find 3.find min and max 4.delete 5.display 6.exit
1
enter the element
0

enter ur choice 1.insert 2.find 3.find min and max 4.delete 5.display 6.exit
2
enter the element to found
0
the element is found it is0
enter ur choice 1.insert 2.find 3.find min and max 4.delete 5.display 6.exit
3
Min is 0, Max is 2

enter ur choice 1.insert 2.find 3.find min and max 4.delete 5.display 6.exit
4
to delete an element..enter the element0

enter ur choice 1.insert 2.find 3.find min and max 4.delete 5.display 6.exit
5
1 2
enter ur choice 1.insert 2.find 3.find min and max 4.delete 5.display 6.exit