Hans Georg Schaathun <h...@schaathun.net> writes: > ["Followup-To:" header set to comp.lang.python.] Ignored, since I don't follow that group.
> On Wed, 18 May 2011 20:20:01 +0200, Raymond Wiker > <raw@RAWMBP-2.local> wrote: > : I don't think anybody mentioned *binary* trees. The context was > : directory traversal, in which case you would have nodes with an > : arbitrary (almost) number of children. > > If we are being specific, then directory trees do have parent pointers. > My point was really that «standard tree representations» is not a > well-defined concept, and having parent pointers is as standard as > not having them. I suppose that I just assumed the standard mathematical definition of a tree as a directed, acyclic graph. It seems that in the context of computability that one would tend toward using the mathematical definitions. Certainly in a complex graph with labeled links or trees with backpointers, you would have an alternate data structure that you could follow. So, to be more precise, then: For directed, acyclic graphs without backpointers, you cannot write an iterative tree walker without simulating a stack. The larger point is that there are algorithms that are inherently recursive and for which there is no natural iterative algorithm. -- Thomas A. Russ, USC/Information Sciences Institute
-- http://mail.python.org/mailman/listinfo/python-list
