//Tree.h
////////////////////////////////////////////////////////////////////////////////
//Class Name :Tree 
//Owner :Mohamed Talaat 
//Creation Date : 20 April 2006 
//Function : implementing BST 
////////////////////////////////////////////////////////////////////////////////
#ifndef TREE
#define TREE
//include header files
#include<iostream>
#include<string>
//include namesapce
using namespace std;
////////////////////////////////////////////////////////////////////////////////
struct node
{
string data;
node *left;
node *right;
};
////////////////////////////////////////////////////////////////////////////////
//class defination
class Tree
{
public:
Tree();
~Tree();
bool IsEmpty();
int LengthIs();
void RetrieveItem(string& item, bool found);
void InsertItem(string item);
void DeleteItem(string item);
void print(std::ofstream& outFile);
private:
node *root;
};//end of class Tree
#endif

//Tree.cpp
////////////////////////////////////////////////////////////////////////////////
//Class Name :Tree 
//Owner :Mohamed Talaat 
//Creation Date : 20 April 2006 
//Function : implementing BST 
////////////////////////////////////////////////////////////////////////////////
//include header files
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<string>
#include"Tree.h"
//include namespace
using namespace std;
////////////////////////////////////////////////////////////////////////////////
//function Name : Tree()
//purpose : default constructor
//input :
//output :
////////////////////////////////////////////////////////////////////////////////
Tree::Tree()
{
root = NULL;
}
////////////////////////////////////////////////////////////////////////////////
//function Name : Tree()
//purpose : default destructor
//input :
//output :
////////////////////////////////////////////////////////////////////////////////
void Destroy(node* tree);
Tree::~Tree()
{
Destroy(root);
}
void Destroy(node* tree)
{
if( tree != NULL)
{
Destroy(tree->left);
Destroy(tree->right);
delete tree;
}
}
////////////////////////////////////////////////////////////////////////////////
//function Name : IsEmpty()
//purpose : check if there is no item in the linked list
//input :
//output : true if the list is empty , false otherwise
////////////////////////////////////////////////////////////////////////////////
bool Tree::IsEmpty()
{
return root == NULL;
}
////////////////////////////////////////////////////////////////////////////////
//function Name : LengthIs()
//purpose : dtermine the length of a tree
//input : 
//output : number of elements in the tree
////////////////////////////////////////////////////////////////////////////////
int CountNodes(node *tree);
int Tree::LengthIs()
{
return CountNodes(root);
}
int CountNodes(node *tree)
{
if ( tree == NULL)
return 0;
else
return CountNodes(tree->left)+CountNodes(tree->right)+1;
}
////////////////////////////////////////////////////////////////////////////////
//function Name : RetrieveItem()
//purpose : retrieve the data whose key matches item's key ( if present) 
//input : key member of data.
//output : data will be copied to item and found = true if found
// othewise the item will kpet unchanged and found = false
////////////////////////////////////////////////////////////////////////////////
void Retrieve(node *tree, string& item , bool& found);
void Tree::RetrieveItem(string& item, bool found)
{
Retrieve(root,item,found);
}
void Retrieve(node *tree, string& item , bool& found)
{
if ( tree == NULL)
found = false;
else if (item< tree->data)
Retrieve(tree->left,item,found);
else if (item> tree->data)
Retrieve(tree->right,item,found);
else
{
item = tree->data;
found = false;
}
}
////////////////////////////////////////////////////////////////////////////////
//function Name : insertItem()
//purpose : insert an item to the tree
//input : item : the item which needed to be added 
//output : 
////////////////////////////////////////////////////////////////////////////////
void findnode(node* tree, string item, node*& nodeptr, node*& parentptr);
void Tree::InsertItem(string item)
{
node* newnode;
node* nodeptr;
node* parentptr;
newnode = new node;
newnode->data = item;
newnode->left = NULL;
newnode->right = NULL;
findnode(root,item,nodeptr,parentptr);
if ( parentptr==NULL )
root=newnode;
if ( item < parentptr->data )
parentptr->left=newnode;
else
parentptr->right = newnode;
}
void findnode(node* tree, string item, node*& nodeptr, node*& parentptr)
{
nodeptr = tree;
parentptr = NULL;
bool found = false;
while (nodeptr != NULL && !found )
{
if ( item< nodeptr->data)
{
parentptr = nodeptr;
nodeptr = nodeptr->left;
}
else if ( item> nodeptr->data )
{
parentptr = nodeptr;
nodeptr = nodeptr->right;
}
else
{
found = true;
}
}
}
////////////////////////////////////////////////////////////////////////////////
//function Name : DeleteItem()
//purpose : delete an item from the tree
//input : item : the item which needed to be deleted 
//output : 
////////////////////////////////////////////////////////////////////////////////
void DeleteNode(node*& tree);
void Delete(node*& tree, string item);
void Tree::DeleteItem(string item)
{
Delete(root,item);
}
void Delete(node*& tree, string item)
{
if ( item < tree->data)
Delete(tree->left,item);
else if ( item > tree->data)
Delete(tree->right,item);
else
DeleteNode(tree);
}
void GetPredecessor(node* tree, string info);
void DeleteNode(node*& tree)
{
string info;
node* temp;
temp=tree;
if (tree->left==NULL)
{
tree=tree->right;
delete temp;
}
else if (tree->right==NULL)
{
tree=tree->left;
delete temp;
}
else
{
GetPredecessor(tree->left,info);
tree->data=info;
Delete(tree->left,info);
}
}
void GetPredecessor(node* tree, string info)
{
while (tree->right!=NULL)
tree = tree->right;
info = tree->data;
}
////////////////////////////////////////////////////////////////////////////////
//function Name : print()
//purpose : save the Tree's data in a file
//input : outFile : the file where the data will be saved
//output : 
////////////////////////////////////////////////////////////////////////////////
void PrintTree(node* tree, std::ofstream& outFile);
void Tree::print(std::ofstream& outFile)
{
PrintTree(root,outFile);
}
void PrintTree(node* tree, std::ofstream& outFile)
{
if ( tree != NULL )
{
PrintTree(tree->left, outFile);
outFile<<tree->data;
PrintTree(tree->right, outFile);
}
}

