Thread: binary search tree help

hi,

i wrote this binary search tree. Having a little problem, it compiles with no errors whatsoever, but for some reason doesnt seem to insert the word that it gets from the file. nextWord works fine because i used it in another program. What am I doing wrong ?

it is supposed to open a text file, read in each word and the bst will keep stat of the words.

bsearchTree.h

Code:

#ifndef _bsearchTree_h
#define _bsearchTree_h

#include <iostream>
#include <iomanip>
#include <string>
#include <cassert>

using namespace std;

template<class KeyType, class DataType>
struct mypair
{   KeyType key;
    DataType data;
};

template<class KeyType, class DataType>
struct node
{   mypair<KeyType, DataType> element;
    node<KeyType, DataType>* left;
    node<KeyType, DataType>* right;
};

template<class KeyType, class DataType>
class bsearchTree
{
public:
      typedef node<KeyType, DataType>* Ptr;
      bsearchTree(); //defined
          //default constructor - constructs empty tree
          
      ~bsearchTree();//defined
          //destructor. Deletes all nodes in the tree. Uses a
          //recursive private member function.
          
      bool empty();//defined
          //returns true if and only if the tree is empty
          
      long int size();//defined
          //returns the number of nodes in the tree. You cannot 
          //just add a data member to the class to keep track of 
          //the size. Uses a recursive private member function.
          
      long int height();//defined
          //returns the height of the tree. Uses a recursive 
          //private member function. Make the height of an empty
          //tree to be -1 rather than 0 as done in the book.
          
      Ptr find(KeyType k);//defined
          //searches the tree for the key. If the key is found it 
          //returns a pointer to the node containing the key; 
          //otherwise it returns NULL. Uses private member function
          //findPosition.
          
      void insert(const mypair<KeyType, DataType>& p);//defined
          //checks whether a pair with the key part of p is already 
          //in the tree. If so then it prints an error message and 
          //does not insert the pair. If not then it inserts the pair. 
          //Uses private member function findPosition.
          
      DataType& data(Ptr ptr);//defined
          //returns a referenece to the data part of the element
          //pointed to by p. This will allow the user to modify the 
          //data and provides some of the functionality that a true 
          //iterator would provide.
          
      void print();//defined
          //outputs the elements in sorted order of the keys, i.e. 
          //inorder. Output each element on a separate line, i.e. 
          //the output is done as cout<<ptr->element<<endl. Do not 
          //directly output the key and data. This way the user can
          //overload the << operator for the pairs to control the output
          //however desired. Uses a recursive private member function.
               
private:
      Ptr root;
      
      void findPosition(const KeyType& k, Ptr& ptr, bool& found);
          //Searches for key, k, in the tree. If found then 
          //sets ptr to point to the node containg the key and sets
          //found to true. If not found then sets ptr to point to the 
          //node such that an element with this key should be inserted 
          //directly below the node (if tree is empty then sets ptr 
          //to NULL) and sets found to false.
          
      //other private member function prototypes
	  void destroy(Ptr &);//defined
	  void inorder(Ptr);//defined
	  long int sizeCount(Ptr );
	  long int heightCount(Ptr);//defined
	  long int maxa(long int,long int);//defined
};

ostream& operator<<(ostream& os, const mypair<string, int> p)
{
	//Ouput the string and then enough space to reach column 20
    //and then output the integer in a field of width 5. This will 
    //allow all the words and frequencies to line up nicely as shown
    //in the write-up.

	os<<p.data<<"                   "<<setw(5)<<p.key;
	return os;
}
    
template<class KeyType,class DataType>
bsearchTree<KeyType,DataType>::bsearchTree():
root(NULL)
{
}

template<class KeyType,class DataType>
bsearchTree<KeyType,DataType>::~bsearchTree()
{
	destroy(root);
}

template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::destroy(node<KeyType, DataType>* &p)
{
	if(p != NULL)
	{
		destroy(p->left);
		destroy(p->right);
		delete p;
		p=NULL;
	}
}

template<class KeyType,class DataType>
bool bsearchTree<KeyType,DataType>::empty()
{
	if(root == NULL)return true;
}

template<class KeyType,class DataType>
DataType& bsearchTree<KeyType,DataType>::data(node<KeyType, DataType>* ptr)
{
	return (ptr->element).data;
}

template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::print()
{
	inorder(root);
}

template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::inorder(node<KeyType, DataType>* p)
{
	if(p != NULL)
	{
		inorder(p->left);
		cout<<p->element<<endl;
		inorder(p->right);
	}
}

template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::height()
{
	return heightCount(root);
}

template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::size()
{
	return sizeCount(root);
}

template<class KeyType,class DataType>
node<KeyType, DataType>* bsearchTree<KeyType,DataType>::find(KeyType k)
{
	node<KeyType, DataType>* ptr;
	bool found=false;

	findPosition(k,ptr,found);

	if(found == true)return ptr;

	return NULL;
}

