Skip to Content.
Sympa Menu

xom-interest - Re: [XOM-interest] Recursion

xom-interest AT lists.ibiblio.org

Subject: XOM API for Processing XML with Java

List archive

Chronological Thread  
  • From: jcowan AT reutershealth.com
  • To: Elliotte Rusty Harold <elharo AT metalab.unc.edu>
  • Cc: xom-interest AT lists.ibiblio.org
  • Subject: Re: [XOM-interest] Recursion
  • Date: Mon, 8 Mar 2004 16:06:02 -0500

Elliotte Rusty Harold scripsit:

> That algorithm was:
> 1) firstChild, unless null, in which case
> 2) nextSibling, unless null, in which case
> 3) parent() and try again, unless root, in which case
> 4) stop.

Sorry, that wasn't too clear. Let me try that again:

0) Move to the root node.
1) Process the current node.
2) If the current node has a child:
move to the first child, go to step 1.
3) If the current node has a rightward sibling:
move to the rightward sibling, go to step 1.
4) If the current node has a parent:
move to the parent, go to step 2.
5) Done.

This does preorder processing (parents before children). Provided there
are O(1) ways to find the first child, right sibling, and parent, this
is slightly more time-efficient than recursion, and its stack consumption
is O(1).

For processing other than from the root node, you eliminate step 0 and
change step 4 to "If the current node is not the initial node".

--
John Cowan jcowan AT reutershealth.com www.reutershealth.com
www.ccil.org/~cowan
If a soldier is asked why he kills people who have done him no harm, or a
terrorist why he kills innocent people with his bombs, they can always
reply that war has been declared, and there are no innocent people in an
enemy country in wartime. The answer is psychotic, but it is the answer
that humanity has given to every act of aggression in history. --Northrop
Frye




Archive powered by MHonArc 2.6.24.

Top of Page