Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!crdgw1!uunet!tekbspa!calvin!yost
From: yost@calvin.Berkeley.EDU (Dave Yost)
Newsgroups: comp.theory
Subject: Re: what to call this kind of tree traversal
Message-ID: <1991Apr8.220149.13938@tss.com>
Date: 8 Apr 91 22:01:49 GMT
References: <1991Apr2.014125.21190@tss.com> <27F8BF3D.17384@ics.uci.edu> <27F8C635.20370@ics.uci.edu>
Sender: news@tss.com (USENET Network News)
Reply-To: yost@tss.COM
Organization: Teknekron Software Systems, Inc.
Lines: 46

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