# Re: unbalanced tree iteration issue

• From: kost BebiX <k.bx@xxxxx>
• Date: Fri, 14 Jan 2011 15:29:34 +0200

14.01.2011, 14:15, "Alex Boyko" <alex.kyrish@xxxxxxxxx>:
Dear All!

I have deal with large unbalanced trees and I have to implement post-order tree traversal. My first attempt is shown below ("Node" and "Tree" classes) and based on recursive generators approach.

class Node():
def __init__(self,value):
self.childs = []
self.value = value

class Tree():

def __init__(self, root):
self.root = root
self.numberCells = 1

node.childs.append(child)
self.numberCells+=1

def __iter__(self):
return self.postorder(self.root)

def postorder(self, node):
if node:
for child in node.childs:
for n in self.postorder(child):
yield n
yield node

It works fine for small test trees. But, my tree has approximately 300000 nodes, and shown post order traversal with generators takes 80 sec against 1 sec with simple recursive routine:

def recursiveFromTop(node):
for child in node.childs:
recursiveFromTop(child)
## here I can do some computations with current node's data

So, I'd like to know how should I implement (if it's possible of course) __iter__ for my tree class based on recursion without generators? Please, can You show me the ways?
because I'm very passionate in idea iterate through my tree with simple:

for node in tree:
do something with node

Best Regards!
Alex

--
http://mail.python.org/mailman/listinfo/python-list

Forgot to make new-style object)
class Node(object):

The results for new-style objects are:
\$ python postorder.py
building tree...done
0:00:26.180799
doing generator post_order...done
0:00:00.000017
doing non-generator post_order...done
0:00:01.117986

--
jabber: k.bx@xxxxx
.