/********************************************************************
This program create binary search tree from text file and use
binary search tree operation to process the tree. Program will
show user manu to how use the binary search tree operation in the
program to let user update data stored in file. At end of program the
tree will save in text file.
********************************************************************/

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

#define size 50

/*******************************************************************
Define component of tree.
********************************************************************/

struct node
{
  int data;
  struct node *left, *right;
};

typedef struct node Node;
typedef Node * TreePtr;

/********************************************************************
Function prototypes.
********************************************************************/

void     Build_Tree              (TreePtr*);
void     ReadDataFromFile        (TreePtr*,FILE *);

int      menu                    ();

void     PrintChoice             (TreePtr );
void     inorder                 (TreePtr );
void     preorder                (TreePtr );
void     postorder               (TreePtr );

void     InsertChoice            (TreePtr *);
void     Insert_1_Key            (TreePtr *);
void     Insert_Manually_Keys    (TreePtr *);
void     Insert_Random_Keys      (TreePtr *);
void     insert                  (TreePtr *,int);

void     DeleteChoice            (TreePtr *);
void     Delete_1_Key            (TreePtr *);
TreePtr  Search_Victem 	         (TreePtr,int);
TreePtr  Search_Parent 	         (TreePtr,int);
int      delete                  (TreePtr *,int);
void     Delete_All_Tree         (TreePtr *);

void     largest                 (TreePtr);
int      FindLargestNode         (TreePtr);

void     smallest                (TreePtr);
int      FindSmallestNode        (TreePtr);

void     leafs                   (TreePtr);
int      Total_Leafs             (TreePtr);

void     height                  (TreePtr);
void     Height_Of_Tree          (TreePtr,int *);

int      IsEmpty                 (TreePtr);

void     SaveInFile              (TreePtr);
void     PrintTreeInFile         (TreePtr,FILE *);

int main()
{
  TreePtr tree = NULL;
  int choice;

  Build_Tree(&tree);

  do
  {
    choice = menu();

    switch (choice)
    {

      case 1 :  PrintChoice(tree);
		break;

      case 2 :  InsertChoice(&tree);
		break;

      case 3 :  DeleteChoice(&tree);
		break;

      case 4 :  largest(tree);
		break;

      case 5 :  smallest(tree);
		break;

      case 6 :  leafs(tree);
		break;

      case 7 :  height(tree);
		break;

      case 8 :  SaveInFile(tree);
		break;

      default : printf("\n\n\nInvalid choice, try again\n");
		printf("\n\n\n\n\n\n\nPress ENTER or any key to continue. \n");
		getch();
		break;
    }

  }while (choice != 8);

  return 0;
}

/*******************************************************************
This function build tree before manu run.
*******************************************************************/

void Build_Tree (TreePtr *tree)
{
  FILE *fptr;
  int key;

  if ((fptr=fopen("tree.dat","r"))==NULL)
    printf("\nThe File could not open \n");
  else
    ReadDataFromFile(&*tree,fptr);
  fclose(fptr);
}

/*******************************************************************
This function store data from file in tree.
*******************************************************************/

void ReadDataFromFile (TreePtr *tree,FILE *fptr)
{
  int key;

  fscanf(fptr,"%d",&key);
  if (!feof(fptr))        /* To ckeck before store the file is empty or no */
    insert(&*tree,key);

  while (!feof(fptr))
  {
    fscanf(fptr,"%d",&key);
    insert(&*tree,key);
  }
}

/*******************************************************************
This function show program manu.
*******************************************************************/

int menu ()
{
  int choice;

  clrscr();

  printf("Binary search tree menu : \n");
  printf("========================== \n");
  printf("1 - Print tree in screen (( 3 ways to print )).\n");
  printf("2 - Insert keys (( 3 ways to insert )).\n");
  printf("3 - Delete keys (( 2 ways to delete )).\n");
  printf("4 - Find the maximum number in the tree.\n");
  printf("5 - Find the minimum number in the tree.\n");
  printf("6 - Print total number of leafs.\n");
  printf("7 - Print the height of the tree.\n");
  printf("8 - Quit.\n");

  printf("\n\nEnter your choice: \n");
  scanf("%d", &choice);

  return(choice);
}

/*******************************************************************
This function show manu of how to print tree.
*******************************************************************/

