Forum Stats

  • 3,875,872 Users
  • 2,266,977 Discussions
  • 7,912,361 Comments

Discussions

depth first, pre-order traversal ?

843834
843834 Member Posts: 49,972
edited Jul 27, 2001 4:53AM in Java Technology & XML
Im experiementing with various examples of parsing an XML document and adapting it to a TreeModel for use in a JTree component. Im looking at some of the newer JAXP API's like org.w3c.dom.traversal
Interface DocumentTraversal. Im wondering about depth first and pre-order traversal.
What do these terms mean ? Im guessing it has to do with the tree type data structure ? Like many programmers out there, I went to college for something other than comp sci so i never had the unfortunate pleasure of taking a data structures course.

Also it seems like the level 2 DOM spec is making things alot easier to work with, but even Sun doesnt have a good tutorial on using the newer API's.

Comments

  • 843834
    843834 Member Posts: 49,972
    Pre-order traversal simply means, that any method is applied to the parent first, before it is applied to its children. A tree like

    aNode
    /
    -pNode-+-bNode
    \
    cNode

    would therefor result in a series of method calls like:
    pNode.yourMethod();
    aNode.yourMethod();
    bNode.yourMethod();
    cNode.yourMethod();
    Whereas post-order taversal would start with the children and process the parent node as last one. Finally a in-order run would process some children first, which come in some kind of order before the parent node, then the root node and finally the remaining children. Of course, that makes only sense if the tree is ordered in some way, eg. if the node content can be ordered alphabetically or so.

    Hope that helps,
    Mathias
  • 843834
    843834 Member Posts: 49,972
    Sorry, the "line art" didn't come out as expected: The nodes a and c should branch at the + sign and not at the root.
This discussion has been closed.