This week's book giveaway is in the Servlets forum.
We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line!
See this thread for details.
The moose likes Java in General and the fly likes Binary search tree questions... Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Binary search tree questions..." Watch "Binary search tree questions..." New topic
Author

Binary search tree questions...

Adam Ellsworth
Greenhorn

Joined: Sep 25, 2004
Posts: 21
I have a few questions on an assignment dealing with binary search trees and English-Latin vocab words. Here's the instructions for better understanding for my questions that will come afterwards



Each unit in a Latin textbook contains a Latin-English vocabulary of words which have been used for the first time in a particular unit. Write a program that converts a set of such vocabularies stored in file Latin into a set of English-Latin vocabularies. Make the following assumptions:

a. Unit names are preceded by a percentage symbol.
b. There is only one entry per line.
c. A Latin word is seperated by a colon from its English quivalent(s); if there is more than one equivalent, they are seperated by a comma.

To output English words in alphabetical order, create a binary serach tree for each unit containing English words and linked lists of Latin equivalents. Make sure that there is only one node for each English word in the tree. For example, there is only one node for and is used twice in unit 6: with words ac and atque. After the task has been completed for a given unit (that is, the content of the tree has been stored in an output file), delete the tree along with all linked lists from computer memory before creating a tree for the next unit.

Here is an example of a file containing Latin-English vocabularies:

%Unit 5
ante : before, in front of, previously
antiquus : ancient
ardeo : burn, be on fire, desire
arma : arms, weapons
aurum : gold
aureus : golden, of gold

%Unit 6
animal : animal
Athenae : Athens
atque : and
ac : and
aurora : dawn

%Unit 7
amo : love
amor : love
annus : year
Asia : Asia

From these units, the program should generate the following output:

%Unit 5
ancient : antiquus
arms : arma
be on fire : ardeo
before : ante
burn : ardeo
desire : ardeo
gold : aurum
golden : aureus
previously : ante
weapons : arma

%Unit 6
Athens : Athenae
and : ac, atque
animal : animal
dawn : aurora

%Unit 7
Asia : Asia
love : amor, amo
year : annus


Ok, now a few questions. I'm not lookin for the answer to the problem, just want a few questions answered to get me goin in the right direction

1) Would you put the elements into the tree in order? Or would you put them in the tree, then make some loops to swap the values to get them in order?

2) Which would be the parent nodes, the latin or the english words?

3) How do you go about putting linked lists into the tree?

These are just a few to get me headed in the right direction, lol. Thanks for any help in advance!
Adam Ellsworth
Greenhorn

Joined: Sep 25, 2004
Posts: 21
Kind of a bump

But the biggest problem I am having is I'm not sure how to associate 3 or more strings to one node...

For instance:

ardeo : burn, be on fire, desire...

What would that part of the tree look like?
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
All binary trees have a Node class with a key or identity and pointers to left and right nodes for smaller and larger identities. I'd make the identity the English word, and add a list of Latin words. I'm being vague because I want you to enjoy figuring it out Lemme know if you need more.


A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Joel McNary
Bartender

Joined: Aug 20, 2001
Posts: 1817

1) Would you put the elements into the tree in order? Or would you put them in the tree, then make some loops to swap the values to get them in order?


With a well-built Binary Tree, it won't matter what order you put the words into the tree in. However, with a basic implementation, it is actually better to put the words in randomly rather than in order.


Piscis Babelis est parvus, flavus, et hiridicus, et est probabiliter insolitissima raritas in toto mundo.
Adam Ellsworth
Greenhorn

Joined: Sep 25, 2004
Posts: 21
"All binary trees have a Node class with a key or identity and pointers to left and right nodes for smaller and larger identities. I'd make the identity the English word, and add a list of Latin words. I'm being vague because I want you to enjoy figuring it out Lemme know if you need more."

Hehe. Yeah, I understand how trees work, but just don't get this one. The Unit 5 would be the root and lets say 'before' would be the first node on the left and 'arms' will be the one on the right. Now the Latin word for before is 'ante' so it will be the left pointer to the node 'before'. The latin word for 'arms' is 'arma' and would be the left pointer for the node 'arms'. Now what happens to lets say 'aurum'? If it goes on the right pointer of the node 'before', wouldn't it be associated with 'before' instead of 'gold' like it should be? I don't understand how to make the second level of the tree and that is whats causin me the grief

Thanks again
Adam Ellsworth
Greenhorn

Joined: Sep 25, 2004
Posts: 21
I mixed up the 'before' and 'arms' nodes, they should be switched to make it a working binary search tree Just sayin to let ya know that I kind of know what I'm talkin about, hehe.
David Harkness
Ranch Hand

Joined: Aug 07, 2003
Posts: 1646
You can work backwards from the desired output to help figure out how to store the words. Binary search trees help you order elements, and the output requires the English words to be in order. Attached to each English word is a list of one or more Latin words.

