Binary Search Tree Manipulation

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//***************************************************************************
//                           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.
Last edited on
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
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?
Sorry I just tried it. Thank you again :D
Topic archived. No new replies allowed.