C++ binary search and hash table

I need some help with several Data structures assignments. One is a binary search tree and testing the functions. I need help figuring out

Here is the hash table chaining type need help completing

#include <iostream>
#include <fstream>
#include "linkedlist.h"
#include "stock.h"

using namespace std;

template <typename T>
class hashtable
{
public:
hashtable(int size = 100);
~hashtable();
void remove(const T & item);
void insert(const T & item);
void display(ostream& os)const;
T * search(const T & item) const;
void writetofile(ostream&os) const;
private:
int hashtable size;
linklist<T> * table;
};
template <typename T>
hashtable<T>::hashtable(int size)
{
table = new linkedlist<T> [size];
hashtable_size = size;
}
template <typename T>
hashtable<T>::~hashtable()
{
delete [] table;
}
template <typename T>
void hashtable<T>::insert(const T & item)
{
int index;
index = item.hash(hashtable_size);
table[index].insertFront(item);
}
template<typename T>
void hashtable<T>::remove(const T & item)
{
int index;
index = item.hash(hashtable_size);
if(table[index].search(item))
table[item.hash(hashtable_size)].deleteNode(item);

}
template<typename T>
void hashtable<T>::writetofile(ostream &os)
{
os << table;
}
template<typename T>
void hashtable<T>::display(ostream &os)
{

}
template<typename T>
T* hashtable<T>::search(const T &item)
{

}

Here is binarysearch tree




#include<iostream>

using namespace std;

template <typename T>
struct node
{
T data;
node<T> *left;
node<T> *right;
};

template <typename T>
class bst
{
private:
node<T> *root ;
int count;
int heightTree(node<T> * root) const;
bool searchTree(node<T>* &root, const T& item);
void insertTree(node<T>* &root, const T& item);
void inorderTree(node<T> *root);//Function to do an inorder traversal of binary tree to which r points
void preorderTree(node<T> *root);//Function to do an preorder traversal of binary tree to which r points
void postorderTree(node<T> *root);//Function to do an postorder traversal of binary tree to which r points
void deleteFromTree(node<T> *&root);//Function to delet a specified node from the tree
public:
bst();//default constructor to create a binary search tree
~bst();//destructor to deallocate all nodes
void insert(const T & item);// insert a new item into appropriate location
bool search(const T& item);//search to determine wheter item is in a tree
void destroy(node<T> * &root);//destroy all nodes in the tree. leaving an empty tree
void deletenode(const T & item);//Find node and delete
void inorder();//display using inorder traversal method
void preorder();//display using preorder traversal method
void postorder();//display using postorder traversal method
int height() const;//return the height of the tree
bool isEmpty();//Function to determine if the binary search tree is empty
};
template <typename T>
bst<T>::bst()
//default constructor creates empty tree
//Postcondition: Sets root to NULL and count to 0
{
root = NULL;
int count = 0;
}
template<typename T>
bst<T>::~bst()
//Destructor
//Deallocates the memory space occupied by the binary tree.
{
destroy(root);
}
template<typename T>
int bst<T>::height()const
{

return heightTree(root);
}
template <typename T>
bool bst<T>::search(const T& item)
//Function to determine if item is in the bst.

