aspose file tools*
The moose likes Java in General and the fly likes Tree Structure + Depth First Traversal? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Tree Structure + Depth First Traversal?" Watch "Tree Structure + Depth First Traversal?" New topic
Author

Tree Structure + Depth First Traversal?

Garrett Smith
Ranch Hand

Joined: Jun 27, 2002
Posts: 401
Posted up on Servlets forum but my question could not be answered. Maybe it was too vague.

Anyway,
How can I create a Tree that can be depth-first traversed?


It's gonna be for an HTML page. Method next() does Depth First Traversal.

each item will need some slighly complex, varied HTML representation, e.g. href, title, link text, className, optionalImageIcon, et c.

I need to know current, hasNext(), and also..

How do I build up this tree?


comp.lang.javascript FAQ: http://jibbering.com/faq/
Pat Farrell
Rancher

Joined: Aug 11, 2007
Posts: 4659
    
    5

What are you looking for? Trees are basic structures, and how next() work are implementation details. Are you looking for all the code to cut and paste? a prebuilt library? some Interface definitions to get you started?
Garrett Smith
Ranch Hand

Joined: Jun 27, 2002
Posts: 401
Ideally, you would write and test the code for me, I would copy-paste it, and it would work perfectly.

I'll take what I can get, though.

I need to know how to:
pick a tree structure that fulfills the need
define elements
add elements to the tree
do depth first traversal on the tree, while knowing the level.

The last step is crucial. I need to display nested lists on the navbar.


I would consider prebuilt lib code, but it probably won't do what I want it to. Most Java -> UI code doesn't.

So I think I should just roll up my sleeves and ask for advice
[ October 10, 2007: Message edited by: Garrett Smith ]
Garrett Smith
Ranch Hand

Joined: Jun 27, 2002
Posts: 401
I want to figure out how to do this.

It's super easy in HTML -- just declare the tree as a list of lists.

In JavaScript, I'd probably write a Tree class that does what I want.

In Java, I need to create a depth-first traversable Tree that can print out a hierarchical structure (as html in my case).

How do I do this?
[ October 11, 2007: Message edited by: Garrett Smith ]
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
A Java tree usually has a Node object something like:

You walk a tree, and in this case generate HTML, by doing something like:

Are you comfortable with that kind of recursion?

Look at the HTML you want to produce from this. I think every node puts out a LI tag. If the node has any children, it also puts out a UL tag around the children.

Along the way you need to detect when node is current page and make it text, not a link. Also note the next link generated and duplicate it in the NEXT link.

Many folks have a strong objection to generating HTML in Java. Once you get this going, we can ask them for alternatives.
[ October 11, 2007: Message edited by: Stan James ]

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
Garrett Smith
Ranch Hand

Joined: Jun 27, 2002
Posts: 401
Originally posted by Stan James:
A Java tree usually has a Node object something like:

You walk a tree, and in this case generate HTML, by doing something like:

Are you comfortable with that kind of recursion?

I have used this algorithm a few times.

every node puts out a LI tag. If the node has any children, it also puts out a UL tag around the children.

Yes.

Along the way you need to detect when node is current page and make it text, not a link.

Yes.

Also note the next link generated and duplicate it in the NEXT link.

I'll probably need something like:


Many folks have a strong objection to generating HTML in Java. Once you get this going, we can ask them for alternatives.

Putting the HTML in the Java code is messy.

I was thinking that it should be really easy to parse the OL as a fragment using an XML parser, and then walk the list tree. Apparently, that is a bad idea.

So back to putting the algorithm into Java code...



There must be a more standard way to do it.

I can check the current page by checking the requestURI.
[ October 11, 2007: Message edited by: Garrett Smith ]
Garrett Smith
Ranch Hand

Joined: Jun 27, 2002
Posts: 401
Now I am copy-pasting HTML into objects, escaping quote marks.
This is madness.

Parsing the list and the iterating the collection on the server would be less error-prone and would keep my HTML out of the objects.

This HTML parser looks like it might be able to do that. I haven't worked with streams in years, though.

http://htmlparser.sourceforge.net/javadoc/org/htmlparser/Parser.html
Pat Farrell
Rancher

Joined: Aug 11, 2007
Posts: 4659
    
    5

Originally posted by Garrett Smith:
Ideally, you would write and test the code for me, I would copy-paste it, and it would work perfectly.


Hey, I'm a professional programmer, I expect to get paid for it to work perfectly.

Looks like you are getting help and making progress.
Java is actually fairly easy to do the node/tree stuff
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
And now for something completely different ...

I recently made a tree with nested ULs that does dynamic open and close. I'd be tempted to reuse that and do all this in JavaScript. Of course users with script turned off would be out of luck.

Here's a little bit of how this works:

options is an array of objects with name and key fields. It comes from the server in JSON syntax like this:

You can generate JSON from your tree of Nodes with a one line call to the StringTree JSON library.
Garrett Smith
Ranch Hand

Joined: Jun 27, 2002
Posts: 401
Originally posted by Pat Farrell:


Hey, I'm a professional programmer, I expect to get paid for it to work perfectly.

Sorry, bad joke.
Originally posted by Pat Farrell:

Looks like you are getting help and making progress.
Java is actually fairly easy to do the node/tree stuff


It isn't that hard to hard-code, but will be hard to maintain. I'm not putting markup in my HTML. I've been down that road.

Same thing with the JSON approach. Hard to maintain and requires inefficient client-side HTML transforms.

I'm considering the htmlparser. Parser.parse gives a NodeList.
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
The Quiotix HTML parser builds a DOM from HTML and provides a nifty Visitor interface to walk the DOM. You can modify nodes and use another Visitor to regenerate HTML that is more correct and beautiful than the original in many cases. I found Visitor much more fun than navigating the DOM myself. I've done this kind of thing in a pre-publish step that generated static HTML, but would find it very strange in dynamic server side processing.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Tree Structure + Depth First Traversal?