t...@sevak.isi.edu (Thomas A. Russ) writes:
> 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.
>
> Consider:
>
> A--+---B----+---D
> | |
> | +---E
> | |
> | +---F
> |
> +---C
>
> If all you keep is the current and previous node, then the only thing
> you have reference do when doing the depth-first traverse is:
> 1. Current = A, Previous = null
> 2. Current = B. Previous = A
> 3. Current = D Previous = B
> 4. Current = E Previous = D
> 5. now what? You can't get from E or D back to B.
>
>> By comparing the previous node (pointer or ID) to the
>> current node's parent and children one will know wherefrom the
>> current node was entered, and can choose the next child in the
>> list as the next node, or the parent if all children have been
>> visited. A visit action may be added in any or all times the
>> node is visited.
>>
>> This node requires no stack. The only state space is constant,
>> regardless of the size of the tree, requiring just the two pointers
>> to previous and current.
>
> This will only work if there is a backpointer to the parent.
No, you don't need backpointers; some cases have been mentionned in the
other answer, but in general:
(defun parent (tree node)
(if (member node (children tree))
tree
(some (lambda (child) (parent child node)) (children tree))))
Yes, the question wasn't about time complexity.
--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.
--
http://mail.python.org/mailman/listinfo/python-list
