Hi again... sorry to bother you guys so much, but as I've said before, my previous C++ courses did NOT prepare me at all for this data structures class. The assignment is to create a binary search tree with random int values and alternately apply insertions and deletions of random elements. I've got an idea, a basic outline, but I can't seem to instantiate a tree object. I've scoured the book and internet forums, but can't seem to find anything of help. The book assumes we know a lot more than we do; this university's curriculum is awful! Code below, I know I have a lot of garbage in it, but I wanted to narrow down as I decided what I needed and didn't need. Thanks for any help provided! Here are the errors I've been getting:
c:\Documents and Settings\Pbrooks4\My Documents\Visual Studio Projects\Kellett_CS3330_6\Source1.cpp(178): error C2133: 'myTree' : unknown size
//Why in the world would I need to declare a size????
c:\Documents and Settings\Pbrooks4\My Documents\Visual Studio Projects\Kellett_CS3330_6\Source1.cpp(178): error C2262: 'myTree' : cannot be destroyed
//Why not? I've declared a destructor
c:\Documents and Settings\Pbrooks4\My Documents\Visual Studio Projects\Kellett_CS3330_6\Source1.cpp(178): error C2512: 'BinSearchTree' : no appropriate default constructor available
//No? How do you figure?
c:\Documents and Settings\Pbrooks4\My Documents\Visual Studio Projects\Kellett_CS3330_6\Source1.cpp(185): error C2662: 'BinSearchTree<T>::insert' : cannot convert 'this' pointer from 'BinSearchTree' to 'BinSearchTree<T> &'
//This when I tried myTree.insert(nodeVal)... what does this error mean?
c:\Documents and Settings\Pbrooks4\My Documents\Visual Studio Projects\Kellett_CS3330_6\Source1.cpp(178): error C2955: 'BinSearchTree' : use of class template requires template argument list
//Does it? Really?
c:\Documents and Settings\Pbrooks4\My Documents\Visual Studio Projects\Kellett_CS3330_6\Source1.cpp(185): error C3861: 'myTree': identifier not found, even with argument-dependent lookup
//Why won't it accept this instantiation??????
Code:
#include <cmath>
#include <iostream>
#include <ctime>
#include <queue>
#include <stack>
using namespace std;
template<class T>
class Stack : public stack<T>
{
public:
T pop()
{
T tmp = top();
stack<T>::pop();
return tmp;
}
};
template<class T>
class Queue: public queue<T>
{
public:
T dequeue()
{
T tmp = front();
queue<T>::pop();
return tmp;
}
void enqueue(const T& el)
{
push(el);
}
};
template<class T>
class BinSearchNode
{
public:
BinSearchNode()
{
left = right = 0;
}
BinSearchNode(const T& el, BinSearchNode *l = 0, BinSearchNode *r = 0)
{
key = el;
left = l;
right = r;
}
T key;
BinSearchNode *left, *right;
};
template<class T>
class BinSearchTree
{
public:
BinSearchTree() //is this not the constructor????
{
root = 0;
}
~BinSearchTree()
{
clear();
}
void clear()
{
clear(root);
root = 0;
}
bool isEmpty() const
{
return root == 0;
}
void preorder()
{
preorder(root);
}
void inorder()
{
inorder(root);
}
void postorder()
{
postorder(root);
}
T* search(const T& el) const
{
return search(root, el);
}
void breadthFirst();
void interativePreorder();
void interativeInorder();
void interativePostorder();
void MorrisInorder();
void insert(const T&);
void deleteByMerging(BinSearchNode<T>*&);
void balance(T*, int, int);
//......
protected:
BinSearchNode<T>* root;
void clear(BinSearchNode<T>*);
T* search(BinSearchNode<T>*, const T&) const;
void preorder(BinSearchNode<T>*);
void inorder(BinSearchNode<T>*);
void postorder(BinSearchNode<T>*);
virtual void visit(BinSearchNode<T>* p)
{
cout << p->key << ' ';
}
//..........
};
template<class T>
T* BinSearchTree<T>::search(BinSearchNode<T>* p, const T& el) const
{
while(p != 0)
if(el == p->key)
return &p->key;
else if(el < p->key)
p = p->left;
else p = p->right;
return 0;
}
template<class T>
void deleteByCopying(BinSearchNode<T>*& node)
{
BinSearchNode<T> *previous, *tmp = node;
if(node->right == 0)
node = node->left;
else if(node->left == 0)
node = node->right;
else
{
tmp = node->left;
previous = node;
while(tmp->right != 0)
{
previous = tmp;
tmp = tmp->right;
}
node->key = tmp->key;
if(previous == node)
previous->left = tmp->left;
else
previous->right = tmp->left;
}
delete tmp;
}
template<class T>
void BinSearchTree<T>::insert(const T& el)
{
BinSearchNode<T> *p = root, *prev = 0;
while(p != 0)
{
prev = p;
if(p->key < el)
p = p->right;
else
p = p->left;
}
if(root == 0)
root = new BinSearchNode<T>(el);
else if(prev->key < el)
prev->right = new BinSearchNode<T>(el);
else
prev->left = new BinSearchNode<T>(el);
}
int main()
{
int treeHeight, i, nodeVal;
BinSearchTree myTree; //trouble!
cout << "Enter the height of the tree you would like to create: ";
cin >> treeHeight;
srand((unsigned)time(0));
for(i = 1; i <= pow(2, treeHeight); i++)
{
nodeVal = (rand()%98)+1;
myTree.insert(nodeVal);
}
return 0;
}