yost@tss.com (Dave Yost) (04/02/91)
Is there a standard name for a tree traversal that
* visits the node
* traverses the children, if any
* visits again
Sort of a combination of preorder and postorder.
I just wrote a generic tree traverser that lets
the user specify the traversal "phases" of interest:
before,
after, or
both before and after
The application was one that printed out a nested
C struct declaration, so it needed to pause once
to print out the
struct {
then traverse the children, and then pause again
to print the
};
I've looked in several of the standard references
and can't find a name for this.
--dave yosteppstein@wormwood.ics.uci.edu (David Eppstein) (04/03/91)
In article <1991Apr2.014125.21190@tss.com> yost@netcom.COM writes: >Is there a standard name for a tree traversal that > * visits the node > * traverses the children, if any > * visits again >Sort of a combination of preorder and postorder. Especially in the context of parallel algorithms, this has typically been called an "Euler tour". If you turn each edge in the tree into two edges, one directed each way, then the traversal really is an Euler tour in the graph sense. See R.E. Tarjan and U. Vishkin, "Finding biconnected components and computing tree functions in logarithmic parallel time", 7th IEEE Symp. Foundations of Computer Science (FOCS), 1984, pp. 12-20. -d -- David Eppstein UC Irvine, Info & Computer Science eppstein@ics.uci.edu
eppstein@wormwood.ics.uci.edu (David Eppstein) (04/03/91)
In article <1991Apr2.014125.21190@tss.com> yost@netcom.COM wrote:
< Is there a standard name for a tree traversal that
< * visits the node
< * traverses the children, if any
< * visits again
< Sort of a combination of preorder and postorder.
I replied:
< Especially in the context of parallel algorithms, this has typically
< been called an "Euler tour".
I should clarify a little. The Euler tour visits each _edge_, then the
edges to the children, then the edge again. In terms of nodes this
visits each node before, between, and after the children. But this is
really not so different from what yost is talking about.
--
David Eppstein UC Irvine, Info & Computer Science eppstein@ics.uci.eduyost@calvin.Berkeley.EDU (Dave Yost) (04/09/91)
In articles <27F8BF3D.17384@ics.uci.edu> and <27F8C635.20370@ics.uci.edu>, eppstein@wormwood.ics.uci.edu (David Eppstein) writes: |> In article <1991Apr2.014125.21190@tss.com> yost@netcom.COM wrote: |> < Is there a standard name for a tree traversal that |> < * visits the node |> < * traverses the children, if any |> < * visits again |> < Sort of a combination of preorder and postorder. |> |> Especially in the context of parallel algorithms, this has typically |> been called an "Euler tour". If you turn each edge in the tree into two |> edges, one directed each way, then the traversal really is an Euler tour |> in the graph sense. |> |> The Euler tour visits each _edge_, then the edges to the children, |> then the edge again. In terms of nodes this visits each node before, |> between, and after the children. But this is really not so different |> from what yost is talking about. |> -- |> David Eppstein UC Irvine, Info & Computer Science eppstein@ics.uci.edu Yes, thanks. Someone else pointed out the Euler connection to me by email. My traversal technique is indeed an Euler tour, but it's different from the one you describe. Consider the tree as a graph with edges from the parent to the first and last children (if only one child, then there are two edges to it), and edges between children at the same level. Example: A / \ B-C-D () / \ E F---G The Euler tour is: A1 B1 E B2 C D1 F G D2 A2 If desired, the client of my traverser can achieve the effect of the tour you suggest by following a pointer to the parent, which is available as part of my implementation. Each visit in my implementation corresponds to a call to the traverser. --dave yost