search tree

[mpolet]

Hi,

I'm a student trying to program a searchtree with the class TreeSet and Node.
The comment is in dutch, so just ignore that. I don't really need help with functionality, just with c++. What do all these errors mean?
Like blablabla is undeclared in the declaration of nodes. I don't have any experience with pointers and stuff. I get the concept. Still I don't get why my compiler is complaining...

In file included from treesettest.h:17,
treeset.h:56: error: `template<class T> class TreeSet' used without template parameters
treeset.h:57: error: non-member function `bool contains(const T&)' cannot have `const' method qualifier
treeset.h: In function `bool contains(const T&)':
treeset.h:58: error: `n' undeclared (first use this function)
treeset.h:58: error: (Each undeclared identifier is reported only once for each function it appears in.)
treeset.h: At global scope:
treeset.h:75: error: `template<class T> class TreeSet' used without template parameters
treeset.h: In function `void remove(const T&)':
treeset.h:84: error: `Node' undeclared (first use this function)
treeset.h:84: error: `currentNode' undeclared (first use this function)
treeset.h:85: error: `parentNode' undeclared (first use this function)
treeset.h:86: error: invalid use of `this' in non-member function
treeset.h:175: error: `rightChild' undeclared (first use this function)
treeset.h:177: error: `leftChild' undeclared (first use this function)
treeset.h:216: error: missing template arguments before "leftTree"
treeset.h:216: error: expected `;' before "leftTree"
treeset.h:218: error: `leftTree' undeclared (first use this function)
...
more of the same
...
BUILD FAILED (exit value 2, total time: 2s) 

This is my code:

#ifndef _TREESET_H
#define	_TREESET_H




template <typename T>
class TreeSet
{
private:
class Node
{
private:
    T _data;
public:

    TreeSet * left;
    TreeSet * right;

    Node(T& data)
    {
        _data = data;
        left = 0;
        right = 0;
    }

    T getData(){return _data;};
    void setData(const T& d){_data = d;};

};

Node * n;

public:
    TreeSet(){n->setData(NULL);};

    TreeSet(const T& data){n->setData(data);};

    ~TreeSet();



    bool contains(const T &data) const;

    void add(const T &data);

    void remove(const T& data);

    void clear();

    template <typename V>
    void visit(V &visitor);
};

template <typename T>
bool TreeSet::contains(const T& data) const
{
    if(n == 0)
        return false;
    
    if(n->getData() == data)
        return true;
    else if(n->getData() < data)
    {
        if(n->right != 0) 
            return n->right->contains(data);
        return false;
    }
    if(n->left != 0)
        return n->left->contains(data);
    return false;
}

template <typename T>
void TreeSet::remove(const T& data)
{
    
    if(contains(data))
    {
        //de Node bestaat zeker

        bool found = false;
        bool isRightChild;
        Node * currentNode;
        Node * parentNode;
        currentNode = this->n;

        if(currentNode->getData() == data)
        {
            found = true;
        }

        //zoeken naar te verwijderen Node
        while(!found)
        {
            if(currentNode->getData() == data)
            {
                found = true;
            }
            else
            {
                parentNode = currentNode;
                if(currentNode->getData() < data)
                {
                    currentNode = currentNode->right->n;
                    isRightChild = true;
                }
                else
                {
                    currentNode = currentNode->left->n;
                    isRightChild = false;
                }
            }
        }

        // 1. blad
        // 2. heeft 1 kind
        // 3. heeft 2 kinderen



        if( currentNode->left == 0 && currentNode->right == 0)
        {
            // 1. blad
            if(isRightChild)
                //Huidige Node is een rechter kind
                parentNode->right = 0;
            else
                //Huidige Node is een linker kind
                parentNode->left = 0;
            delete currentNode;
            return;
        }


        if((currentNode->left == 0 && currentNode->right != 0)|| (currentNode->left != 0 && currentNode->right == 0))
        {
            // 2. heeft 1 kind
            if(currentNode->left == 0 && currentNode->right != 0)
            {
                //Huidige Node heeft een rechter kind
                if(isRightChild)
                {
                    //Huidige Node is een rechter kind
                    parentNode->right = currentNode->right;
                }
                else
                {
                    //Huidige Node is een linker kind
                    parentNode->left = currentNode->right;
                }
            }
            else
            {
                //Huidige Node heeft een linker kind
                if(isRightChild)
                {
                    //Huidige Node is een rechter kind
                    parentNode->right = currentNode->left;
                }
                else
                {
                    //Huidige Node is een linker kind
                    parentNode->left = currentNode->left;
                }
            }
            delete currentNode;
            return;
        }

        // deze controle is nutteloos, maar ik doe ze lekker toch,... nè!
        if (currentNode->left != 0 && currentNode->right != 0)
        {
            // 3. heeft 2 kinderen
            Node * rightChild;
            rightChild = currentNode->right->n;
            Node * leftChild;
            leftChild = currentNode->left->n;
            if((rightChild->left == 0) && (rightChild->right == 0))
            {
                //isRightChild heeft geen kinderen; nice replacen die shit
                if(isRightChild)
                {
                    parentNode->right = currentNode->right;
                }
                else
                {
                    parentNode->left = currentNode->right;
                }
                delete currentNode;
                return;
            }
            if((leftChild->left == 0) && (leftChild->right == 0))
            {
                //linkerkind heeft geen kinderen; nice replacen die shit
                if(isRightChild)
                {
                    parentNode->right = currentNode->left;
                }
                else
                {
                    parentNode->left = currentNode->left;
                }
                delete currentNode;
                return;
            }

            //zowel linkerkind als rechter kind heeft kinderen

            //parentNode laten wijzen naar isRightChild vervangen
            //bij isRightChild zoeken totdat het geen linkerkind heeft
            
            //en die null pointer laten wijzen naar linkerkind

            parentNode->right = currentNode->right;
            TreeSet leftTree = currentNode->left;

            while(leftTree != 0)
            {
                leftTree = leftTree->n->left;
            }
            leftTree->n->left = currentNode->left;
            delete currentNode;            
        }
    }
}

template <typename T>
void TreeSet::add(const T &data)
{
   if(!contains(data))
       //slecht dat hij deze controle recursief (telkens opnieuw) controleert,
       //opl eventueel apparte methode die recursief wordt gebruikt

   {
       if(n->getData() < data)
           if(n->right != 0)
               n->right->add(data);
           else
               n->right = new TreeSet(data);
       else
           if(n->left != 0)
               n->left->add(data);
           else
               n->left = new TreeSet(data);
   }
}

template <typename T>
void TreeSet::clear()
{
    if(n->right != 0)
    {
        n->right->clear();
        delete n->right;
    }

    if(n->left != 0)
    {
        n->left->clear();
        delete n->left;
    }

    delete n;

    //huidige treeset moet niet delete worden, Node wel
    //zal n bij huidige deze treeset dan wijzen naar NULL?
}
#endif 

Thx for the help.

Regards

[Galik]

TreeSet is a template so you need to use parameters every time you declare one.

Your lines 17 & 18 above should probably be something like this:

    TreeSet<T> * left; 
    TreeSet<T> * right;

[Denis]

It should be

template <typename T>
bool TreeSet<T>::contains(const T& data) const

Other part of source code you can change by your self

[mpolet]

Thx, that helped a lot