Code:
#ifndef _bsearchTree_h
#define _bsearchTree_h
#include <iostream>
#include <iomanip>
#include <string>
#include <cassert>
using namespace std;
template<class KeyType, class DataType>
struct mypair
{ KeyType key;
DataType data;
};
template<class KeyType, class DataType>
struct node
{ mypair<KeyType, DataType> element;
node<KeyType, DataType>* left;
node<KeyType, DataType>* right;
};
template<class KeyType, class DataType>
class bsearchTree
{
public:
typedef node<KeyType, DataType>* Ptr;
bsearchTree(); //defined
//default constructor - constructs empty tree
~bsearchTree();//defined
//destructor. Deletes all nodes in the tree. Uses a
//recursive private member function.
bool empty();//defined
//returns true if and only if the tree is empty
long int size();//defined
//returns the number of nodes in the tree. You cannot
//just add a data member to the class to keep track of
//the size. Uses a recursive private member function.
long int height();//defined
//returns the height of the tree. Uses a recursive
//private member function. Make the height of an empty
//tree to be -1 rather than 0 as done in the book.
Ptr find(KeyType k);//defined
//searches the tree for the key. If the key is found it
//returns a pointer to the node containing the key;
//otherwise it returns NULL. Uses private member function
//findPosition.
void insert(const mypair<KeyType, DataType>& p);//defined
//checks whether a pair with the key part of p is already
//in the tree. If so then it prints an error message and
//does not insert the pair. If not then it inserts the pair.
//Uses private member function findPosition.
DataType& data(Ptr ptr);//defined
//returns a referenece to the data part of the element
//pointed to by p. This will allow the user to modify the
//data and provides some of the functionality that a true
//iterator would provide.
void print();//defined
//outputs the elements in sorted order of the keys, i.e.
//inorder. Output each element on a separate line, i.e.
//the output is done as cout<<ptr->element<<endl. Do not
//directly output the key and data. This way the user can
//overload the << operator for the pairs to control the output
//however desired. Uses a recursive private member function.
private:
Ptr root;
void findPosition(const KeyType& k, Ptr& ptr, bool& found);
//Searches for key, k, in the tree. If found then
//sets ptr to point to the node containg the key and sets
//found to true. If not found then sets ptr to point to the
//node such that an element with this key should be inserted
//directly below the node (if tree is empty then sets ptr
//to NULL) and sets found to false.
//other private member function prototypes
void destroy(Ptr &);//defined
void inorder(Ptr);//defined
long int sizeCount(Ptr );
long int heightCount(Ptr);//defined
long int maxa(long int,long int);//defined
};
ostream& operator<<(ostream& os, const mypair<string, int> p)
{
//Ouput the string and then enough space to reach column 20
//and then output the integer in a field of width 5. This will
//allow all the words and frequencies to line up nicely as shown
//in the write-up.
os<<p.key<<" "<<setw(5)<<p.data;
return os;
}
template<class KeyType,class DataType>
bsearchTree<KeyType,DataType>::bsearchTree():
root(NULL)
{
}
template<class KeyType,class DataType>
bsearchTree<KeyType,DataType>::~bsearchTree()
{
destroy(root);
}
template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::destroy(node<KeyType, DataType>* &p)
{
if(p != NULL)
{
destroy(p->left);
destroy(p->right);
delete p;
p=NULL;
}
}
template<class KeyType,class DataType>
bool bsearchTree<KeyType,DataType>::empty()
{
if(root == NULL)return true;
}
template<class KeyType,class DataType>
DataType& bsearchTree<KeyType,DataType>::data(node<KeyType, DataType>* ptr)
{
return (ptr->element).data;
}
template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::print()
{
inorder(root);
}
template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::inorder(node<KeyType, DataType>* p)
{
if(p != NULL)
{
inorder(p->left);
cout<<p->element<<endl;
inorder(p->right);
}
}
template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::height()
{
return heightCount(root);
}
template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::size()
{
return sizeCount(root);
}
template<class KeyType,class DataType>
node<KeyType, DataType>* bsearchTree<KeyType,DataType>::find(KeyType k)
{
node<KeyType, DataType>* ptr;
bool found;
findPosition(k,ptr,found);
if(found == true)
{
ptr->element.data--;
return ptr;
}
return NULL;
}
template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::insert(const mypair<KeyType,DataType>& p)
{
node<KeyType,DataType>* ptr;
node<KeyType,DataType>* ptr1;
bool found=false;
findPosition(p.key,ptr,found);
if(found == true)cerr<<"duplicates not allowed."<<endl;
if(found == false && ptr == NULL)//this means tree is empty
{
ptr = new node<KeyType,DataType>;
assert(ptr != NULL);
root = ptr;
ptr->element.key=p.key;
ptr->element.data=1;
ptr->left=NULL;
ptr->right=NULL;
}
else
{
if(found == false && ptr != NULL)//key is unique
{
if(ptr->element.key < p.key)
{
ptr1=ptr->left;
ptr1= new node<KeyType,DataType>;
assert(ptr1!=NULL);
ptr1->element.key=p.key;
ptr1->element.data=1;
ptr1->left=NULL;
ptr1->right=NULL;
}
else
{
ptr1=ptr->right;
ptr1= new node<KeyType,DataType>;
assert(ptr1!=NULL);
ptr1->element.key=p.key;
ptr1->element.data=1;
ptr1->left=NULL;
ptr1->right=NULL;
}
}
}
}
template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::findPosition(const KeyType& k, node<KeyType, DataType>* &ptr, bool& found)
{
node<KeyType,DataType>* current;
node<KeyType,DataType>* follow;
if(root == NULL)
{
found = false;
ptr=NULL;
}
else
{
current = root;
while(current != NULL && found != true)
{
follow=current;
if(current->element.key == k)
{
found = true;
current->element.data++;
ptr=current;
}
else
if(current->element.key > k)current=current->left;
else
current=current->right;
}//end of while
ptr=follow;
}
}
template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::heightCount(node<KeyType, DataType>* p)
{
if(p == NULL)return -1;
else
return 1 + maxa(heightCount(p->left),heightCount(p->right));
}
template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::maxa(long int x, long int y)
{
return(x > y ? x : y);
}
template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::sizeCount(node<KeyType,DataType>* p)
{
if( p == NULL)return 0;
return sizeCount( p->left ) + 1 + sizeCount( p->right );
}
#endif