Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!elroy.jpl.nasa.gov!usc!orion.oac.uci.edu!ucivax!eppstein
From: eppstein@wormwood.ics.uci.edu (David Eppstein)
Newsgroups: comp.theory
Subject: Re: what to call this kind of tree traversal
Message-ID: <27F8C635.20370@ics.uci.edu>
Date: 2 Apr 91 17:58:13 GMT
References: <1991Apr2.014125.21190@tss.com> <27F8BF3D.17384@ics.uci.edu>
Reply-To: eppstein@ics.uci.edu (David Eppstein)
Organization: UC Irvine Department of ICS
Lines: 17
Nntp-Posting-Host: wormwood.ics.uci.edu

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.edu