aspose file tools*
The moose likes Java in General and the fly likes Hey guys, A little help with binary trees Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Hey guys, A little help with binary trees" Watch "Hey guys, A little help with binary trees" New topic
Author

Hey guys, A little help with binary trees

Chas Martin
Greenhorn

Joined: Oct 07, 2008
Posts: 18
Hi all, I here for a little help again.
I have an assignment that requires me to take in a .txt file like this:


I am supposed to read this in and print out the in-order, pre-order and post order.
The thing I am stuck on is getting it to look at the strings and lexicographically compare two strings. There is a compare method but I cant figure out how to make it work. Once I get that done, I dont think I'll have any problem getting it to print out the finished product which should look like this:


Does anybody know how to use the compare method because I am stuck bad! any help will be very appreciated.
Thank you all so much
--Chas
marc weber
Sheriff

Joined: Aug 31, 2004
Posts: 11343

Originally posted by Chas Martin:
... The thing I am stuck on is getting it to look at the strings and lexicographically compare two strings. There is a compare method but I cant figure out how to make it work...

Do you mean the compareTo method in the String class? As the API says...
The character sequence represented by this String object is compared lexicographically to the character sequence represented by the argument string. The result is a negative integer if this String object lexicographically precedes the argument string. The result is a positive integer if this String object lexicographically follows the argument string. The result is zero if the strings are equal...

