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

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

# 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) {}

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
``````
``````// 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 )
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
``````
``````// 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;
}
``````
0
villmund
• 13
• 7
• 2
1 Solution

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

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

Author Commented:
I am not allowed to change the two header files other than change/ use the insert and find functions.
0

Commented:
Your program crashed when I ran it using VS 2010 Express. It crahsed right at the breakpoint that I noted above.
0

Author 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

Commented:
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);
}
``````
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

Commented:
You wrote:
``````        ptr = bst.find(s);
if(*ptr != s)
``````
but bst.find has
``````    return NULL;
``````
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

Author 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

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

Author 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;
}
``````
0

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

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

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

Author Commented:
how did you increment the count in the find?
0

Commented:
You defined element as:
``````template <typename T>
struct BinaryNode
{
T element;
``````
When you find a word match in find, you return:
``````return &(ptr->element);
``````
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:

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

Author Commented:
Thank you for all the help and for being patient with me.
0

Commented:
here is where you recognize a word already was found before:

``````if(x == ptr->element)
``````

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

Commented:
Original code:
``````  if(x == ptr->element)
return &(ptr->element);
``````
I wrote:
When you find a word match in find, you return:
``````return &(ptr->element);
``````
you wrote:
here is where you recognize a word already was found before:
``````if(x == ptr->element)
``````
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

Commented:
And then I wrote:
Right before the return statement, you increment count.
0

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

Author Commented:
I understand what you are saying. My teacher won't care that I did it a little differently though.
0

Commented:
Ok, glad you got it working :)
0

## Featured Post

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