void PrintChoice (TreePtr tree)
{
  int  choice;

  clrscr();

  if (!IsEmpty(&*tree))
  {
    printf("Printing Choice : \n");
    printf("================== \n");
    printf("1 - Inorder traversing.\n");
    printf("2 - Preorder traversing.\n");
    printf("3 - Postorder traversing.\n");

    printf("\nEnter your choice : \n");
    scanf("%d", &choice);

    printf("\n");

    if (choice==1)
      inorder(tree);
    else
    if (choice==2)
      preorder(tree);
    else
    if (choice==3)
      postorder(tree);
    else
      printf("You enter invalid choice try again. \n");
  }
  else
     printf("Try again the tree is empty. \n");

  printf("\n\n\n\n\nPress ENTER or any key to continue. \n");
  getch();
}

/*******************************************************************
Inorder traversing :
====================
1 - Traverse the left subtree inorder.
2 - Print the value in the node.
3 - Traverse the right subtree inorder.
*******************************************************************/

void inorder (TreePtr tree)
{
  if (tree!=NULL)
  {
    inorder(tree->left);
    printf(" %d ", tree->data);
    inorder(tree->right);
  }
}

/*******************************************************************
Preorder traversing :
====================
1 - Print the value in the node.
2 - Traverse the left subtree preorder.
3 - Traverse the right subtree preorder.
*******************************************************************/

void preorder (TreePtr tree)
{
  if (tree!=NULL)
  {
    printf(" %d ", tree->data);
    preorder(tree->left);
    preorder(tree->right);
  }
}

/*******************************************************************
Postorder traversing :
====================
1 - Traverse the left subtree postorder.
2 - Traverse the right subtree postorder.
3 - Print the value in the node.
*******************************************************************/

void postorder (TreePtr tree)
{
  if (tree!=NULL)
  {
    postorder(tree->left);
    postorder(tree->right);
    printf(" %d ", tree->data);
  }
}

/*******************************************************************
This function show manu of insertion to tree.
*******************************************************************/

void InsertChoice (TreePtr *tree)
{
  int choice;

  clrscr();

  printf("Inserting Choice : \n");
  printf("=================== \n");
  printf("1 - Insert one key.\n");
  printf("2 - Insert multiple keys manually.\n");
  printf("3 - Insert multople keys randomly.\n");
  printf("\nNOTE : duplicate number will not add to binary search tree.\n");

  printf("\n\n\nEnter your choice : \n");
  scanf("%d", &choice);

  if (choice==1)
  {
    printf("\n\nPlzzz enter key : \n");
    Insert_1_Key(&*tree);
  }
  else
  if (choice==2)
    Insert_Manually_Keys(&*tree);
  else
  if (choice==3)
    Insert_Random_Keys(&*tree);
  else
    printf("\n\nYou enter invalid choice try again. \n");

  printf("\n\n\n\n\n\n\nPress ENTER or any key to continue. \n");
  getch();
}

/*******************************************************************
This function insert 1 key to tree.
*******************************************************************/

void Insert_1_Key (TreePtr *tree)
{
  int key;

  scanf("%d",&key);
  insert(&*tree,key);
}

/*******************************************************************
This function insert multiple keys manually to tree.
*******************************************************************/

void Insert_Manually_Keys (TreePtr *tree)
{
  int i,Number_Of_Keys;

  clrscr();
  printf("Plzzz enter # of keys to insert in tree manually : \n");
  scanf("%d",&Number_Of_Keys);

  for (i=0;i<Number_Of_Keys;i++)
  {
    printf("\nPlzzz enter element for key # %d : \n",i+1);
    Insert_1_Key(&*tree);
  }
}

/*******************************************************************
This function insert multiple keys manually to tree.
*******************************************************************/

void Insert_Random_Keys (TreePtr *tree)
{
  int i,Number_Of_Keys;

  clrscr();
  printf("Plzzz enter # of keys to insert in tree randomly : \n");
  scanf("%d",&Number_Of_Keys);

  srand(time(NULL));

  for (i=0;i<Number_Of_Keys;i++)
  insert(&*tree,rand()%size);
}

/*******************************************************************
This function insert keys to tree.
*******************************************************************/

void insert (TreePtr *tree,int value)
{
   if ( *tree == NULL )
  {
     *tree = malloc( sizeof( Node ) );

    if ( *tree != NULL )
    {
	 ( *tree )->data = value;
	 ( *tree )->left = NULL;
	 ( *tree )->right = NULL;
      }
      else
      {
	printf( "%d not inserted. No memory available.\n",value );
	printf("\n\n\n\n\n\n\nPress ENTER or any key to continue. \n");
	getch();
      }
   }
   else
      if ( value < ( *tree )->data )
	 insert( & ((*tree)->left) , value );
     else if ( value > ( *tree )->data )
	 insert( &(( *tree) ->right) , value );
}

