Binary Search Tree (with display option)

[aruljothi]

Code :
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>


struct tree
{
int data;
tree *left,*right,*parent;
};
typedef tree *tree_type;
tree_type  root=NULL;



void delete_Node();
void printTree(tree_type ptr,int x,int y,int depth);
void predessor();
void successor();
tree_type minValue(tree_type ptr);
tree_type maxValue(tree_type ptr);
void insertion();
void search();
tree_type SearchNode(tree_type ptr,int target);
void Preorder(tree_type ptr);
void Postorder(tree_type ptr);
void Inorder(tree_type ptr);
void insert();
void insert_node(tree_type curr,tree_type ptr);
void Destroy();


void main(void)
{
  char choice;
do{
  clrscr();
  printf("
Binary Search Tree

");

  printf(" Insert Node.......1

");
  printf("Search Node.......2

");
  printf("Successor Node....3

");
  printf("Predessor Node....4

");
  printf("Delete Node.......5

");
  printf("Indorder..........6

");
  printf("Preorder..........7

");
  printf("Postorder.........8

");
  printf("Destroy Tree......9

");
  printf("Exit..............0


");
  printf("
Enter Choice Number ");
  scanf("%c",&choice);

  switch(choice)
  {
    case 49 : insertion();break;
    case 50 : search();getch();break;
    case 51 : successor();getch();break;
    case 52 : predessor();getch();break;
    case 53 : delete_Node();break;
    case 54 : clrscr();printf("
INORDER
TRAVERSAL

");Inorder(root);gotoxy(30,7);printf("Binary Search
Tree");printTree(root,38,10,0);getch();break;
    case 55 : clrscr();printf("
PREORDER
TRAVERSAL

");Preorder(root);gotoxy(30,7);printf("Binary Search
Tree");printTree(root,38,10,0);getch();break;
    case 56 : clrscr();printf("
POSTORDER
TRAVERSAL

");Postorder(root);gotoxy(30,7);printf("Binary Search
Tree");printTree(root,38,10,0);getch();break;
    case 57 : clrscr();Destroy();break;
    case 48 : break;

   }

}while(choice!=48);


}




void Destroy()
{
  char ch;
   clrscr();
  printf(" Destroy Tree (Y/N) ? ");
  ch=getche();
  if(ch=='y'||ch=='Y')    root=NULL;


}


void insert(int value)
{
  tree_type ptr;
  tree_type curr =(tree_type)malloc(sizeof(tree));
       curr->data=value;
       curr->left=NULL;
       curr->right=NULL;
       curr->parent=NULL;


     if(root==NULL) root=curr;
     else
     {    ptr=root;



      while(ptr->right!=NULL||ptr->left!=NULL)
         {
         if(ptr->data>=curr->data)  if(ptr->left!=NULL) ptr=ptr->left;

                    else break;

         if(ptr->data<curr->data) if(ptr->right!=NULL) ptr=ptr->right;

                      else break;



         }
         curr->parent=ptr;
      if(ptr->data<curr->data)  ptr->right=curr;


      if(ptr->data>curr->data)  ptr->left=curr;


     }

}

void printTree(tree_type ptr,int x,int y,int depth)
{
  if(ptr==NULL) return;

  gotoxy(x,y);

  printf("%d",ptr->data);

  if(ptr->left!=NULL) printTree(ptr->left,x-14/(depth+1),y+4,depth+1);

  if(ptr->right!=NULL)
printTree(ptr->right,x+14/(depth+1),y+4,depth+1);


}









void insert_node(tree_type curr,tree_type ptr)
{



      while(ptr->right!=NULL||ptr->left!=NULL)
         {
         if(ptr->data>=curr->data)  if(ptr->left!=NULL) ptr=ptr->left;

                    else break;

         if(ptr->data<curr->data) if(ptr->right!=NULL) ptr=ptr->right;

                      else break;


         }

         curr->parent=ptr;
      if(ptr->data<curr->data)   ptr->right=curr;


      if(ptr->data>curr->data)   ptr->left=curr;



}





void  search()
{
   int target;
   clrscr();
   gotoxy(30,7);printf("Binary Search Tree");printTree(root,38,10,0);
   gotoxy(1,1);
   printf("
Enter The Target Value To Search
");
   scanf("%d",&target);


   if(SearchNode(root,target)!=NULL) printf("Value %d Was Found
",target);
     else printf("Value %d Wasn't Found ",target);

}



tree_type SearchNode(tree_type ptr,int target)
{
   if(ptr==NULL) return NULL;
   if(ptr->data==target) return ptr;

   if(target<ptr->data) return SearchNode(ptr->left,target);

       else return SearchNode(ptr->right,target);

}




void Inorder(tree_type ptr)
{
       if(ptr==NULL) return;
   Inorder(ptr->left);
   printf(" %d ",ptr->data);
   Inorder(ptr->right);



}

void Preorder(tree_type ptr)
{
   if(ptr==NULL) return;
   printf(" %d ",ptr->data);
   Preorder(ptr->left);
   Preorder(ptr->right);

}
void Postorder(tree_type ptr)
{

   if(ptr==NULL) return;
   Postorder(ptr->left);
   Postorder(ptr->right);
   printf(" %d ",ptr->data);

}


void insertion()
{
int value;

   clrscr();
   printf("Insert Values Greater Than Zero
");
   scanf("%d",&value);

while(value>0) {

   insert(value);
   scanf("%d",&value);
   }

}


tree_type maxValue(tree_type ptr)
{
while(ptr->right!=NULL)
{ ptr=ptr->right;}
return ptr;
}

tree_type minValue(tree_type ptr)
{
while(ptr->left!=NULL)
ptr=ptr->left;
return ptr;
}


void successor()
{
    int target;
    tree_type ptr;
    clrscr();
    gotoxy(30,7);printf("Binary Search Tree");printTree(root,38,10,0);
    gotoxy(1,1);
    printf("
Enter The Value To Find Its Successor Node ");
    scanf("%d",&target);


    ptr=SearchNode(root,target);
    if(ptr==NULL) {printf("
Value %d  Was Not Found
",target);return;}

       if(ptr==maxValue(root)) printf("
Successor Node of %d Was Not
Found ",target);

       else {
     if(ptr->right!=NULL) {
            ptr=minValue(ptr->right);
            printf("
The Successor Node Was Found To Be %d",ptr->data);
                }
     else { while(ptr!=ptr->parent->left) ptr=ptr->parent;
       if(ptr->parent!=NULL) printf("
The Successor Node Was Found To Be
%d",ptr->parent->data);
       else printf("
Successor Node Was Not Found ");
          }
    }




}




void predessor()
{
    int target;
    tree_type ptr;
    clrscr();
     gotoxy(30,7);printf("Binary Search Tree");printTree(root,38,10,0);
    gotoxy(1,1);
    printf("
Enter The Value To Find Its Predessor Node ");
    scanf("%d",&target);


    ptr=SearchNode(root,target);
    if(ptr==NULL) {printf("
Value %d  Was Not Found
",target);return;}

    if(ptr==minValue(root)) printf("
Predessor Node of %d Was Not
Found
",target);
    else {
     if(ptr->left!=NULL) {
            ptr=maxValue(ptr->left);
            printf("
The Predessor Node Was Found To Be %d",ptr->data);
                }
     else { while(ptr!=ptr->parent->right) ptr=ptr->parent;
       if(ptr->parent!=NULL) printf("
The Predessor Node Was Found To Be
%d",ptr->parent->data);
       else printf("
Predessor Node Was Not Found ");
          }
    }




}

void delete_Node()
{
int target;
clrscr();
gotoxy(30,7);printf("Binary Search Tree");printTree(root,38,10,0);
gotoxy(1,2);
printf("
Enter The Target Value To Delete ");
scanf("%d",&target);
tree_type ptr;
ptr=SearchNode(root,target);

  if(ptr==NULL) { printf("
Node %d  Was Not Found ",target);getch();}

  else

    {
      if(ptr==root&&ptr->left==NULL&&ptr->
      right==NULL) {root=NULL;return;}

      if(ptr==root&&ptr->right!=NULL) {
                  root=ptr->right;
                  insert_node(ptr->left,root);
                  return;
                  }

    else if(ptr==root&&ptr->left!=NULL)  {root=ptr->left;return;}




      if(ptr->right==NULL&&ptr->left==NULL) if(ptr->data <
ptr->parent->data)
                    ptr->parent->left=NULL;
                 else ptr->parent->right=NULL;

      else {


     if(ptr->data<ptr->parent->data) ptr->parent->left=NULL;
     else ptr->parent->right=NULL;
     insert_node(ptr->right,ptr->parent);
     insert_node(ptr->left  ,ptr->parent);
     }
     }



}