["Followup-To:" header set to comp.lang.python.] On 17 May 2011 23:42:20 -0700, Thomas A. Russ <t...@sevak.isi.edu> wrote: : Tree walks are the canonical example of what can't be done in an : iterative fashion without the addition of an explicitly managed stack
Of course you can do it. It isn't nice, but it is possible. I assume that you refer to depth first walks, as breadth first is more easily described by iteration on a queue in the first place. Depth first can be achieved by looping over the nodes, with a state keeping references to the current and the previous node considered. 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. -- :-- Hans Georg -- http://mail.python.org/mailman/listinfo/python-list
