Hans Georg Schaathun <h...@schaathun.net> writes:
> ["Followup-To:" header set to comp.lang.python.]
> On Wed, 18 May 2011 21:09:15 +0200, Raymond Wiker
> <raw@RAWMBP-2.local> wrote:
> : > In the sense that the tree itself is a stack, yes. But if we
> : > consider the tree (or one of its branches) to be a stack, then
> : > the original claim becomes a tautology.
> :
> : No, the tree is not a stack, but the chain of parent pointers
> : from a particular node may be considered as a stack that records the
> : path taken to reach the current node.
>
> That is one of its branches, yes, path from root towards leaf.
> It is part of the data structure, and you don't travers a data
> structure without using the datastructure.
>
> : > But you do have a point. Keeping a stack of nodes on the path
> : > back to root is a great deal simpler and cheaper than a call
> : > stack, and not really a significant expense in context.
> :
> : For this particular operation, possibly. For other tree
> : operations, a single parent pointer may not be sufficient.
>
> Que? What tree operations do you have in mind? We have covered
> all the standard textbook tree walks by now.
I said tree operations, not tree walks. A tree operation might
involve several tree walks. Further, there has been an implicit
assumption (I think) in this discussion that the order of children is
given, or does not matter - if this is not the case, then you also need
to maintain a stack of data structures representing lists (or sets) of
children.
--
http://mail.python.org/mailman/listinfo/python-list