//main.cpp
#include<iostream>
#include<conio.h>
#include<fstream>
#include<cstdlib>
#include<string>
#include"Tree.h"
using namespace std;
void main()
{
Tree mytree;
mytree.InsertItem("HI");
int n = mytree.LengthIs();
cout<<"number of elements in the tree is:"<<n<<endl;
}

void Insert(node* tree , string item);
void Tree::InsertItem(string item)
{
Insert(root,item);
}
void Insert(node* tree , string item)
{
if ( tree == NULL)
{
tree = new node;
tree->data = item;
tree->left = NULL;
tree->right = NULL;
}
else if ( item< tree->data)
Insert(tree->left,item);
else 
Insert(tree->right,item);
}

//main.cpp
#include<iostream>
#include"Tree.h"
using namespace std;

int main()
{

  cout << "Instantiating mytree" << endl;
  Tree mytree;

  cout << "Calling InsertItem(\"HI\")" << endl;
  mytree.InsertItem("HI");

  cout << "Calling LengthIs()" << endl;

  int n = mytree.LengthIs();
  cout<<"number of elements in the tree is:"<<n<<endl;
  return 0;
}

void Tree::InsertItem(string item)
{
  cout << "In InsertItem() item <" << item << ">" << endl;
  node* newnode;
  node* nodeptr;
  node* parentptr;
  newnode = new node;
  newnode->data = item;
  newnode->left = NULL;
  newnode->right = NULL;
  cout << "Calling findnode()" << endl;
  findnode(root,item,nodeptr,parentptr);
  cout << "Back from findnode()" << endl;
     
  if ( parentptr==NULL ) {
    cout << "parentptr == NULL" << endl;
    root=newnode;
  }

  if ( item < parentptr->data ) {
    cout << "item < parentptr->data" << endl;
    parentptr->left=newnode;
  }
  else {
    cout << "item not less than parentptr->data" << endl;
    parentptr->right = newnode;
  }

}

  if ( parentptr==NULL ) {
    cout << "parentptr == NULL" << endl;
    root=newnode;
    cout << "set root equal to newnode" << endl;
  }

  cout << "parentptr: " << parentptr << endl;
  if ( item < parentptr->data ) {
    cout << "item < parentptr->data" << endl;
    parentptr->left=newnode;
  }