Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / First Aid / February 2005

Tip: Looking for answers? Try searching our database.

Recursive Flatten BST

Thread view: 
Chris Hatton - 13 Feb 2005 13:40 GMT
I have a bst which contain words(Strings), what I'm trying to is do an
inorder traversal so as I can print the words in alphabetical order. The
system.out.println() prints them ok, but what I really want it to do is
return a LinkedQueue from my bst, but it only seems to add the very root
of the tree.

Any ideas where I'm going wrong here?

public LinkedQueue flatten(BstNode x){ // x = root node
        LinkedQueue words = new LinkedQueue();   
        if(x != null){
            flatten(x.getLeft());    // traverse the left subtree
            words.qAdd(x.getData());
            System.out.println(x.getData());
            flatten(x.getRight());    // traverse the right subtree
        }   
        return words;       
}

Thanks,
Chris
Stefan Schulz - 13 Feb 2005 13:39 GMT
> I have a bst which contain words(Strings), what I'm trying to is do an
> inorder traversal so as I can print the words in alphabetical order. The
[quoted text clipped - 14 lines]
>          return words;       
> }

You create a new LinkedQueue in each and every node, and in the end only
return the Queue created for the root node.

What you probably wanted is this:

public LinkedQueue flatten(BstNode x){ // x = root node
        LinkedQueue words = new LinkedQueue();   
    flatten(x, words);
    return words
}

private void flatten(BstNode x, LinkedQueue words){
        if(x != null){
        // traverse the left subtree
            flatten(x.getLeft(), words);   
            words.qAdd(x.getData());
            System.out.println(x.getData());
        // traverse the right subtree
            flatten(x.getRight());
        }   
}

Signature

In pioneer days they used oxen for heavy pulling, and when one ox
couldn't budge a log, they didn't try to grow a larger ox. We shouldn't
be trying for bigger computers, but for more systems of computers.
          --- Rear Admiral Grace Murray Hopper

Chris Hatton - 13 Feb 2005 13:59 GMT
>>I have a bst which contain words(Strings), what I'm trying to is do an
>>inorder traversal so as I can print the words in alphabetical order. The
[quoted text clipped - 36 lines]
>          }   
> }

I can't belive I did that!  <d:-)

Well, you live and learn.

Cheers,

Chris


Free Magazines

Get these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.