Binary Search Tree within in BT ?

[tones1986]

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 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 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 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!

[tones1986]

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::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::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.