Hans Georg Schaathun <h...@schaathun.net> writes:
> ["Followup-To:" header set to comp.lang.python.]
> On 18 May 2011 09:16:26 -0700, Thomas A. Russ
> <t...@sevak.isi.edu> wrote:
> : Well, unless you have a tree with backpointers, you have to keep the
> : entire parent chain of nodes visited. Otherwise, you won't be able to
> : find the parent node when you need to backtrack. A standard tree
> : representation has only directional links.
>
> The array representation of a binary tree is standard, and the
> «back» (parent) pointers are mathematically given. /Some/
> standard tree representation do not have parent pointers.
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.
> You are right that I assumed parent pointers of some description;
> but it does demonstrate that tree walks can be done iteratively,
> without keeping a stack of any sort.
Except that the chain of parent pointers *would* constitue a
stack.
--
http://mail.python.org/mailman/listinfo/python-list