{
return searchTree(root, item);

}
template <typename T>
void bst<T>::deletenode(const T & item)
//Function to delete item from the bst
//Postcondition: If a node with the same info as item
//is found, it is deleted from the bst
{
node<T> *current; //pointer to traverse the tree
node<T> *trailCurrent; //pointer behind current

bool found = false;

if(root == NULL)
cout<<"Cannot delete from the empty tree."<<endl;
else
{
current = root;
trailCurrent = root;

while(current != NULL && !found)
{
if(current->data == item)
found = true;
else
{
trailCurrent = current;

if(current->data > item)
current = current->left;
else
current = current->right;
}
}//end while

if(current == NULL)
cout<<"The delete item is not in the tree."<<endl;
else
if(found)
{
if(current == root)
deleteFromTree(root);
else
if(trailCurrent->data > item)
deleteFromTree(trailCurrent->left);
else
deleteFromTree(trailCurrent->right);
}
}
}
template <typename T>
void deleteFromTree(node<T> *& root)
{

node<T> *current; //pointer to traverse
//the tree
node<T> *trailCurrent; //pointer behind current
node<T> *temp; //pointer to delete the node

if(r == NULL)
cerr<<"Error: The node to be deleted is NULL."
<<endl;
else if(r->left == NULL && r->right == NULL)
{
temp = r;
r = NULL;
delete temp;
}
else if(r->left == NULL)
{
temp = r;
r = temp->right;
delete temp;
}
else if(r->right == NULL)
{
temp = r;
r = temp->left;
delete temp;
}
else
{
current = r->left;
trailCurrent = NULL;

while(current->right != NULL)
{
trailCurrent = current;
current = current->right;
}//end while

r->data = current->data;

if(trailCurrent == NULL) //current did not move;
//current == p->left; adjust p
r->left = current->left;
else
trailCurrent->right = current->left;

delete current;
}//end else
}//end deleteFromTree
template <typename T>
bool bst<T>::isEmpty()
//Function to determine if the bst is empty.
//Postcondition: Returns true if the bst is empty otherwise, returns false.
{
if(root==NULL)
return true;
else
return false;
}
template <typename T>
void bst<T>::inorder()

{
inorderTree(root);
}
template <typename T>
void bst<T>:reorder()
{
preorderTree(root);
}
template <typename T>
void bst<T>:ostorder()
{
postorderTree(root);
}
template <typename T>
void bst<T>::inorderTree(node<T> *root)
//Function to do an inorder traversal of the binary
//tree to which r points.
//Postcondition: The nodes of the binary tree to which r
//points are output in the inorder sequence
{

if(root != NULL)
{
inorderTree(root->left);
cout<<root->data<<" ";
inorderTree(root->right);
}
}
template <typename T>
void bst<T>:reorderTree(node<T> *root)
//Function to do an preorder traversal of the binary
//tree to which r points.
//Postcondition: The nodes of the binary tree to which r
//points are output in the preorder sequence.
{

if(root != NULL)
{
cout<<root->data<<" ";
preorderTree(root->left);
preorderTree(root->right);
}
}
template <typename T>
void bst<T>:ostorderTree(node<T> *root)
//Function to do an postorder traversal of the binary
//tree to which r points.
//Postcondition: The nodes of the binary tree to which r
//points are output in the inorder sequence.
{

if(root != NULL)
{
postorderTree(root->left);
postorderTree(root->right);
cout<<root->data<<" ";
}
}
template <typename T>
void bst<T>::insert(const T &item)
{
insertTree(root, item);
}
template <typename T>
bool bst<T>::searchTree(node<T> * &root, const T & item)
{
bool found;
if(root==NULL)
{
found = false;
}
else if (item < root->data)
{
found = searchTree(root -> left, item);
}
else if (root -> data < item)

{
found = searchTree(root -> right, item);
}
else
{
found = true;
}
return found;

}
template <typename T>
void bst<T>::insertTree(node<T> *&root,const T & item)
{

if(root == NULL)
{
root = new node<T>;
root->data = item;
root->left = NULL;
root->right = NULL;
}
else if (item < root->data)
{
insertTree(root->right, item);
}
else
{
insertTree(root->left, item);
}

}//end insert
template <typename T>
int bst<T>::heightTree(node<T> * root)const
{
int result = 0;
if (root != 0)
{
int lh = heightTree(root->left);
int rh = heightTree(root->right);
if (lh > rh)
{
result = 1 + lh;
}
else
{
result = 1 + rh;
}

}
return result;

}
template <typename T>
void bst<T>::destroy(node <T> * &root)
{
if (root != 0)
{
destroy(root->left);
destroy(root->right);
delete root;
root = NULL;
}
}

 

code...tags...

[ code] [/co de]

 

Isn't there a binary search in STL?

Or its quite easy to create a tree or heap in STL?

 

You could use the standard C function qsort - see man page for details.