Hey all - i am working on an assignment in which i previously created a class to create a Binary Tree. The follow up assignment was to create a Binary Search Tree... but using all the BT methods except an additional couple and obviously a different insert method to stop duplicates.
I have multiple files, but i will post what i think would be needed.
BST.h file - binary search tree class implementation
#ifndef BST_H
#define BST_H
#include "340.h"
#include "BT.h"
template <class T>
class BSTree : public BT<T>
{
public:
void insert(const T&);
void remove(const T&);
bool search(const T&, int&) const;
};
/****************************************************************
FUNCTION: insert()
ARGUMENTS: data value
RETURNS: None
NOTES: inserts the new data item into the tree
****************************************************************/
template <class T>
void BSTree<T>::insert(const T& newItem)
{
cout << "in BST insert()" << endl;
Node<T> * current = BT<T>::root, * parent = NULL;
while (current != NULL && newItem != current->data)
{
parent = current;
if (newItem < current->data)
current = current->left;
else if (newItem > current->data)
current = current->right;
else if (newItem == current->data)
{
cout << "values are the same, should quit" << endl;
return;
}
}
if (current != NULL)
return;
else
{
Node<T> * newNode;
newNode = new Node<T>(newItem);
if (parent == NULL)
BT<T>::root = newNode;
else
{
if (newNode->data < parent->data)
parent->left = newNode;
else if (newNode->data > parent->data)
parent->right = newNode;
else if (newNode->data == parent->data)
{
cout << "values are the same, should quit" << endl;
return;
}
}
return;
}
....other methods and end of .hBT.h - binary tree implementation in class
#ifndef H_BT
#define H_BT
#include "340.h"
#include "Node.h"
template<class T> class BT {
public:
BT() { root = NULL;}
BT(const BT<T>&);
BT& operator=(const BT<T>&);
virtual ~BT() { clear(); }
bool empty() const { return root == 0; }
int size() const { return size(root); }
int height() const { return height(root); }
int leaves() const { return leaves(root); }
virtual void insert(const T& x) { insert(root, x); }
void clear() { clear(root); root = 0; }
bool search(const T&, int&) const;
void preOrder(void (*p)(T&)) { preOrder(root, p); }
void inOrder(void (*p)(T&)) { inOrder(root, p); }
void postOrder(void (*p)(T&)) { postOrder(root, p); }
void printTree(Node<T> *);
Node<T>* root;
private:
int size(Node<T>*) const;
int height(Node<T>*) const;
int leaves(Node<T>*) const;
void insert(Node<T>*&, const T&);
void clear(Node<T>*);
void inOrder(Node<T>*, void (*)(T&));
void preOrder(Node<T>*, void (*)(T&));
void postOrder(Node<T>*, void (*)(T&));
Node<T>* copy(const Node<T>*);
};
...methods....
/****************************************************************
FUNCTION: insert()
ARGUMENTS: data value
RETURNS: None
NOTES: inserts the new data item into the tree
****************************************************************/
template <class T>
void BT<T>::insert(Node<T>*& root, const T& newItem)
{
cout << "in BT insert()" << endl;
Node<T> *newNode = new Node<T>(newItem);
newNode->left = NULL;
newNode->right = NULL;
{
if (root == NULL)
root = newNode;
else if (height(root->left) <= height(root->right))
insert(root->left, newItem);
else
insert(root->right, newItem);
}
}
...methods/end of .h....And within my prog5.cc
/****************************************************************
FILE: prog5.cc
AUTHOR: Anthony Hogan
LOGON ID: Z109079
DUE DATE: 4/11/08
PURPOSE: This contains the need #includes and class definition
so that it is not used more than once in the progam
****************************************************************/
#include "BST.h"
int main()
{
int n = 10;
vector<int> vec;
BST<int> tree;
vector<int>::iterator theIterator = vec.begin();
for (int i = 0; i <= n; i++)
{
vec.push_back( rand() % n + 1 );
tree.insert(rand() % n + 1);
}
bool isFound = false;
double countFound = 0,
searchCount = 0,
precSucc = 0;
for(theIterator = vec.begin(); theIterator != vec.end(); theIterator++)
{
isFound = tree.search(*theIterator,n);
if (isFound == true)
{
countFound++;
isFound = false;
}
searchCount++;
}
tree.printTree(tree.root);
/*
cout << "BST:" << endl;
cout << " Number of Node: SOME VALUE??? " << endl;
cout << " Number of leaves: " << tree.leaves() << endl;
cout << " Height of tree " << tree.height() << endl;
cout << endl;
precSucc = (countFound/searchCount) * 100;
cout << "Ratio of successful searches for 'BST' is " << precSucc << endl;
cout << "Successfull Searches: " << countFound << " Total # search: " << searchCount << endl;
cout << "Average search length for 'BST' is SOME VALUE " << endl;
cout << endl;
cout << "The elements of 'BST' in inOrder:" << endl;
tree.printTree(tree.root);
*/
system("PAUSE");
return 0;
}Okay - those are the files - my problems include:
How do i use this line within prog5.cc to call the BST version of insert()?
tree.insert(rand() % n + 1);Obviously i declared the tree as a BT<T> tree - but if i try declaring my tree as a BST - i get errors:
16 C:\Users\Tony\Documents\school\Fall 08\CSCI 340\assign5\prog5.cc aggregate `BST<int> tree' has incomplete type and cannot be defined
I made the BST class a friend of sorts of the BT class so it should have access to all the methods of the BT class... so should i be declaring it as BST<T> Tree then? Or what? Any ideas?
And my other question is about the BST insert - is this insert going to work? In terms of removing duplicates etc... and making a perfect binary search tree? I think i had it working before but am nervous i may have got it wrong!
Any help would be appreciated!