Thread: Binary Search Tree - object instantiation problem

  1. #1
    Registered User
    Join Date
    Jun 2006
    Posts
    121

    Binary Search Tree - object instantiation problem

    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;
    }

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >//Does it? Really?
    Yes, really. Try adding one and see your errors magically vanish. Perhaps:
    Code:
    BinSearchTree<int> myTree;
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    Thanks, Prelude, I had tried <T> there instead of <int>, and then just given up.

    -Patrick

  4. #4
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    That's basically what template are: a generic class designed to work with any type (int, float, std::string, whatever class you create) that meets its basic requirements. Write it once and use it everywhere. You've already seen (or should see) this in the STL, with std::vector, std::map and so on.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  2. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 02:12 PM
  3. problem in creating a tree
    By Lorin_sz in forum C Programming
    Replies: 1
    Last Post: 09-26-2005, 01:24 PM
  4. binary search tree help
    By noob2c in forum C++ Programming
    Replies: 6
    Last Post: 11-09-2003, 02:51 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM