Stumped on a Programming Assignment using Binary Search Trees
I have an assignment due for a Java Data Structures class and I am stuck with no idea how to proceed. Here are the specifics:
====================================================
Implement a Binary Search Tree that will store a sequence of words. The tree will maintain a unique set of words read in from a text file. Case does not matter (揟he?is the same as 搕he?.
For this exercise, there is no requirement to take care of punctuation in the input file. If you do handle punctuation, you will receive extra credit.
Each node in the tree will keep a tally of how many times the word appears in the file.
When a word is read in from the file, add it to the tree. If the word is already in the tree, increment its count.
Once the tree is built, the user can search for a word. The output will either report
that the word is not in the tree, or if it is, how many occurrences of the word there are.
The user can delete an occurrence of a word. If the deletion causes the count to be zero, delete the node with that word from the tree. When the user deletes a word, print the word and its remaining frequency and if it is removed from the tree, print a message stating what word has been deleted from the tree.
Provide a way to both print an inorder traversal of the tree and save an inorder traversal to a file. The input file should be stored in the root of C and called 搃nwords.txt?and the output file should be in the root of C and called 搊utwords.txt?.
Example:
inwords.txt
The cat traveled up the tree after the big dog. The cat was fast but the dog was also fast.
the 5
cat 2traveled 1
after 1dog 2 up 1
big 1fast 2tree 1 was 2
also 1but 1
Create a class called Word. Word will have two fields the actual String word and an int to hold the number of occurrences. The BST will hold Binary Nodes. The data part of the node is a Word object.
==================================================
The things I have done:
1) Read sentence in from text file.
2) Converted the sentence to lower case.
3) Implemented a Tokenizer to break up the sentence into Word objects.
4) Created a Word class that holds a String and an int.
I am kind of lost after that. I am looking for any information anyone can offer to help me break this programmer's block I have.
[2417 byte] By [
hughveala] at [2007-11-27 9:03:56]
Aaaaaaaggggggh! My eyes.Using bold does not make us want to help any more than not using bold.
I'd like to help out some more, but I'm about to leave work, but I found this nice link
that might help you out with your problem
http://www.java-tips.org/java-se-tips/java.lang/binary-search-tree-implementation-in-java.html
Read it, and see if that helps, I think you will like it.
A piece of advice - Read it, UNDERSTAND it, type it and adapt it, don't just
copy-paste it. The only way to learn it is that you UNDERSTAND it, and by
Typing it, you reinforce that learning.
Good luck on your homework.
Another piece of advice - Try using the "split()" method of the String object
instead of the Tokenizer.
Cya L8r.
Next step would be to implement the Binary Search Tree that can hold a Word class as the value of a node.Good luck.
dwga at 2007-7-12 21:36:30 >
That is the trouble I am having right now.
import java.util.Scanner;
import java.io.*;
import java.util.StringTokenizer;
public class TestDriver2
{
public static void main(String[] args) throws IOException
{
BinarySearchTree bST = new BinarySearchTree();
Word wrd1 = new Word();
Word wrd2 = new Word();
int tracker;
String inFileName = "inwords.txt";
BufferedReader inFile = new BufferedReader (new FileReader (inFileName));
String liner = inFile.readLine();
liner = liner.toLowerCase();
System.out.println("The passage that was read from infile is : " + liner);
StringTokenizer strTokenizer = new StringTokenizer (liner, "., ");
while (strTokenizer.hasMoreTokens())
{
tracker = 0;
wrd1 = new Word(strTokenizer.nextToken(),tracker++);
//The line below is where the trouble is.
//If I use wrd1.getWord() instead it adds just the string and not the int
bST.addElement(wrd1);
}
System.out.println("BST is: " + bST);
}
} // main
// class BinarySearchTree
This gives the following error:
TestDriver2.java:32: addElement(java.lang.Comparable) in BinarySearchTree cannot be applied to (Word)
bST.addElement(wrd1);
^
Did you read the error message?This is how you coded your add element method:addElement(java.lang.Comparable) And this is how you are calling it:addElement(wrd1); What type is your method expecting as a parameter and what type are you sending it?
Here is the method:
public void addElement (Comparable element)
{
BinaryTreeNode temp = new BinaryTreeNode (element);
if (isEmpty())
root = temp;
else
{
BinaryTreeNode current = root;
boolean added = false;
while (!added)
{
if (element.compareTo(current.element) < 0)
if (current.left == null)
{
current.left = temp;
added = true;
} //if
else
current = current.left;
else
if (current.right == null)
{
current.right = temp;
added = true;
} //if
else
current = current.right;
}//while
}//else
count++;
} // method addElement
I tried changing the type of the parameter to T, but it didn't work.
Well, Word apparently doesn't implement Comparable, and you've written your BST.addElement method to take an argument of type Comparable. (Or rather, your professor did, because if you had written it, you'd realize it.)That's what caused the syntax error.
But....I don't think the solution is to make Word implement Comparable. When you think about it, it doesn't really make sense to add Word objects to your BST. The Word objects hold a String and an int for the count, right? The BST nodes' data fields hold Word objects. You're not trying to count Word objects; you're using Word objects to count Strings. So it would make more sense to call addElement with a String argument...and String already implements Comparable.
That is why when I first tried this I used wrd1.getWord(), which is a method I created for my Word class. My questions is: How will the number of occurences be tracked with the particular string if I don't pass it as well?
For flounder:
/*
Word class
*/
public class Word //implements Comparable<Word>
{
private String Phrase;
private int counter;
//Empty Constructor
public Word()
{
Phrase = null;
counter = 0;
}
//constructor with 2 arguments
public Word(String phr, int cnt)
{
Phrase = phr;
counter = cnt;
}
//Constructor with one argument
public Word(String phr)
{
Phrase = phr;
counter = 0;
}
//equals() method
public boolean equals(Word looking)
{
boolean status;
if(Phrase.equals(looking.Phrase)&& (counter != looking.counter))
status = true;
else
status = false;
return status;
}
//compareTo method
/*public int compareTo(Word comp)
{
if (comp.Phrase == ((Word) comp).Phrase)
return 0;
else if ((comp.Phrase) > ((Word) comp).Phrase)
return 1;
else
return -1;
}*/
//toString method
public String toString()
{
String describer = Phrase + ", " + counter;
return describer;
}
//setPhrase
public void setPhrase(String p)
{
Phrase = p;
}
//setCount
public void setCount(int c)
{
counter = c;
}
//getword
public String getWord()
{
return Phrase;
}
//getcount
public int getCount()
{
return counter;
}
//incword
public void incword()
{
counter++;
}
//decword
public void decword()
{
counter--;
}
}
//implements Comparable<Word>and you wonder why the compiler complains?
Using the generic form:implements Comparable gave me an abstract override error. Doing it this way allows the type to be recognized. Or so I thought.
> My questions is: How will the number of
> occurences be tracked with the particular string if I
> don't pass it as well?
That question makes no sense.
Think about it: the whole point of the BST is to do the counting. When you call addElement, you're passing a single thing to be counted. If you were to pass a number with it (as Word uses), the number would be 1 each time.
Did you write the BST? It seems odd to me that the addElement would take a Comparable, but it would add the element to an object (Word) that takes specifically a String (and not a Comparable).
The BST was a given portion of the project, taken directly from the textbook.
I think I just got the gist of what you are saying. Instead of keeping track of the count, I can just use the find command to increment the count each time the count is needed. Is that what you meant?
Message was edited by:
hughveal
No, I mean:
1) The BST does the counting. You do not need to pass a count value into addElement, within a Word object or otherwise. So don't pass addElement a Word, pass it a String (namely the word being counted).
2) Within the BST, there is some functionality that finds the node holding the word, or if it's not there, figures out where it should go.
2.1) if the node is found, it:
2.1.1) gets the Word object
2.1.2) increments the counter in the Word object. The Word class should have an "increment" method or the like, by the way.
2.2) if the node is not found, it:
2.2.1) creates a new Word object, with the counter set to one, and the word set to the word being searched for
2.2.2) creates a new BST node, with the data being set to the new Word object.
OK. I have a good understanding of that, but here is what has halted all my progress.
Word lobjWord = bST.find(wrd1);
EVerytime I run this I get the following error and I don't know where to go fix it.
TestDriver2.java:33: incompatible types
found: java.lang.Object
required: Word
Word lobjWord = bST.find(wrd1);
I have tried to modify the find method and also changed the wrd1 to wrd1.getWord() to just pull the string and nothing else. Any ideas?
I don't know what the API for bST.find is. Does it specify that it takes a Word parameter and returns Object? Or what?
I'm going to guess for now. Let's say it takes an Object and returns an Object.
Then you are telling it you are expecting it to return a Word instead of Object. If the object it returns really is a Word (or a subclass of Word), then you can still get it to work by casting it.
Word lobjWord = (Word) bST.find(wrd1);
The header for find is:public Object find(Comparable targetElemewnt) throws ElementNotFoundException
> The header for find is:> ...Then code it with the cast like I suggested.Note that then it will compile, but if at runtime the object returned really isn't a Word, then you'll get a runtime exception.
