Solved

# Binary Search Tree Functions

Posted on 2011-05-12
898 Views
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
Question by:villmund

LVL 31

Expert Comment

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

LVL 32

Expert Comment

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 Comment

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

LVL 31

Expert Comment

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

Author Comment

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

LVL 31

Expert Comment

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

LVL 31

Expert Comment

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 Comment

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

LVL 31

Expert Comment

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 Comment

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

LVL 31

Expert Comment

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

LVL 31

Expert Comment

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

LVL 31

Expert Comment

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 Comment

how did you increment the count in the find?
0

LVL 31

Accepted Solution

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 Comment

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

LVL 32

Expert Comment

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

LVL 31

Expert Comment

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

LVL 31

Expert Comment

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

LVL 31

Expert Comment

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 Comment

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

LVL 31

Expert Comment

Ok, glad you got it working :)
0

## Featured Post

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address.Â This address might be address of another variable/address of devices/address of fuâ€¦
Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every montâ€¦
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Botâ€¦