Here's another hint: you only see each Latin word once, so you don't need to look them up, while you may see an English word more than once.

The Java Collections framework has two classes that would be useful here (though I assume your assignment is to build your own BST): TreeSet and TreeMap. TreeSet holds an ordered set (no duplicates) of objects. You would create a class to hold the English word and its LinkedList of Latin equivalents. TreeMap holds an ordered set of keys, each mapped to a single Object value.

Does any of that help?
Adam Ellsworth
Greenhorn

Joined: Sep 25, 2004
Posts: 21
Sounds like TreeMap would be useful, but unfortunately, I think we do have to build our own BST. Still not gettin how to store them, but I'll try to work backwards like you suggested and see how that works. Thanks for the help, I'm sure I'll be back, lol.
Adam Ellsworth
Greenhorn

Joined: Sep 25, 2004
Posts: 21
"Attached to each English word is a list of one or more Latin words."

Thats what I can't figure out how to do. Do I have to use the treeSet for that? Or is it possible to associate a linked list with a node without using it?
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Ah, that just means that one variable on the Node is some kind of collection of words. Array, Set, ArrayList ... your choice! You might like an ordered Set so you can report them in alpha order. Let us know how this is shaping up ... show code again!
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Is this for a data structure class? If so, then you may not be allowed to use any of Java's built-in classes. However, you've probably already implemented most of them on your own some time during the semester. Still, the previous discussion of the Java Collection API may help you figure out how to implement your tree. For example, you can borrow ideas from TreeMap and implement them yourselves. Specifically, you may want each node to contain two things: the English word and a list of Latin words. If you are allowed, you can use ArrayList as suggested above. Otherwise, you may need to implement your own linked list structure (if you haven't done this already, that is).

HTH

Layne


Java API Documentation
The Java Tutorial
Adam Ellsworth
Greenhorn

Joined: Sep 25, 2004
Posts: 21
Thanks for the help

I'm usually not one to complain about professors, but this one is absolutely terrible He doesn't teach at all and refuses to answer any questions. A class consists of him READING straight off of the powerpoint presentataion the that the books company sent him So currently I'm trying hard to teach myself how to use the treeMap. Think I got everything stored in there so far but still having troubles adding a latin word to an already exsisting english word. Also havin trouble writing to the file.

It is a data structures class but I sent him an email today asking if we could use treeMap...he didn't answer yet, go figure, hehe.

Here is my code so far, it is very rough at the moment and not working too smooth, so bear with me and yell at me if I'm headed in the wrong direction anywhere, hehe.

Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Since it is a data structures class, you are probably not allowed to use TreeMap or the other built-in classes. However, now that you've done it using them, perhaps you have an idea of the features you need to implement in your own binary tree data structure.

Let us know if you have any more questions.

Layne
David Harkness
Ranch Hand

Joined: Aug 07, 2003
Posts: 1646
Originally posted by Adam Ellsworth:
In Java, an object instance may be assigned to a variable of type X if the object's class is a subclass of class X or implements interface X. I can't make that make sense in words. Thus, you can safely call treeMap.put(aString, anArrayList) since String and ArrayList are both subclasses of Object. In fact, Object is the root class, meaning every class has Object as its ancestor.

You could put anything into the TreeMap, even another TreeMap. Don't get stuck thinking that objects must be single-valued entities.
Adam Ellsworth
Greenhorn

Joined: Sep 25, 2004
Posts: 21
Just got the email back and we aren't allowed using treeMaps,I knew they were too good to be true, lol. I was thinking about how to use a regular tree for this and was wondering if it would be possible to do something like this:




I know what I'm thinkin, just having trouble explaining it Would it be possible to add a third "pointer" to an eglish node and just not "visit" it when printing them out in order? Let me know if you know what I'm talkin about, cause I know it sounds confusing
Adam Ellsworth
Greenhorn

Joined: Sep 25, 2004
Posts: 21
Ok, makin some progress. I have three things to fix before its complete though. Here they are:

1) How do you clear/make a new tree when I encounter the "%Unit5-7"? Need to make seperate trees, not 1 big one

2) The treeContains() needs fixed to check for duplicate nodes. Instead of making a list or an array, I kinda took the short cut. Instead of putting the english word node in, then the Latin node, I simply combined them and made it into one string making one node. Only problem with that is it causes the treeContains() not to work because it only searches for the english word, not the whole string.

3) I need to output it to a file but can't do it. I can't even do something like out.write("Blah"); Nothing appears in the file. You can check my Stream in the code below. I need to be able to output the tree and just lines. Heres the code:

 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Binary search tree questions...
 
Similar Threads
a limitation of english
probly
Vocabulary building
Need help outputting to a text file...
Translation and language comparison