binary search tree help

This is a discussion on binary search tree help within the C++ Programming forums, part of the General Programming Boards category; hi, i wrote this binary search tree. Having a little problem, it compiles with no errors whatsoever, but for some ...

  1. #1
    Registered User
    Join Date
    Mar 2003
    Posts
    134

    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);
            }
             
            
    }
    Last edited by noob2c; 11-08-2003 at 10:31 AM.

  2. #2
    Registered User
    Join Date
    Mar 2003
    Posts
    134
    can someone pls help me out? any hints ?

  3. #3
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401
    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.
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,558
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Mar 2003
    Posts
    134
    its the insert and findPosition that are messing up, have no idea why though
    Last edited by noob2c; 11-09-2003 at 10:03 AM.

  6. #6
    Registered User
    Join Date
    Mar 2003
    Posts
    134
    i made the following changes, but only one word goes through

    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.key<<"                 "<<setw(5)<<p.data;
    	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;
    
    	findPosition(k,ptr,found);
    
    	if(found == true)
    	{
    		ptr->element.data--;
    		return ptr;
    	}
    	
    	return NULL;
    }
    
    template<class KeyType,class DataType>
    void bsearchTree<KeyType,DataType>::insert(const mypair<KeyType,DataType>& p)
    {
    	node<KeyType,DataType>* ptr;
    	node<KeyType,DataType>* ptr1;
    	bool found=false;
    
    	findPosition(p.key,ptr,found);
    
    	if(found == true)cerr<<"duplicates not allowed."<<endl;
    
    
    	if(found == false && ptr == NULL)//this means tree is empty
    	{
    		ptr = new node<KeyType,DataType>;
    		assert(ptr != NULL);
    		root = ptr;
    		ptr->element.key=p.key;
    		ptr->element.data=1;
    		ptr->left=NULL;
    		ptr->right=NULL;
    	}
    	else
    	{
    
    		if(found == false && ptr != NULL)//key is unique
    		{
    			if(ptr->element.key < p.key)
    			{
    				ptr1=ptr->left;
    				ptr1= new node<KeyType,DataType>;
    				assert(ptr1!=NULL);
    				ptr1->element.key=p.key;
    				ptr1->element.data=1;
    				ptr1->left=NULL;
    				ptr1->right=NULL;
    			}
    
    			else
    			{
    				ptr1=ptr->right;
    				ptr1= new node<KeyType,DataType>;
    				assert(ptr1!=NULL);
    				ptr1->element.key=p.key;
    				ptr1->element.data=1;
    				ptr1->left=NULL;
    				ptr1->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;
    	node<KeyType,DataType>* follow;
    
    	if(root == NULL)
    	{
    		found = false;
    		ptr=NULL;
    	}
    
    	else
    	{
    		current = root;
    
    		while(current != NULL && found != true)
    		{
    			follow=current;
    
    			if(current->element.key == k)
    			{
    				found = true;
    				current->element.data++;
    				ptr=current;
    			}
    
    			else
    				if(current->element.key > k)current=current->left;
    				else
    					current=current->right;
    		}//end of while
    
    		ptr=follow;
    	}
    
    	
    }
    
    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

  7. #7
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401
    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.
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  2. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 08:11 AM
  3. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 04:15 PM
  4. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 09:18 AM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21