C++ Homework - Binary Search Tree Help

Question

For starters this is homework, I just really need help with a binary search tree.

The program is to display polymorphism, using person as an abstract base class, and other types of people which inherit Person. Each person has a last name, and I am trying to use a binary search tree to alphabetize the people by last name.

I have written what I think should be an acceptable Binary Search Tree, But I am still getting errors. The binary search tree only needs to have an insert and traverse function. Which should be recursive.

The error I am getting is: Error 19 error C4430: missing type specifier - int assumed bst.cpp

This occurs at line 51, 64 and 70. Here is my code:

Header File:

#ifndef BST_H
#define BST_H

template <class T>
class BST
{
    private:
        class BinNode
        {
            public:
                BinNode(void);
                BinNode(T node);

                BinNode *left;
                BinNode *right;
                T data;
        };

        BinNode* root;

    public:
        BST();   
        ~BST();

        void insert(const T &);
        void traverse();
        void visit(BinNode *);


    //Utlity Functions
    private:
        void insertAux(BinNode* &, BinNode *);
        void traverseAux(BinNode *, ostream &);
};

#include "BST.cpp"
#endif

Implementation File:

 #include <iostream>
#include <string>

using namespace std;

#ifdef BST_H

template <class T>
BST<T>::BinNode::BinNode()
{
    left = right = 0;
}

template <class T>
BST<T>::BinNode::BinNode(T node)
{
   left = right = 0;
   data = node;
}

template <class T>
BST<T>::BST()
{
    root = 0;
}

template <class T>
void BST<T>::insertAux(T i, BinNode* &subRoot)
{
    //inserts into empty tree
    if(subRoot == 0)
        subRoot = new BinNode(i);
    //less then the node
    else if(i<subRoot->data)
        insertAux(i, subRoot->left);
    //greater then node
    else
        insertAux(i, subRoot->right);
}

template <class T>
void BST<T>::insert(const T &i)
{
    insertAux(T i, root)
}

template <class T>
BST<T>::traverse()
{
    traverseAux(root);
}

template <class T>
BST<T>::traverseAux(BinNode *subRoot)
{
    if (subRoot == 0)
        return;
    else
    {
        traverseAux(subRoot->left);
        visit(subRoot);
        traverseAux(subRoot->right);
    }       
}

template <class T>
BST<T>::visit(BinNode *b)
{
    cout << b->data << endl;
}

#endif

If anyone could take a quick glance at this for me and give me some tips? It is really confusing me right now. Thanks!

Answer 1

You omitted the return type on some of your function definitions.

For example:

template <class T>
BST<T>::traverse()
{
    traverseAux(root);
}

should be:

template <class T>
void BST<T>::traverse()
{
    traverseAux(root);
}