/*******************************************************************
This function show manu to delete from tree.
*******************************************************************/

void DeleteChoice (TreePtr *tree)
{
  int choice;

  clrscr();

  if (!IsEmpty(*tree))
  {
    printf("Deleting Choice : \n");
    printf("================== \n");
    printf("1 - Delete one node.\n");
    printf("2 - Delete the whole tree.\n");

    printf("\nEnter your choice : \n");
    scanf("%d", &choice);

    if (choice==1)
      Delete_1_Key(&*tree);
    else
    if (choice==2)
    {
      Delete_All_Tree(&*tree);
      printf("\n\nThe tree has been destroy. \n");
    }
    else
      printf("You enter invalid choice try again. \n");
   }
   else
      printf("Try again the tree is empty. \n");

   printf("\n\n\n\n\n\n\nPress ENTER or any key to continue. \n");
   getch();
}

/*******************************************************************
This function delete 1 key from tree.
*******************************************************************/

void Delete_1_Key (TreePtr *tree)
{
  int key;

  printf("\n\nPlzzz enter key to delete it : \n");
  scanf("%d",&key);

  if (delete(&*tree,key))
    printf("\n\nThe key %d delete from tree. \n",key);
  else
    printf("\n\nThe key %d not fount in the tree. \n",key);
}

/*******************************************************************
This function find the victem key to be delete from tree.
*******************************************************************/

TreePtr Search_Victem (TreePtr tree,int key)
{
  if ( tree->data==key)
    return tree;
  else
  if (tree->left==NULL && tree->right==NULL)
    return NULL;
  else
  if (key<tree->data)
    return Search_Victem (tree->left,key);
  else
    return Search_Victem (tree->right,key);
}

/*******************************************************************
This function find the parent of victem key to be delete from tree.
*******************************************************************/

TreePtr Search_Parent (TreePtr tree,int key)
{
  if (tree->left->data==key && tree->left!=NULL)
    return tree;
  if (tree->right->data==key && tree->right!=NULL)
    return tree;
  if (key<tree->data)
    return Search_Parent (tree->left,key);
  else
    return Search_Parent (tree->right,key);
}

/*******************************************************************
This function delete one key from tree.
*******************************************************************/

int delete (TreePtr *tree,int data)
{
    TreePtr parent,victem;
    int MaxLeft;

    victem=Search_Victem(*tree,data);

/* First 3 conditions only if tree contain 1 or 2 node and delete all tree */

    if ( victem->left==NULL && victem->right==NULL && victem==*tree )
    {
      free(*tree);
      *tree=NULL;
      return 1;                       /* Victem delete */
    }

    else

    if ( victem->left==NULL && victem==*tree )
    {
      *tree=victem->right;
      free(victem);
      return 1;                       /* Victem delete */
    }

    else

    if ( victem->right==NULL && victem==*tree )
    {
      *tree=victem->left;
      free(victem);
      return 1;                       /* Victem delete */
    }

    else

    /* This condition to check if victem not found not need
       to search the parent of victem and not do delete operations */

    if ( victem!=NULL )
    {
       /* This condition if we delete the root is victem not need
	  to search parent of victem */

      if ( victem!=*tree )
	parent=Search_Parent(*tree,data);

      /* This for if victem is leaf */

      if ( victem->left == NULL && victem->right == NULL )
      {
	if ( victem->data < parent->data )
	  parent->left=NULL;
      else
	if ( victem->data > parent->data )
	  parent->right=NULL;
	free(victem);
      }
      else

      /* Delete victem if it have child in right and indicate the pointer
	 of parent to the right of child of victem */

      if ( victem->left == NULL )
      {
	if ( victem->data < parent->data )
	  parent->left = victem->right;
	else
	  parent->right = victem->right;
	free(victem);
      }
      else

      /* Delete victem if it have child in left and indicate the pointer
	 of parent to the left of child of victem */

      if ( victem->right == NULL )
      {
	if ( victem->data < parent->data )
	  parent->left = victem->left;
	else
	  parent->right = victem->left;
	free(victem);
      }
      else

      /* Find largest # in left tree to be parent */

      {
	MaxLeft = FindLargestNode (victem->left);
	victem->data = MaxLeft;

	/* Special case if MaxLeft == victem */

	if ( victem->data == victem->left->data && parent!=NULL )
	{
	  parent=victem;
	  victem=victem->left;

	  if ( victem->left == NULL )     /* Right NULL not need to check */
	  {
	    parent->left=NULL;
	    free(victem);
	  }
	  else         /* Left not NULL */
	  {
	    parent->left = victem->left;
	    free(victem);
	  }
	}
	else
	  delete(&victem->left,MaxLeft);
      }

      return 1;     /* Victem delete */

    }

    else

       return 0;    /* Victem not delete */
}