template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::insert(const mypair<KeyType,DataType>& p)
{

	node<KeyType, DataType>* ptr;
	bool found=false;
	findPosition(p.key, ptr, found);

	if(found == true)cout<<"error duplicates not allowed"<<endl;//should never come here.

	if(found == false && ptr == NULL)
	{
		ptr = new node<KeyType, DataType>;
		assert(ptr != NULL);
		(ptr->element).data=1;
		(ptr->element).key=p.key;
		ptr->left=NULL;
		ptr->right=NULL;
	}
}

template<class KeyType,class DataType>
void bsearchTree<KeyType,DataType>::findPosition(const KeyType& k, node<KeyType, DataType>* &ptr, bool& found)
{
	node<KeyType, DataType>* current;//pointer to travel the tree
	node<KeyType, DataType>* follow;//pointer behind current


	if(root == NULL)//this is when the tree is empty
	{
		found=false;
		ptr=NULL;
	}

	else
	{
		current = root;

		while(current != NULL && found != true)
		{
			follow=current;

			if(current->element.key == k)
			{
				ptr=current;
				found = true;
				current->element.data+=1;
			}
			else
				if(current->element.key > k)current=current->left;
				else
					current = current->right;
		}//end of while

		if(follow->element.key > k)
		{
			ptr=follow->left;
			found = false;
		}
		else
		{
			ptr=follow->right;
			found = false;
		}


	}//end of else
}

template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::heightCount(node<KeyType, DataType>* p)
{
	if(p == NULL)return -1;

	else
		return 1 + maxa(heightCount(p->left),heightCount(p->right));
}

template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::maxa(long int x, long int y)
{
	return(x > y ? x : y);
}

template<class KeyType,class DataType>
long int bsearchTree<KeyType,DataType>::sizeCount(node<KeyType,DataType>* p)
{
	if( p == NULL)return 0;

	return sizeCount( p->left ) + 1 + sizeCount( p->right );
}


#endif

main.cpp

Code:

#include <iostream>
#include <cmath>
#include <string>
#include <fstream>
#include <cctype>
#include <cstdlib>
#include "bsearchTree.h"

using namespace std;

void nextWord(ifstream& ifs, string& word, bool& found);


int main()
{
	char fname[20];
	ifstream infile1;
	string word;
	bool found = true;
	bool finder = false;
	char ch;
	
	bsearchTree<string, int> bst;
	mypair<string, int> bst1;
	

	cout<<"Enter File Name:";
    cin>>fname;
	infile1.open(fname);
	
	if(infile1.fail())
    {
      cerr<<"Input file " <<fname <<" does not exist"<<endl;
      cin.get(ch);
      exit(1);
    }

	while(found == true)
	{
		nextWord(infile1,word,found);

		if(found == true)
		{
			if(bst.find(word) == NULL)
			{
				bst1.key=word;
				bst1.data=1;
				bst.insert(bst1);
			}
		}
		word.erase(word.begin(),word.end());
		finder = false;
	}

	infile1.close();

	cout<<"number of nodes in the tree "<<bst.size()<<endl;
	cout<<"height of tree "<<bst.height()<<endl;
	long double k = bst.size();
	long double a = 2;
	cout<<"height of a perfectly balanced tree "<<floor(log(k)/log(a))<<endl;

	cout<<"Word                Frequency"<<endl;
	bst.print();

	

	system("PAUSE");
	return 0;
}


void nextWord(ifstream& ifs, string& word, bool& found)
{
        char ch=' ';
                                
                         
                 
        while( !isalpha(ch) && !ifs.fail() )
        {
                ifs.get(ch); 
        }
        if(ifs.fail())found=false;
        else
                found=true;
        
        while(isalpha(ch) && !ifs.fail())
        {
                word.push_back(tolower(ch));
                ifs.get(ch);
        }
         
        
}

You'll have to be patient - people do not really have the time to look through or run all that code. If you have a debugger, I suggest you learn how to use it. If you don't have a debugger, you can just place MessageBox() calls in certain places to output variables to the screen. That way, you can see where the problem is.

1. what is the point of the variable called finder?

2. Test this

Code:

	while(found == true)
	{
		nextWord(infile1,word,found);
		if(found == true)
			cout << "Word = " << word << end;
	}

Make sure that you can read words properly from the file before doing anything with them. If you're not reading words properly, the rest of your code will make no sense whatsoever.

Then you write a whole bunch of tests for your bst class

Start with an empty tree then call things like
bst.empty() // should be true
bst.size() // should be 0
bst.height() // should be 0
bst.find() // should always return false

Then add ONE known word to the bst and repeat your tests, and check you get the expected behaviour.

Keep adding elements to this (and other trees) designed to exercise specific parts of your code.

WHEN it fails to work, put a breakpoint at the start of the test which fails and single step the code until the code goes somewhere you didn't expect. You have now found a bug.

Fix it, rinse and repeat.

Then (and only then) do you bury your class inside a larger program.

its the insert and findPosition that are messing up, have no idea why though

When you end up with a mass of code and a small processing error, the best solution is sometimes to start again. Slowly rebuild your program, compiling and running frequently, so that you can identify which section causes the error. It won't be that hard; just copy and paste small sections of code from the original to the new. Test every function individually to ensure it is working correctly.

Note: You should have been doing this in the first place anyway. It make take a little longer, but it saves you a hell of a lot of time later on during debugging.