[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 911
  • Last Modified:

Binary Search Tree Functions

I need help finishing a program's find function for a binary search tree. This is an assignment for school and I was given two header files and a cpp file. My task is to write a program which counts the number of occurrences of unique words in a document. I started writing some of the program when I got confused on what to do next.

find was described like this:
"Add a public method T* find( const T & x ) using ITERATION, that is, by using loop(s).  This method is different from bool contains(const T & x), in that find() should return a pointer to the ELEMENT in the binary node if the parameter x exists in the tree (while contains() simply returns true/false). "

I wrote a find function but I don't think it is right. I also wrote the insert function.
I was told to do the following with the find and insert functions:
"You look up the word in the BST. You do so by first creating a Word object (as a local variable) and calling the find method in bst.  If the word is already in the tree, increment the 'count' in the returned Word object. Note: the object is returned by Word*, not Word itself. So in order to increment count, you have to go through a (Word) pointer.
Otherwise this is the first time the word is encountered in the document. Insert a new Word entry in the BST with an appropriate count. "

Overall, I need help writing my find function and implementing the find/ insert functions so that the program counts unique words. I don't know how to count unique words using the returned *Word. If anyone can help, it would be helpful.
// filename: word.h

#ifndef WORD_H
#define WORD_H

#include <iostream>
#include <string>
#include <iomanip>
using namespace std;

/*
 *  class Word
 */

struct Word
{
  // Data members
  string wstring;
  int count;

  // Constructor
  Word(const string& s = "", int cnt = 0) : wstring(s), count(cnt) {}

  // Overloaded operators
  bool operator==(const Word& s2) const;
  bool operator!=(const Word& s2) const;
  bool operator<(const Word& s2) const;
  bool operator<=(const Word& s2) const;
  bool operator>(const Word& s2) const;
  bool operator>=(const Word& s2) const;
};

bool Word::operator==(const Word& s2) const
{
  return wstring == s2.wstring;
}

bool Word::operator!=(const Word& s2) const
{
  return !(wstring == s2.wstring);
}

bool Word::operator<(const Word& s2) const
{
  return wstring < s2.wstring;
}

bool Word::operator<=(const Word& s2) const
{
  return (wstring < s2.wstring) || (wstring == s2.wstring);
}

bool Word::operator>(const Word& s2) const
{
  return !(wstring <= s2.wstring);
}

bool Word::operator>=(const Word& s2) const
{
  return !(wstring < s2.wstring);
}

// output of Word struct
ostream & operator<<(ostream & os, const Word & w)
{
  os << setw(20) << left << w.wstring
     << setw(3) << right << w.count << endl;
  return os;
}

#endif

Open in new window

// filename: bst2.h -- Class BST (for binary search tree)

#ifndef BST_H
#define BST_H

#include <iostream>
#include <cassert>
using namespace std;

//===============================================
// struct BinaryNode
//===============================================
template <typename T>
struct BinaryNode
{
  T element;
  BinaryNode *left;
  BinaryNode *right;

  BinaryNode( const T & theElement, BinaryNode *lt, BinaryNode *rt )
         : element( theElement ), left( lt ), right( rt ) { }
};

//===============================================
// class BST
//===============================================
template <typename T>
class BST
{
public:
  BST( ) : root(NULL), curSize(0) {}
  BST( const BST & rhs ) : curSize(rhs.curSize) { root = clone(rhs.root); }
  ~BST( ) { makeEmpty( ); }
  const BST & operator=( const BST & rhs );

  void insert( const T & x );  // (2) WRITE THIS METHOD
  void remove( const T & x ) { remove( x, root ); }
  void makeEmpty( ) { makeEmpty(root); }

  const T & findMin( ) const { assert(!isEmpty());  return findMin(root)->element; }
  const T & findMax( ) const { assert(!isEmpty());  return findMax(root)->element; }
  bool contains( const T & x ) const { return contains( x, root ); }

  T* find( const T & x ); // (1) WRITE THIS METHOD

  bool isEmpty( ) const { return (root == NULL); }
  int size() const { return curSize; }
  void printTree(ostream& out) const { printTree(root, out); out << endl; }

private:
  BinaryNode<T> *root;
  int curSize;

  // private functions -- most of them are called from their public
  // counterparts with 'root';
  void remove( const T & x, BinaryNode<T> * & t );
  BinaryNode<T> * findMin( BinaryNode<T> *t ) const;

  BinaryNode<T> * findMax( BinaryNode<T> *t ) const; // (3) WRITE THIS METHOD

  bool contains( const T & x, BinaryNode<T> *t ) const;
  void makeEmpty( BinaryNode<T> * & t );
  void printTree( BinaryNode<T> *t, ostream& out ) const;
  BinaryNode<T> * clone( BinaryNode<T> *t ) const;
};

template <typename T>
T* BST<T>::find( const T & x )
{
	BinaryNode<T> *ptr = root;
	while(ptr != NULL)
	{
		if(x == ptr->element)
			return &(ptr->element) // address of the 'element' member variable of the BinaryNode
		else if(x < ptr->element)
			ptr = ptr->left;
		else if(x > ptr->element)
			ptr = ptr->right;
	}
	return NULL;
}

/**
 * Insert x into the tree; duplicates are ignored.
 */
template <typename T>
void BST<T>::insert( const T & x )
{
	BinaryNode<T> *ptr = root;

	if( root == NULL)
		root = new BinaryNode<T>(x,NULL,NULL);
	else
	{
		while(ptr != NULL)
		{
			if(x < ptr->element)
			{
				if(ptr->left == NULL)
				{
					ptr->left = new BinaryNode<T>(x,NULL,NULL);
					ptr = NULL;
				}
				else
					ptr = ptr->left;
			}
			else// if (x > ptr->element)
			{
				if(ptr->right == NULL)
				{
					ptr->right = new BinaryNode<T>(x,NULL,NULL);
					ptr = NULL;
				}
				else
					ptr = ptr->right;
			}
		}
	}
}


/**
 * Internal method to test if an item is in a subtree.
 * x is item to search for.
 * t is the node that roots the subtree.
 */
template <typename T>
bool BST<T>::contains( const T & x, BinaryNode<T> *t ) const
{
  if( t == NULL )
    return false;
  else if( x < t->element )
    return contains( x, t->left );
  else if( t->element < x )
    return contains( x, t->right );
  else
    return true;    // Match
}

/**
 * Internal method to find the smallest item in a subtree t.
 * Return node containing the smallest item.
 */
template <typename T>
BinaryNode<T> * BST<T>::findMin( BinaryNode<T> *t ) const
{
  if( t == NULL )
    return NULL;
  if( t->left == NULL )
    return t;
  return findMin( t->left );
}

/**
 * Internal method to find the largest item in a subtree t.
 * Return node containing the largest item.
 */
template <typename T>
BinaryNode<T> * BST<T>::findMax( BinaryNode<T> *t ) const
{
  if( t == NULL )
    return NULL;
  if( t->right == NULL )
    return t;
  return findMax(t->right);
}

/**
 * Internal method to remove from a subtree.
 * x is the item to remove.
 * t is the node that roots the subtree.
 * Set the new root of the subtree.
 */
template <typename T>
void BST<T>::remove( const T & x, BinaryNode<T> * & t )
{
  if( t == NULL )
    return;   // Item not found; do nothing
  if( x < t->element )
    remove( x, t->left );
  else if( t->element < x )
    remove( x, t->right );
  else if( t->left != NULL && t->right != NULL ) // Two children
  {
    t->element = findMin( t->right )->element;
    remove( t->element, t->right );
  }
  else
  {
    BinaryNode<T> *oldNode = t;
    t = ( t->left != NULL ) ? t->left : t->right;
    delete oldNode;
    curSize--;
  }
}

/**
 * Internal method to make subtree empty.
 */
template <typename T>
void BST<T>::makeEmpty( BinaryNode<T> * & t )
{
  if( t != NULL )
  {
     makeEmpty( t->left );
     makeEmpty( t->right );
     delete t;
   }
   t = NULL;
}

/**
 * Deep copy.
 */
template <typename T>
const BST<T> & BST<T>::operator=( const BST<T> & rhs )
{
  if( this != &rhs )
  {
    makeEmpty( );
    root = clone( rhs.root );
  }
  return *this;
}

/**
 * Internal method to clone subtree.
 */
template <typename T>
BinaryNode<T> * BST<T>::clone( BinaryNode<T> *t ) const
{
  if( t == NULL )
    return NULL;

  return new BinaryNode<T>( t->element, clone( t->left ), clone( t->right ) );
}

/**
 * Internal method to print a subtree rooted at t in sorted order.
 */
template <typename T>
void BST<T>::printTree( BinaryNode<T> *t, ostream& out ) const
{
  if( t != NULL )
  {
    printTree( t->left, out );
    out << t->element;
    printTree( t->right, out );
  }
}

#endif

Open in new window

// filename: WordCountApp.cpp

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cctype>
using namespace std;

#include "word.h"
#include "bst2.h"

int main()
{
  ifstream fin;
  ofstream fout;

  fin.open("review.txt");
  if (!fin) 
  {
    cerr << "Input file opening error\n";
    exit(1);
  }

  fout.open("words.txt");
  if (!fout) 
  {
    cerr << "Output file opening error\n";
    exit(1);
  }

  BST<Word> bst;
  int total = 0;
  string s;

  while (fin >> s) 
  {
	  total++;

	  Word *ptr;
	  ptr = bst.find(s);
	  if(*ptr != s)
		  bst.insert(s);
  }

  cout << "Total number of words read:   "
       << total << endl;
  cout << "Total number of unique words: "
       << bst.size() << endl;
  cout << endl;

  Word maxWord = bst.findMax();
  cout << "** FindMax returns \"" << maxWord.wstring << "\", "
                                  << maxWord.count << endl << endl;
  bst.printTree(fout);

  fin.close();
  fout.close();

  system("pause");
  return 0;
}

Open in new window

0
villmund
Asked:
villmund
  • 13
  • 7
  • 2
1 Solution
 
phoffricCommented:
You are crashing, aren't you?

Are you constrained to use the two header files intact except to add find and insert implementation?

You should be using a debugger to help you. If no debugger, then at least add this code just to make sure you expect this contructor to be called when you expect it to be called.
    // Constructor
    Word(const string& s = "", int cnt = 0) : wstring(s), count(cnt) {
        cout << "Word ctor: s = " << s << "  cnt = " << cnt << endl;
    }

But a debugger may be essential. Put a break in this function:
      bool Word::operator!=(const Word& s2) const
{
    return !(wstring == s2.wstring);
}
and examine the values.

>> You do so by first creating a Word object (as a local variable) and calling the find method in bst.
   I didn't see where you were doing this in the main function.

I will be back tomorrow (maybe a little bit later).
0
 
sarabandeCommented:
you should use a different name for the 'wstring' member.

'wstring' is a typedef for basic_string<wchar_t> and it probably gives problems to use it for a variable. you also shouldn't have the using namespace std; clause in word.h but use std:: prefix in headers.

Sara
0
 
villmundAuthor Commented:
I am not allowed to change the two header files other than change/ use the insert and find functions.
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
phoffricCommented:
Your program crashed when I ran it using VS 2010 Express. It crahsed right at the breakpoint that I noted above.
0
 
villmundAuthor Commented:
That is strange. I can run my program and can get it to print out all words in a txt file, but I don't how to check for unique words.
0
 
phoffricCommented:
What OS and debugger do you use? Maybe I'll be able to switch.

Since you are not crashing (and I am getting an Memory Access Violation) then in addition to the Word constructor debug noted above, add the following debug:
bool Word::operator!=(const Word& s2) const 
{   
    cout << "operator!= :: s2.wstring = " << s2.wstring << endl;
    cout << "operator!= :: wstring = " << wstring << endl;
    return !(wstring == s2.wstring); 
}

Open in new window

As usual, you should be able to predict what the debug will write before you actually run it. Are you getting what you expected?
0
 
phoffricCommented:
You wrote:
        ptr = bst.find(s);
        if(*ptr != s)

Open in new window

but bst.find has
    return NULL;

Open in new window

So, sometimes ptr is NULL, and *ptr is trying to derereference NULL. This alone should cause a crash. However, I am crashing before this dererencing even occurs.

Could it be that the code that runs for you is different than what is posted? If so, then on the first call to bst.find(s), your tree root is NULL, and the returned ptr is NULL. Is that what you find also? Add debug if you do not know.
0
 
villmundAuthor Commented:
I had some parts commented out when I ran it, that is why it ran. What should I switch the return code to be?
0
 
phoffricCommented:
Returning NULL when the tree is empty seems to make sense. If the tree is empty, then just insert. But, I suspect that your program is doing some (possibly subtle) things that you may be unaware of. Even though you are constrained to use the implementations provided to you, you have to take ownership of the code. So, for starters, you should add the debug and make sure you understand what is going on.

Please only discuss code that you posted as it will cause confusion and take longer to resolve your problems.

Also, you didn't address this comment in the first post:
>> You do so by first creating a Word object (as a local variable) and calling the find method in bst.
   I didn't see where you were doing this in the main function.

Maybe the code you are running does this. But again, if what you are running is different than what you posted, we are obviously out of sync.
0
 
villmundAuthor Commented:
I don't understand what to do with the count. I thought that Word *ptr was what I needed to count the same word up. What I have below is what I have right now in my main.cpp. I have my "if" statement (inside my while loop) check for NULL but if I already have the word in the list, I want to add to that unique word's count.

What prints out right now in a .txt file is all the unique words but they don't count up. Once I can get them to count the occurences of each unique word I will be done. You don't need to write the code for me, I just need help understanding what I should do.

I didn't change my insert or find (except i forgot a semi colon in a line of my find function)
// filename: WordCountApp.cpp

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cctype>
using namespace std;

#include "word.h"
#include "bst2.h"

string checkPunct(string &s);
string lowerCase(string &s);

int main()
{
  ifstream fin;
  ofstream fout;

  fin.open("review.txt");
  if (!fin) 
  {
    cerr << "Input file opening error\n";
    exit(1);
  }

  fout.open("words.txt");
  if (!fout) 
  {
    cerr << "Output file opening error\n";
    exit(1);
  }

  BST<Word> bst;
  int total = 0;
  string s;

  while (fin >> s) 
  {
	  checkPunct(s);
	  lowerCase(s);
	  total++;

	  Word *ptr;
	  ptr = bst.find(s);
	  if(ptr == NULL)
		  bst.insert(s);
	  //else
		  //add to count of the word
  }

  cout << "Total number of words read:   "
       << total << endl;
  cout << "Total number of unique words: "
       << bst.size() << endl;
  cout << endl;

  Word maxWord = bst.findMax();
  cout << "** FindMax returns \"" << maxWord.wstring << "\", "
                                  << maxWord.count << endl << endl;
  bst.printTree(fout);

  fin.close();
  fout.close();

  system("pause");
  return 0;
}

string checkPunct(string &s)
{
	string::iterator t = s.begin();

	while(t != s.end())
	{
		if(ispunct(*t))
		{
			t = s.erase(t);
		}
		else
			break;
	}

	t = s.end();
	t--;
	while(t != s.begin())
	{
		if(ispunct(*t))
		{
			t-- = s.erase(t);
		}
		else
			break;
	}
	return s;
}

string lowerCase(string &s)
{
	string::iterator t = s.begin();

	while(t != s.end())
	{
		*t = tolower(*t); 
		t++;
	}
	return s;
}

Open in new window

0
 
phoffricCommented:
I'm back for a minute, and will return tomorrow (or maybe a minute in a couple of hours).

You didn't address this comment in the first post:
>> >> You do so by first creating a Word object (as a local variable) and calling the find method in bst.
>>   I didn't see where you were doing this in the main function.

The implied question is: Where are you "first creating a Word object (as a local variable)"?

Also think about what T is in
T* find( const T & x )
0
 
phoffricCommented:
>> I don't understand what to do with the count.
When you find the word using find(), then you can increment count right there.
0
 
phoffricCommented:
I added the line of code to increment count in find(). The result was that the file showed a count that was one less than the number of occurences. So, I modified the Word constructor to initialize the count to 1 rather than 0, and then the file produced the correct count of words.
0
 
villmundAuthor Commented:
how did you increment the count in the find?
0
 
phoffricCommented:
You defined element as:
template <typename T>
struct BinaryNode
{
  T element;

Open in new window

When you find a word match in find, you return:
return &(ptr->element);

Open in new window

Right before the return statement, you increment count.

Hopefully, this is clear to you. If not, then if you use the VS C++ debugger, then you can highlight ptr->element and see its value when you hit the breakpoint on find's return statement.

If you do not have it, you can download Visual Studio Expresss C++ 2010 from:
        http://www.microsoft.com/express/Downloads/

If you are not familiar with this debugger, then here are three articles (all of which applies to VS 2010). To quickly get started (about 15 minutes learning curve), you can read:

   C/C++ Beginner's Debugging Guide

After becoming familiar with the basics, move onto these two articles:

   Breakpoint Tips for C/C++

   Watch, Memory, Stack Tips: C/C++

Since you are developing pretty complicated programs, using this debugger will help you greatly in your programming endeavors.
0
 
villmundAuthor Commented:
Thank you for all the help and for being patient with me.
0
 
sarabandeCommented:
here is where you recognize a word already was found before:

if(x == ptr->element)

Open in new window


and there you should increment the ptr->count.

note, as you have now two statements after the if statement, the incrementing of count and the return of the element), the two statements need to be put into a {}-block.

Sara
0
 
phoffricCommented:
Original code:
  if(x == ptr->element)
      return &(ptr->element);

Open in new window

I wrote:
When you find a word match in find, you return:
return &(ptr->element);

Open in new window

you wrote:
here is where you recognize a word already was found before:
if(x == ptr->element) 

Open in new window

I don't see any added value to what I already wrote. Also, this code is fairly complicated, and as it is homework, we want the author to learn by trying things out and asking questions when he gets stuck.

>>the two statements need to be put into a {}-block.
This author, as you already know from previous questions, is quite adept at C++ language syntax. This obviously is well within his capababilities. Once again, your comment requires me to RA to remove your superfluous and misleading comments.
0
 
phoffricCommented:
And then I wrote:
  Right before the return statement, you increment count.
0
 
phoffricCommented:
If you installed VS C++ and ran the debugger to the suggested breakpoint, and highlighted
    ptr->element
then you would see exactly the correct way to increment the word count.

The only other comment that I was trying to make was that bst.find takes a Word argument. When you pass in a string argument instead, then your constructors handle that. But your requirement was
"You look up the word in the BST. You do so by first creating a Word object (as a local variable) and calling the find method in bst."

This suggests that the word object be created before calling find, and then you pass in the word object rather than your string.
0
 
villmundAuthor Commented:
I understand what you are saying. My teacher won't care that I did it a little differently though.
0
 
phoffricCommented:
Ok, glad you got it working :)
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

  • 13
  • 7
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now