/*******************************************************************
This function destroy the tree.
*******************************************************************/

void Delete_All_Tree (TreePtr *tree)
{
  if (*tree!=NULL)
  {
    Delete_All_Tree(&(*tree)->left);
    Delete_All_Tree(&(*tree)->right);
    delete(&*tree,(*tree)->data);
  }
}

/*******************************************************************
This function show user the maximum number in the tree.
*******************************************************************/

void largest (TreePtr tree)
{
  clrscr();

  if (!IsEmpty(tree))
    printf("The maximum # in tree = %d \n",FindLargestNode(tree));
  else
    printf("Try again the tree is empty. \n");

  printf("\n\n\n\n\n\n\nPress ENTER or any key to continue. \n");
  getch();
}

/*******************************************************************
This function find the maximum number in the tree.
*******************************************************************/

int FindLargestNode (TreePtr tree)
{
  if (tree->right==NULL)
    return(tree->data);
  return FindLargestNode (tree->right);
}

/*******************************************************************
This function show user the minimum number in the tree.
*******************************************************************/

void smallest (TreePtr tree)
{
  clrscr();

  if (!IsEmpty(tree))
    printf("The minimum # in tree = %d \n",FindSmallestNode(tree));
  else
    printf("Try again the tree is empty. \n");

  printf("\n\n\n\n\n\n\nPress ENTER or any key to continue. \n");
  getch();
}

/*******************************************************************
This function find the minimum number in the tree.
*******************************************************************/

int FindSmallestNode (TreePtr tree)
{
  if (tree->left==NULL)
    return(tree->data);
  return FindSmallestNode (tree->left);
}

/*******************************************************************
This function show user total # of leafs in the tree.
*******************************************************************/

void leafs (TreePtr tree)
{
  clrscr();

  if (!IsEmpty(tree))
    printf("The total # of leafs in the tree = %d \n",Total_Leafs(tree));
  else
    printf("Try again the tree is empty. \n");

  printf("\n\n\n\n\n\n\nPress ENTER or any key to continue. \n");
  getch();
}

/*******************************************************************
This function compute total # od leafs in the tree.
*******************************************************************/

int Total_Leafs (TreePtr tree)
{
  if (tree==NULL)  /* This condition nothing do just return 0 to end */
    return 0;      /* compute with out this condition make infinite loop */
  else
  if ( tree->left==NULL  && tree->right==NULL)
    return 1;
  else
  return (Total_Leafs(tree->left) + Total_Leafs(tree->right));
}

/*******************************************************************
This function show user height of tree.
*******************************************************************/

void height (TreePtr tree)
{
  int  height;

  clrscr();

  if (!IsEmpty(tree))
  {
    Height_Of_Tree(tree,&height);
    printf("The height of tree = %d \n",height-1);
  }
  else
    printf("Try again the tree is empty. \n");

  printf("\n\n\n\n\n\n\nPress ENTER or any key to continue. \n");
  getch();
}

/*******************************************************************
This function compute height of the tree.
*******************************************************************/

void Height_Of_Tree (TreePtr tree, int *height)
{
  int left_height, right_height;

  if (tree==NULL)
    *height=0;
  else
  {
    Height_Of_Tree(tree->left, &left_height);
    Height_Of_Tree(tree->right, &right_height);
    if( left_height > right_height)
	*height=left_height+1;
    else
	*height=right_height+1;
  }
}

/*******************************************************************
This function to check if the tree is empty or no.
*******************************************************************/

int IsEmpty (TreePtr tree)
{
  return  tree == NULL ;
}

/*******************************************************************
This function save the tree in file.
*******************************************************************/

void SaveInFile (TreePtr tree)
{
  FILE *fptr;
  int key;

  if ((fptr=fopen("tree.dat","w"))==NULL)
    printf("\nThe File could not open \n");
  else
    PrintTreeInFile(tree,fptr);
  fclose(fptr);
}

/*******************************************************************
This function write data of tree in file.
*******************************************************************/

void PrintTreeInFile (TreePtr tree,FILE *fptr)
{
  if (tree!=NULL)
  {
    fprintf(fptr,"%d ",tree->data);
    PrintTreeInFile(tree->left,fptr);
    PrintTreeInFile(tree->right,fptr);
  }
}