Hans Georg Schaathun <h...@schaathun.net> writes:
> ["Followup-To:" header set to comp.lang.python.]
> 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 cannot see that going back to the original case (directory
traversal) is any more specific than talking about a completely
unrelated case (binary trees).
Further, even though most(?) hierarchical file systems have parent
pointers, this is not necessary.
> : Except that the chain of parent pointers *would* constitue a
> : stack.
>
> 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.
> 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.
--
http://mail.python.org/mailman/listinfo/python-list
