Data Structure and Algorithm

/***************************************
 APPLICATION : A Complete Tree Program
 CODED BY    : Ankit Pokhrel
 COMPILED ON : Borland C++ Ver 5.02
 DATE     : 2010 - July - 27
***************************************/

#include "iostream.h"
#include "conio.h"

struct TREE //structure to represent a tree
{
 int data;
 struct TREE *right,*left,*root;
};

typedef TREE tree;

tree *New;
void create() //function to create a node
{
 New = new tree;
 New -> left = NULL;
 New -> right = NULL;
}

tree *par; //parent node
tree* find(tree *t,int item)
{
 tree *loc,*ptr,*save;
 if(t == NULL) //tree doesn't exist
  {
   loc = NULL;
   par = NULL;
   return loc;
  }

 if(t -> data == item) //if root node
  {
   loc = t -> root; //set loc to root
   par = NULL; //no parent
   return loc; //return location
  }

  if(item < t -> data)
   {
    ptr = t -> left; //move to left
    save = t -> root; //save parent node
   }

  else
   {
    ptr = t -> right; //move to right
    save = t -> root; //save parent node
   }

 while(ptr != NULL)
  {
   if(item == ptr -> data)
    {
     loc = ptr; //set loc
     par = save; //set parent
     return loc; //return location
    }

   if(item < ptr -> data)
    {
     save = ptr; //save parent
     ptr = ptr -> left; //move to left
    }

   else
    {
     save = ptr; //save parent
     ptr = ptr -> right; //move to right
    }
  }

 loc = NULL; //data not found
 par = save; //save parent
 return loc; //return location
}

void caseA(int Item,tree *&tr) //if node has no or one child
{
 tree *child;
 tree *loc = find(tr,Item); //find location of the item
 if(loc -> left == NULL && loc -> right == NULL) //if no children
  child = NULL;
 else if(loc -> left != NULL) //if left child
  child = loc -> left;
 else
  child = loc -> right;

 if(par != NULL)
  {
   if(loc == par -> left) //if node to be deleted is left of parent
    par -> left = child;
   else
    par -> right = child;
  }

 else
  {
   tr -> root = child; //replace root
   tr = child;
  }
}

void caseB(int Item,tree *&tr) //if node has both children
{
 tree *suc,*loc,*parTemp;
 loc = find(tr,Item); //find location of item
 parTemp = par; //save parent of Item
 suc = loc -> right; //go to right

 while(suc -> left != NULL)
  suc = suc -> left; //go to left

 caseA(suc -> data,tr); //Delete successor using caseA
 par = parTemp; //set parent
 if(par != NULL)
  {
   if(loc == par -> left) //if node to be deleted is left of parent
    par -> left = suc;
   else
    par -> right = suc;
  }

 else
  {
   tr -> root = suc; //replace root
   tr = suc;
  }

 suc -> left = loc -> left; //set left of successor
 suc -> right = loc -> right; //set right of successor
}

tree* remove(int Item,tree *&t)
{
 tree *loc = find(t,Item); //find location
 if(loc == NULL)
  {
   cout << "Item not Found.";
   return loc;
  }

 if(loc -> right != NULL && loc -> left != NULL) //if node has both child
  caseB(Item,t); //call caseB
 else
  caseA(Item,t); //call caseA

 return loc;
}

void insert(tree *&t,int Item)
{
 if(t == NULL) //if tree doesn't exists
  {
   t = new tree; //create a tree
   t -> data = Item; //insert data
   t -> left = NULL;
   t -> right = NULL;
   t -> root = t; //initialize root
   return;
  }

 tree *trav = t;
 if(Item < trav -> data)
  {
   if(trav -> left == NULL)
    {
     create();
     New -> data = Item;
     trav -> left = New;
    }
   else
    insert(trav -> left,Item); //go to left
  }

 else
  {
   if(trav -> right == NULL)
    {
     create();
     New -> data = Item;
     trav -> right = New;
    }
   else
    insert(trav -> right,Item); //go to right
  }
}

void preorder(tree *t)
{
 if(t != NULL)
  {
   cout << t -> data << ' ';
   preorder(t -> left);
   preorder(t -> right);
  }
}

void inorder(tree *t)
{
 if(t != NULL)
  {
   inorder(t -> left);
   cout << t -> data << ' ';
   inorder(t -> right);
  }
}

void postorder(tree *t)
{
 if(t != NULL)
  {
   postorder(t -> left);
   postorder(t -> right);
   cout << t -> data << ' ';
  }
}

int main()
{
 tree *tr1 = NULL;
 int n = 0;
 cout << "Enter Numbers :\n";
 while(n != -999) //create a tree
  {
   cin >> n;
   if(n != -999)
     insert(tr1,n);
  }

 inorder(tr1);

 cout << "\nDelete : ";
 cin >> n;
 tree *temp = remove(n,tr1);
 cout << endl;
 inorder(tr1);
 if(temp != NULL)
  cout << "\nDeleted Item : " << temp -> data;
 getch();
 return 0;
}