What does this mean? Consider...

  • If i is less than zero, that means str1 comes before str2.
  • If i is zero, that means the strings are equal.
  • If i is greater than zero, that means str1 comes after str2.


  • "We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." ~Joe Strummer
    sscce.org
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38902
        
      23
    The String#compareToIgnoreCase method is similar, but you might find it useful.
    Chas Martin
    Greenhorn

    Joined: Oct 07, 2008
    Posts: 18
    I have this so far but Its skipping every other line


    When I run it I get this :


    How do I make it hit every line. Thanks for the help guys, I am a complete beginner so I can't go to far without getting stuck.
    Thanks,
    --Chas
    Mark Vedder
    Ranch Hand

    Joined: Dec 17, 2003
    Posts: 624

    Originally posted by Chas Martin:
    I have this so far but Its skipping every other line

    How do I make it hit every line.


    It is hitting each line. The question you want to ask yourself is "Am I processing every line?" You read in name, and then nextName. Do you handle both completely?

    You also have another pretty significant bug looming. Currently it does not surface because you have an even number of names in your list. Either add one name or remove one name from the "names.txt" file so it has an odd number of lines (not just an odd number of names, but an odd number of lines including any empty lines) and run your code. See what happens. Why do you think that is?

    Hint... what does the scanner.next() method do if there are no more tokens on the current line? Answering that question should help you fix both bugs.
    Chas Martin
    Greenhorn

    Joined: Oct 07, 2008
    Posts: 18
    Thanks for the help but I still cannot figure it out. I have tried everything I can possibly think of.
    It still just keeps printing out every other comparison.
    Im not sure and I cant find any info that tells me what the sc.next method does when there are no more tokens.
    I have hit a wall and am so confused!
    Can you give me a few more hints?
    Thanks guys
    Mark Vedder
    Ranch Hand

    Joined: Dec 17, 2003
    Posts: 624

    Originally posted by Chas Martin:

    Im not sure and I cant find any info that tells me what the sc.next method does when there are no more tokens.


    Sometimes in programming, you will not directly find the answer to a question like "what happens if...". So you need to do some experimenting to find the answer on your own. But to me, and many other developers, that's what makes programming fun. So let's run a little experiment:



    If you run that, you will see the following output.

    one
    alpha
    two
    bravo
    three

    Don't just take my word for it. Enter that and run it yourself. The best way to learn something and retain it is to do it yourself.

    Now... look at the code above... do you see anything that tells the scanner to go to the next line? nope. The only method we are calling on scanner is the next() method. But yet we are reading words (or tokens) from multiple lines. What does that tell us about what the next() method does when there are no more tokens on the current line?

    In the code, change the number in the for loop to the number of lines (10) and see what happens. Change it to the number of tokens in the file (20) and see what happens. Change it to a number greater than the number of tokens, say 100. What happens? Why did that happen?


    Ok, now let's up the stakes a little. We want to read the whole file. All the tokens. But what happens if we do not know how many tokens are in the file? Well, the Scanner Class has ways of telling us when there is nothing else to read. You have discovered one of them. But there are other ways. What are they? Take a look at the documentation. The one you are using may not be the best choice for you.

    A good way to approach things when you are having trouble is to start very small. Just tackle one simple thing in the problem. The first step as it were. Here, start with writing a program that reads the file and outputs all the tokens one after the other. Do not worry about the sorting at first. Just output each token. Kind of like what I did above, but where it outputs each token and all tokens regardless of how many are in the file. Test it on a file with an even number of names, one with an odd number of names, one with only one name, and then a file with no names at all (i.e. an empty file). Testing using all four of those files will ensure you don't have any major issues. Once you have done that, you can go to the next step of adding some of the basic sorting.

    And doing this might help you resolve the every other error you are getting. Keep the code very simple. In fact, you can actually do it by only changing one line of code in the above example. Once you have that working, try adding some basic sorting. Do a little at a time. If suddenly you start seeing only every other line, you will know what it was you did to cause it.

    Be sure to post your solution -- whether its the full solution or just the solution to this first part -- so we can verify it for you.
    [ December 09, 2008: Message edited by: Mark Vedder ]
    ramya narayanan
    Ranch Hand

    Joined: Oct 06, 2008
    Posts: 338
    Mark, apart from the problem the way you prescribed to solve the issue or problem is educating.
    M'ile one thing I haven't got from this post is

    What is the pre-order and post-order he is saying.
    What is the logic behind that?

    Regards.
    ramya narayanan
    Ranch Hand

    Joined: Oct 06, 2008
    Posts: 338
    Take a look at the documentation. The one you are using may not be the best choice for you.


    The reason I've found out is that it may throw java.util.NoSuchElementException when we use while(sc.hasNextLine()).
    The reason being when I include some additional lines after last element in inputs.txt it will throw these exception.

    Am I right Mark Vedder?

    inputs.txt:

    Note the included blank lines after eleven sai

    javacode:


    output:


    Well, the Scanner Class has ways of telling us when there is nothing else to read.

    Going through the docs & soon will find it out.
    But anyhow any guess or hints will be appreciated
    Regards.
    Mark Vedder
    Ranch Hand

    Joined: Dec 17, 2003
    Posts: 624

    Originally posted by ramya narayanan:
    What is the pre-order and post-order he is saying.
    What is the logic behind that?


    That's referring to the possible ways to traverse a binary tree. The Wikipedia Binary Tree Article has a section that explains it better than I could.




    Originally posted by ramya narayanan:

    The reason I've found out is that it may throw java.util.NoSuchElementException when we use while(sc.hasNextLine()).
    The reason being when I include some additional lines after last element in inputs.txt it will throw these exception.
    Am I right Mark Vedder?


    In this case, yes; that is correct. The hasNextLine() method tells us if there is a next line or not. But we are not reading the text in a full line at a time. At first, it appears that we are. But that's only because in the original problem there was only one name per line. But we are using the next() method to do the reading. The next() method reads the next Token; not the next line. So if we use the hasNextLine() method along with the next() method, we are mixing processing methodologies. One methodology is working with lines (checking for the existence of a line and not a next token {hint hint}) while the other is working with tokens (reading token by token and not line by line).

    We want to setup our code so we read the same thing (either a line or a token) and check if any more of that thing (a line or a token) exists. But we don't want to mix them. In other words, we don't want to check for a line and read by token; nor do we want to check for a token and read by a line. While we could, we would have to compensate for doing such and it would make the code more convoluted and harder to understand.

    There's actually a couple of different ways to solve this. I'm attempting to point out the one that I think will make the most sense and will line up to how Chas was approaching the problem.
    [ December 10, 2008: Message edited by: Mark Vedder ]
    ramya narayanan
    Ranch Hand

    Joined: Oct 06, 2008
    Posts: 338
    Mark, when I use the delimiter property of the Scanner class , it avoids the exception & I've tried it out with even, odd , one or no tokens.
    No exception is thrown & it's working fine.


    Input.txt:


    output:


    Now how to do sorting.
    No replies yet on what is pre-order or post-order?
    Regards.
    Joanne Neal
    Rancher

    Joined: Aug 05, 2005
    Posts: 3576
        
      15
    Originally posted by ramya narayanan:
    No replies yet on what is pre-order or post-order?
    Regards.


    See Mark's last post


    Joanne
    Mark Vedder
    Ranch Hand

    Joined: Dec 17, 2003
    Posts: 624

    Originally posted by ramya narayanan:
    Mark, when I use the delimiter property of the Scanner class , it avoids the exception & I've tried it out with even, odd , one or no tokens.
    No exception is thrown & it's working fine.


    Input.txt:


    output:




    Well, it's not actually the



    line that is preventing the exception. You also changed the the condition in the while loop from a hasNextLine to hasNext.

    When working with tokens, and outputting there value, it's usually a good idea to use some type of delimitation character to see what the output is for a token. It helps to visually see what is an actual token. For example surround the value with single quotes. (I should have done that in the first place but didn't - oops.)



    Change that line and run the program. Notice when you do that you are not getting one name per token. You are getting a full line as a token. Why do you think that is? Now remove or comment out the line that is setting the delimiter:



    and run the code. Notice the difference when that line is removed? Why did that happen? Read through the Scanner documentation (including the documentation for the useDelimiter method) and see if you can figure out why that is.
    [ December 10, 2008: Message edited by: Mark Vedder ]
    ramya narayanan
    Ranch Hand

    Joined: Oct 06, 2008
    Posts: 338
    Since it's well past 22:00 hrs in India, I will certaily see to it tomorrow mark.
    But it has been a very great educating experience for me, Mark
    Thanks once again for your expertise & simplicity.
    Regards.
    Chas Martin
    Greenhorn

    Joined: Oct 07, 2008
    Posts: 18
    Hey guys, thanks for the help. Here is my final and working project:
    First is my main.java class:


    Here is my secondary class called BinaryNodes.java:


    Thanks for the help, I couldnt have done it without you guys!!
    --Chas
    ramya narayanan
    Ranch Hand

    Joined: Oct 06, 2008
    Posts: 338
    Chas in your program how do you conclude pre-order & post-order sorting?
    Could you throw some light on this?
    Regards.
    ramya narayanan
    Ranch Hand

    Joined: Oct 06, 2008
    Posts: 338
    This reply is for mark's post yesterday.
    Change that line and run the program. Notice when you do that you are not getting one name per token. You are getting a full line as a token.
    Why do you think that is?

    It is because I've instructed the JVM to partisan tokens from the text file based on the newline character i.e one token from each line


    which results in the following output:


    In this case hasNext() method means whether nexttokens(string of characters in each line) is there or not.

    Now remove or comment out the line that is setting the delimiter:




    output:


    Notice the difference when that line is removed? Why did that happen?

    Because now we're delimiting text content(input.txt) only by whitespaces while earlier we were delimiting text content one line at a time.


    We want to setup our code so we read the same thing (either a line or a token) and check if any more of that thing (a line or a token) exists.

    This is now achieved by using scanner's hasNext() method & wrapping up the retrieved tokens with some delimiters(like ') for better visibility.
    Am I right

    This is the part of the code you're making us to understand right now!

    which results in the following output:

    Also this has two benefits:
    1) No NoSuchElementException is thrown.
    2) No whitespaces at the end of retrieval which happens with using delimiters

    Is this correct ?
    Then if you can throw light on sorting I will appreciate it?
    Regards
    ramya narayanan
    Ranch Hand

    Joined: Oct 06, 2008
    Posts: 338
    Chas if you could include one blank line in your names.txt file after the last token like this:


    Run it:

    Regards.
    ramya narayanan
    Ranch Hand

    Joined: Oct 06, 2008
    Posts: 338
    If you could just replace


    with


    it's working fine.
    Regards.
    Bert Bates
    author
    Sheriff

    Joined: Oct 14, 2002
    Posts: 8815
        
        5
    off to the intermediate forum


    Spot false dilemmas now, ask me how!
    (If you're not on the edge, you're taking up too much room.)
    ramya narayanan
    Ranch Hand

    Joined: Oct 06, 2008
    Posts: 338
    Any replies?
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38902
        
      23
    Originally posted by ramya narayanan:
    Any replies?


    It's been replied to.
    ramya narayanan
    Ranch Hand

    Joined: Oct 06, 2008
    Posts: 338

    Just for simple sorting i.e sorting on ascending order , if we put the elements in an array list & use collections.sort(arraylist,<comparator> whether we can get the elements arranged in ascending order?
    Even no need of using the comparator in collection.sort as the Strings are by default Comparable & naturally arranged in ascending order.
    Is it possible?
    Mark Vedder
    Ranch Hand

    Joined: Dec 17, 2003
    Posts: 624

    Originally posted by ramya narayanan:

    Just for simple sorting i.e sorting on ascending order , if we put the elements in an array list & use collections.sort(arraylist,<comparator> ;) whether we can get the elements arranged in ascending order?
    Even no need of using the comparator in collection.sort as the Strings are by default Comparable & naturally arranged in ascending order.
    Is it possible?


    If the goal is simply to sort a list in ascending order, then yes using the Collections.sort method would work fine. The goal of this exercise was not simply to sort the list of names. Rather it was to learn about Binary Trees and their usefulness in searches. So that is why the code was written in the manner that it was and the Collections.sort method was not used.
    ramya narayanan
    Ranch Hand

    Joined: Oct 06, 2008
    Posts: 338
    Thanks mark for the clarity.
    Regards.
     
    Consider Paul's rocket mass heater.
     
    subject: Hey guys, A little help with binary trees