Binary Search Tree Manipulation

[RaineShadow]

I have a program assignment that I was given the .h file for and was supposed to make the .cpp file insert, remove and so on the with the tree. I'm having problems trying to call the functions in the .h file in my .cpp file. Here is what my .h file is.

mybst.h

#ifndef MY_BINARY_SEARCH_TREE
#define MY_BINARY_SEARCH_TREE
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;

template <typename T>
struct BinaryNode
{
   T data;
   BinaryNode<T> *left, *right;
   BinaryNode()
   {
      left = right = 0;
   }
   BinaryNode(const T& value): data(value)
   {
      left = right = 0;
   }
};

template <typename T>
class BST
{
protected:
   BinaryNode<T> *root;
public:
   explicit BST() { root = 0; }

   BinaryNode<T> *getroot() { return root; }

   virtual ~BST() { nuke( root ); }

   bool is_empty() { return root == 0; }

   int height() { return height( root ); }

   int height(BinaryNode<T> *p)
   {
      if (p)
      {
         int h1 = height(p->left);
         int h2 = height(p->right);
         return h1 > h2 ? 1 + h1: 1 + h2;
      }
      else
         return 0;
   }

   void nuke() { nuke(root); }

   void nuke(BinaryNode<T> * & t)
   {
     if (t)
     {
        nuke(t->left);
        nuke(t->right);
        delete t;
     }
     t = 0;
   }

   int size() { return size(root); }

   int size(BinaryNode<T> *t)
   {
	  if (t)
	     return 1 + size(t->left) + size(t->right);
	  else
	     return 0;
   }

   BinaryNode<T> *find(T item) { return find(item, root); }

   BinaryNode<T> *find(T item, BinaryNode<T> *t)
   {
      if (! t) return 0;
      if (t->data == item)
         return t;
      else
         if (item < t->data)
            return find(item, t->left);
         else
            return find(item, t->right);
   }

   void print_tree() { print_tree( root ); }

   void print_tree(BinaryNode<T> *p)
   {
	  static int ct = 0;
      if (p)
      {
         print_tree(p->left);
         cout << fixed << setw(10) << p->data;
         if (++ct % 7 == 0) cout << endl;
         print_tree(p->right);
      }
   }

   BinaryNode<T> *findmin(BinaryNode<T> *t)
   {
	  if (t)
	     if (t->left)
	        return findmin(t->left);
	     else
	        return t;
	  else
	     return 0;
   }

   void remove( const T& item) { remove(item, root); }

   void remove( const T& item, BinaryNode<T> * & t )
   {
      BinaryNode<T> *p;
      if (! t)
      {
	     cout << "\nError, cannot delete item, not found.\n";
	     return;
      }
      if (item < t->data)
         remove(item, t->left);
      else
         if (t->data < item)
            remove(item, t->right);
         else
         {  //t points to item to be deleted
	         if (t->left != 0 && t->right != 0) //node has 2 children
             {
                p = findmin(t->right);
                t->data = p->data;
                remove(t->data, t->right);
    	     }
	         else //1 child or none
             {
		        p = t;
		        t = t->right ? t->right : t->left;
		        delete p;
	         }
	     }
   }

   void dump_array(T x[], BinaryNode<T> *p)
   {
     static int j = 0;
     if (p)
     {
       dump_array(x, p->left);
       x[j++] = p->data;
       dump_array(x, p->right);
     }
   }

   void dump_array(T x[])
   {
      dump_array(x, root);
   }

   void insert( const T& item ) { insert(item, root); }

   void insert( const T& item, BinaryNode<T> * & t )
   {
      if (! t)
         t = new BinaryNode<T>(item);
      else
      {
         if (item < t->data)
            insert( item, t->left );
         else
//            if (t->data < item)
               insert( item, t->right );
//            else
            //duplicate, do not insert it
//               cout << "\nDuplicate item not inserted...\n";
      }
   }
};
#endif 

And here is what my .cpp file looks like.

four.cpp

//***************************************************************************
//                           Giselle Colon                                  *
//                       Programming II MW 4:15                             *
//                        Due October 17,2012                               *
//                            Assignment 4                                  *
//***************************************************************************

// Basic binary search tree manipulation
// Insert, traverse, delete
#include <iostream>
#include "mybst.h"
using namespace std;

int main(){
   int a = 0;
   cout << "Hello this is the program for binary search tree manipulation"
        << endl;

   BST<T>::insert(15);

   return 0;
}

Here are the list of errors I get and how I compile it.

g++ mybst.h four.cpp -o four
four.cpp: In function âint main()â:
four.cpp:19: error: âTâ was not declared in this scope
four.cpp:19: error: template argument 1 is invalid
four.cpp:19: error: invalid type in declaration before â(â token

Thank you in advance.

[pogrady]

When declaring a template the variable name T is used often (all though it can be anything). When declaring a user defined type that incorporates a template, you must pass the type as the parameter to the template argument list. Instead of this:

BST<T>::insert(15);

It would be this:

BST<int> bst; //declare a bst object with a type of int
bst.insert(15);//insert the integer 15

[RaineShadow]

Ok that worked! Thank you so much I've been looking in so many places trying to figure that out.

I'm guessing that when I want to use something like the function is_empty I'd do:

BST<bool>empty;
empty.is_empty();

Is that correct?

[RaineShadow]

Sorry I just tried it. Thank you again :D