Hey all - i am working on an assignment in which i previously created a class to create a Binary Tree. The follow up assignment was to create a Binary Search Tree... but using all the BT methods except an additional couple and obviously a different insert method to stop duplicates.

I have multiple files, but i will post what i think would be needed.

BST.h file - binary search tree class implementation

#ifndef BST_H
#define BST_H

#include "340.h"
#include "BT.h"

template <class T> 
class BSTree : public BT<T>
   {
   public:
      void insert(const T&); 
      void remove(const T&);  
      bool search(const T&, int&) const;
   };

/****************************************************************
   FUNCTION:   insert()
   ARGUMENTS:  data value
   RETURNS:    None
   NOTES:      inserts the new data item into the tree
****************************************************************/ 
template <class T>
void BSTree<T>::insert(const T& newItem)
{   
cout << "in BST insert()" << endl;
Node<T> * current = BT<T>::root, * parent = NULL;

while (current != NULL && newItem != current->data)
{
  parent = current;
  if (newItem < current->data)
    current = current->left;
  else if (newItem > current->data)
    current = current->right;
  else if (newItem == current->data)
  {
    cout << "values are the same, should quit" << endl;
    return;
  }
}

if (current != NULL)
    return;  
  else
  {
    Node<T> * newNode;
    newNode = new Node<T>(newItem);
  
    if (parent == NULL)
      BT<T>::root = newNode;
    else
    {
      if (newNode->data < parent->data)
           parent->left = newNode;
      else if (newNode->data > parent->data)
           parent->right = newNode;
      else if (newNode->data == parent->data)
        {
        cout << "values are the same, should quit" << endl;
       return;
        }
    }
    
  return;
  }
....other methods and end of .h

BT.h - binary tree implementation in class

#ifndef H_BT
#define H_BT

#include "340.h"
#include "Node.h"


template<class T> class BT {
public:
    
    BT() { root = NULL;}
    BT(const BT<T>&);
    BT& operator=(const BT<T>&);
    virtual ~BT() { clear(); }

    bool empty() const { return root == 0; }
    int size() const { return size(root); }
    int height() const { return height(root); }
    int leaves() const { return leaves(root); }
    virtual void insert(const T& x) { insert(root, x); }
    void clear() { clear(root); root = 0; }

    bool search(const T&, int&) const;
    void preOrder(void (*p)(T&)) { preOrder(root, p); }
    void inOrder(void (*p)(T&)) { inOrder(root, p); }
    void postOrder(void (*p)(T&)) { postOrder(root, p); }
    void printTree(Node<T> *);

    Node<T>* root;

private:
    int size(Node<T>*) const;
    int height(Node<T>*) const;
    int leaves(Node<T>*) const;
    void insert(Node<T>*&, const T&);
    void clear(Node<T>*);

    void inOrder(Node<T>*, void (*)(T&));
    void preOrder(Node<T>*, void (*)(T&));
    void postOrder(Node<T>*, void (*)(T&));

    Node<T>* copy(const Node<T>*);
};
...methods....
/****************************************************************
   FUNCTION:   insert()
   ARGUMENTS:  data value
   RETURNS:    None
   NOTES:      inserts the new data item into the tree
****************************************************************/ 
template <class T>
void BT<T>::insert(Node<T>*& root, const T& newItem)
{   
cout << "in BT insert()" << endl;
Node<T> *newNode = new Node<T>(newItem);
newNode->left = NULL;
newNode->right = NULL;
 {
     if (root == NULL)
       root = newNode;
     else if (height(root->left) <= height(root->right))
       insert(root->left, newItem);
     else
       insert(root->right, newItem);
 }
}
...methods/end of .h....

And within my prog5.cc

/****************************************************************
   FILE:      prog5.cc
   AUTHOR:    Anthony Hogan
   LOGON ID:  Z109079
   DUE DATE:  4/11/08

   PURPOSE:   This contains the need #includes and class definition
              so that it is not used more than once in the progam
****************************************************************/
#include "BST.h"

int main()
{
    int n = 10;
    vector<int> vec;    
    BST<int> tree;
    vector<int>::iterator theIterator = vec.begin();
   
    for (int i = 0; i <= n; i++)
    {
        vec.push_back( rand() % n + 1 );
        tree.insert(rand() % n + 1);
    }
    
   bool isFound = false;
   double countFound = 0,
       searchCount = 0,
       precSucc = 0;
          for(theIterator = vec.begin(); theIterator != vec.end(); theIterator++)    
        {
           isFound = tree.search(*theIterator,n);
           if (isFound == true)
              {
              countFound++;
              isFound = false;
              }
           searchCount++;
        }
    
   tree.printTree(tree.root);    
   /*
   cout << "BST:" << endl;
   cout << "       Number of Node:  SOME VALUE??? " << endl;
   cout << "       Number of leaves:     " << tree.leaves() << endl;
   cout << "       Height of tree        " << tree.height() << endl;
   cout << endl;
   precSucc = (countFound/searchCount) * 100;
   cout << "Ratio of successful searches for 'BST' is " << precSucc << endl;
   cout << "Successfull Searches: " << countFound << " Total # search: " << searchCount << endl;
   cout << "Average search length for 'BST' is SOME VALUE " << endl;
   cout << endl;
   cout << "The elements of 'BST' in inOrder:" << endl;
   tree.printTree(tree.root);
   */ 
    system("PAUSE");
    return 0;
}

Okay - those are the files - my problems include:

How do i use this line within prog5.cc to call the BST version of insert()?

tree.insert(rand() % n + 1);

Obviously i declared the tree as a BT<T> tree - but if i try declaring my tree as a BST - i get errors:
16 C:\Users\Tony\Documents\school\Fall 08\CSCI 340\assign5\prog5.cc aggregate `BST<int> tree' has incomplete type and cannot be defined

I made the BST class a friend of sorts of the BT class so it should have access to all the methods of the BT class... so should i be declaring it as BST<T> Tree then? Or what? Any ideas?

And my other question is about the BST insert - is this insert going to work? In terms of removing duplicates etc... and making a perfect binary search tree? I think i had it working before but am nervous i may have got it wrong!

Any help would be appreciated!

I just wanted to update what is going on with the program. I have got the classes working together without a problem so it seems... but now i am having a problem when refering to any sort of node using the left/right variables.

Here is a gdb debug on my program:
Starting program: /home/turing/z109079/340/assign5/prog5.exe
warning: no loadable sections found in added symbol-file system-supplied
DSO at 0x7fff69dfe000
duplicates not allowed!
duplicates not allowed!
duplicates not allowed!
duplicates not allowed!
print tree below
sh: PAUSE: command not found

Program received signal SIGSEGV, Segmentation fault.
0x00000000004013a3 in BT<int>::clear (this=0x7fff69d855d0,
copyRoot=0x700000004) at BT.h:176
176 clear(copyRoot->left);

Previously i got this error from the gdb debugger:
(i commented out the lines that caused the error (within printTree() as shown below), then the above error occured, so i assume its got something to do with the right/left either not being there or are NULL?!?)

Starting program: /home/turing/z109079/340/assign5/prog5.exe
warning: no loadable sections found in added symbol-file system-supplied
DSO at 0x7fff173fe000
duplicates not allowed!
duplicates not allowed!
duplicates not allowed!
duplicates not allowed!
print tree below

Program received signal SIGSEGV, Segmentation fault.
0x00000000004020d7 in BT<int>::printTree (this=0x7fff1738abe0,
node=0x700000004) at BT.h:81
81 printTree(node->left);

I will attach my code - all the files together that i am using in the assignment. Please if you could attempt running it yourself - and maybe then you can see where my problem lies? Thank you so much in advance.

Attachments
#ifndef H_340
#define H_340

#include <iostream>
#include <fstream>
#include <iomanip>
#include <sstream>

#include <cstdlib>
#include <climits>
#include <cmath>
#include <ctime>

#include <algorithm>
#include <functional>
#include <iterator>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <set>

#include <stdexcept>
using namespace std;
#endif
/****************************************************************
   FILE:      BSTree.h
   AUTHOR:    Anthony Hogan
   LOGON ID:  Z109079
   DUE DATE:  4/11/08

   PURPOSE:   This contains the need #includes and class definition
              so that it is not used more than once in the progam
****************************************************************/
#ifndef BST_H
#define BST_H

#include "340.h"
#include "BT.h"

template <class T> 
class BSTree : public BT<T>
   {
   public:
      void insert(const T&)
      void remove(const T&);
      bool search(const T&, int&) const;
   private:
      void insert(Node<T>*&, const T&);
   };

/****************************************************************
   FUNCTION:   insert()
   ARGUMENTS:  data value
   RETURNS:    None
   NOTES:      inserts the new data item into the tree
****************************************************************/ 
template <class T>
void BSTree<T>::insert(const T& newItem)
{   
Node<T> * current, * trailCurrent, *newNode;

Node<T> * newNode;
newNode = new Node<T>(newItem);

if (this->root == NULL)
   this->root = newNode;
else
{
    current = this->root;
    
    while (current != NULL)
    {
          trailCurrent = current;
          
          if (current->data == newItem)
          {
             cout << "duplicates not allowed!" << endl;
             return;
          }
          else if (current->data > newItem)
             current = current->left;
          else
             current = current->right;
    }//end while
    
    if (trailCurrent->data > newItem)
         trailCurrent->left = newNode;
    else
         trailCurrent->right = newNode;
}//end insert

/*    
while (current != NULL && newItem != current->data)
{
  parent = current;
  if (newItem < current->data)
    current = current->left;
  else // if (newItem > current->data)
    current = current->right;
}

if (current != NULL)
    return;  
  else
  {
    Node<T> * newNode;
    newNode = new Node<T>(newItem);
  
    if (parent == NULL)
      root = newNode;
    else
      if (newNode->data < parent->data)
           parent->left = newNode;
         else
           parent->right = newNode;
    
  return;
  }
}
*/  
/*
void BST<T>::remove(const T& x)
{
}
*/
/****************************************************************
   FUNCTION:   search
   ARGUMENTS:  value to search for, total path length
   RETURNS:    true or false if found
   NOTES:      searches for a set value in tree
****************************************************************/
template <class T>
bool BSTree<T>::search(const T& x, int& len) const
{
     Node<T> * current;
     bool found = false;
     int count = 0;
     
     if (this->root == NULL)
         cout << "Cannot search empty tree!" << endl;
     else
     {
         current = this->root;
         
         while (current != NULL && !found && count <= len)
         {
               if (current->data == x)
                  found = true;
               else if (current->data > x)
                  current = current->left;
               else
                  current = current->right;
               count++;
         }//end while
     }
     return found;
}

#endif // END OF BST.H
#ifndef H_BT
#define H_BT

#include "340.h"
#include "Node.h"


template<class T> class BT {
public:
    
    BT() { root = NULL;}
    BT(const BT<T>&);
    BT& operator=(const BT<T>&);
    virtual ~BT() { clear(); }

    bool empty() const { return root == 0; }
    int size() const { return size(root); }
    int height() const { return height(root); }
    int leaves() const { return leaves(root); }
    virtual void insert(const T& x) { insert(root, x); }
    void clear() { clear(root); root = 0; }

    bool search(const T&, int&) const;
    void preOrder(void (*p)(T&)) { preOrder(root, p); }
    void inOrder(void (*p)(T&)) { inOrder(root, p); }
    void postOrder(void (*p)(T&)) { postOrder(root, p); }
    void printTree(Node<T> *);

    Node<T>* root;

private:
    int size(Node<T>*) const;
    int height(Node<T>*) const;
    int leaves(Node<T>*) const;
    void insert(Node<T>*&, const T&);
    void clear(Node<T>*);

    void inOrder(Node<T>*, void (*)(T&));
    void preOrder(Node<T>*, void (*)(T&));
    void postOrder(Node<T>*, void (*)(T&));

    Node<T>* copy(const Node<T>*);
};

/****************************************************************
   FUNCTION:   search
   ARGUMENTS:  value to search for, total path length
   RETURNS:    true or false if found
   NOTES:      searches for a set value in tree
****************************************************************/
template <class T>
bool BT<T>::search(const T& x, int& len) const
{
     Node<T> * current;
     bool found = false;
     
     if (root == NULL)
         cout << "Cannot search empty tree!" << endl;
     else
     {
         current = root;
         
         while (current != NULL && !found)
         {
               if (current->data == x)
                  found = true;
               else if (current->data > x)
                  current = current->left;
               else
                  current = current->right;
         }//end while
     }
     return found;
}

template <class T>
void BT<T>::printTree(Node<T> * node) 
{ 
  static int count = 0;
  if (node == NULL) return; 
  printTree(node->left); 
  cout << node->data << " "; 
  printTree(node->right); 
 count += 1;
} 

template <class T>
BT<T>::BT(const BT<T> &treeCopy)
{
root = copy(treeCopy.root);
}

template <class T>
BT<T> & BT<T>::operator=(const BT<T> & rightOp)
{
if(this != &rightOp)
  {
  clear();
  root = copy(rightOp.root);
  }
return *this;
} 
/****************************************************************
   FUNCTION:   size() RECURSIVE
   ARGUMENTS:  None
   RETURNS:    size of the tree
   NOTES:      this finds the size of the tree
****************************************************************/ 
template <class T>
int BT<T>::size(Node<T> * copyRoot) const
{
if (copyRoot == NULL)
   return 0;
else 
  return 1 + (size(copyRoot->right) + size(copyRoot->left));
}

/****************************************************************
   FUNCTION:   height() RECURSIVE
   ARGUMENTS:  None
   RETURNS:    returns the size of the height
   NOTES:      this finds the height of the tree
****************************************************************/ 
template <class T>
int BT<T>::height(Node<T> * copyRoot) const
{
int leftSize = 0, rightSize = 0;
  if (copyRoot == NULL)
    return 0;
  else
    {
    leftSize += height(copyRoot->left);
    rightSize += height(copyRoot->right);
    if (leftSize > rightSize)//if (height(copyRoot->left) > height(copyRoot->right))
       return (1 + leftSize);
    else
       return (1 + rightSize);
    }   
}

/****************************************************************
   FUNCTION:   height() RECURSIVE
   ARGUMENTS:  None
   RETURNS:    returns the size of the height
   NOTES:      this finds the height of the tree
****************************************************************/ 
template <class T>
int BT<T>::leaves(Node<T> * copyRoot) const
{
int leafCnt = 0;
    if (copyRoot->left == NULL && copyRoot->right == NULL)
        return 0;
    if (copyRoot->left != NULL)
    {
    ++leafCnt;
    leaves(copyRoot->left); 
    }
    if (copyRoot->right != NULL)
    {
    ++leafCnt;
    leaves(copyRoot->right);
    }
    return leafCnt;
}
/****************************************************************
   FUNCTION:   destroyTree()
   ARGUMENTS:  root of the tree
   RETURNS:    None
   NOTES:      this deletes the nodes of the tree
****************************************************************/ 
template <class T>
void BT<T>::clear(Node<T> * copyRoot)
{
 if (copyRoot != NULL) 
   {
   clear(copyRoot->left);
   clear(copyRoot->right);
   delete copyRoot;
   }   
}

 /****************************************************************
   FUNCTION:   copy_tree()
   ARGUMENTS:  root of the tree
   RETURNS:    None
   NOTES:      this deletes the nodes of the tree
****************************************************************/
template <class T>
Node<T> * BT<T>::copy(const Node<T> * copyRoot)
{  
if (copyRoot == NULL)
   return NULL;
else
{
Node<T> * newNode;
newNode = new Node<T>(copyRoot->data);
newNode->left = copy(copyRoot->left);
newNode->right = copy(copyRoot->right);
return newNode;
}
}

/****************************************************************
   FUNCTION:   insert()
   ARGUMENTS:  data value
   RETURNS:    None
   NOTES:      inserts the new data item into the tree
****************************************************************/ 
template <class T>
void BT<T>::insert(Node<T>*& root, const T& newItem)
{   
cout << "in BT insert()" << endl;
Node<T> *newNode = new Node<T>(newItem);
newNode->left = NULL;
newNode->right = NULL;
 {
     if (root == NULL)
       root = newNode;
     else if (height(root->left) <= height(root->right))
       insert(root->left, newItem);
     else
       insert(root->right, newItem);
 }
}


/****************************************************************
   FUNCTION:   preTrav()
   ARGUMENTS:  root of the tree
   RETURNS:    None
   NOTES:      prints each member of the tree
****************************************************************/ 
template <class T>
void BT<T>::preOrder(Node<T> * current, void (*p)(T&))
{
 if (current != NULL)
    {
    p(current->data);
    preOrder(current->left, p);
    preOrder(current->right, p);
    }
} 

/****************************************************************
   FUNCTION:   inTrav()
   ARGUMENTS:  root of the tree
   RETURNS:    None
   NOTES:      prints each member of the tree
****************************************************************/ 
template <class T>
void BT<T>::inOrder(Node<T> * current, void (*p)(T&))
{
 if (current != NULL)
    {
    inOrder(current->left, p);
    p(current->data);
    inOrder(current->right,p);
    }
} 

/****************************************************************
   FUNCTION:   postTrav()
   ARGUMENTS:  root of the tree
   RETURNS:    None
   NOTES:      prints each member of the tree
****************************************************************/ 
template <class T>
void BT<T>::postOrder(Node<T> * current, void (*p)(T&))
{
 if (current != NULL)
    {
    postOrder(current->left, p);
    postOrder(current->right, p);
    p(current->data);
    }
}

#endif //END OF BS.H
/****************************************************************
Name: Anthony Hogan
****************************************************************/
#ifndef NODE_H
#define NODE_H

#include "BT.h"

template<class T> class BST;
template<class T> class BT;
template<class T> class Node
{
friend class BT<T>;
public:
   Node(const T& =T(),Node<T>* =0,Node<T>* =0);

   T data;
   Node<T> *left,*right;
};
//START OF BSTNODE METHODS
/****************************************************************
   FUNCTION:   BSTNode()
   ARGUMENTS:  int
   RETURNS:    None
   NOTES:      this is BSTNode constructor
****************************************************************/ 
template <class T>
Node<T>::Node(const T& item,Node<T> *left,Node<T> *right)
{
  data = item;
  left = right = NULL;
}
//END OF BSTNODE METHODS
#endif // END OF NODE.H
/****************************************************************
   FILE:      prog5.cc
   AUTHOR:    Anthony Hogan
   LOGON ID:  Z109079
   DUE DATE:  4/11/08

   PURPOSE:   This contains the need #includes and class definition
              so that it is not used more than once in the progam
****************************************************************/
#include "BST.h"

int main()
{
    int n = 10;
    vector<int> vec;    
    BSTree<int> tree;
    vector<int>::iterator theIterator = vec.begin();
   
    for (int i = 0; i <= n; i++)
    {
        vec.push_back( rand() % n + 1 );
        tree.insert(rand() % n + 1);
    }
    
   bool isFound = false;
   double countFound = 0,
       searchCount = 0,
       precSucc = 0;
          for(theIterator = vec.begin(); theIterator != vec.end(); theIterator++)    
        {
           isFound = tree.search(*theIterator,n);
           if (isFound == true)
              {
              countFound++;
              isFound = false;
              }
           searchCount++;
        }
    
   tree.printTree(tree.root);    
   /*
   cout << "BST:" << endl;
   cout << "       Number of Node:  SOME VALUE??? " << endl;
   cout << "       Number of leaves:     " << tree.leaves() << endl;
   cout << "       Height of tree        " << tree.height() << endl;
   cout << endl;
   precSucc = (countFound/searchCount) * 100;
   cout << "Ratio of successful searches for 'BST' is " << precSucc << endl;
   cout << "Successfull Searches: " << countFound << " Total # search: " << searchCount << endl;
   cout << "Average search length for 'BST' is SOME VALUE " << endl;
   cout << endl;
   cout << "The elements of 'BST' in inOrder:" << endl;
   tree.printTree(tree.root);
   */ 
    system("PAUSE");
    return 0;
}
This article has been dead for over six months. Start a new discussion instead.