How to traverse a binary Tree with a recursive generator?
Solution 1
Perhaps I'm missing something, but I'm not sure why the dictionary is relevant in inorder()
. Think about what an in-order traversal looks like in general:
def inorder(t):
# Process left sub tree
# Process t
# Process right sub tree
and so in terms of generators, this would look like:
def inorder(t):
if t.left:
for elem in inorder(t.left):
yield elem
yield t
if t.right:
for elem in inorder(t.right):
yield elem
Solution 2
I am thoroughly confused by your thinking. For one thing, there's not actually any dictionaries in this code, and I don't understand why you introduced the d
global.
All you need to do for in-order traversal of a binary tree is to traverse the left, the current label, and the right:
def inorder(tree):
for label in tree.left:
yield label
yield tree.label
for label in tree.right:
yield label
That's it.
However I would make some improvements to your code:
# Document classes and functions with docstrings instead of comments
class Tree(object):
"""A binary tree class"""
def __init__(self, label, left=None, right=None):
"""Label is the node value, left and right are Tree objects or None"""
self.label = label
self.left = left # Tree() or None
self.right = right # Tree() or None
def __repr__(self):
return 'Tree(%r, %r, %r)' % (self.label, self.left, self.right)
def __iter__(self):
# No need for a separate inorder() function
if self.left is not None:
for t in self.left:
yield t
yield self.label
if self.right is not None:
for t in self.right:
yield t
def tree(indexable):
"""Return a tree of anything sliceable"""
ilen = len(indexable)
if not ilen:
# You should be clearer about empty values
# left and right should be Tree (something with left, right, and __iter__)
# or None if there is no edge.
return None
center = ilen // 2 # floor division
return Tree(indexable[center], tree(indexable[:center]), tree(indexable[center+1:]))
def test():
seq = range(10)
t = tree(seq)
# list(t) will consume an iterable
# no need for "result = []; for x in t: result.append(x)"
assert seq == list(t)
if __name__ == '__main__':
test()
msc87
Updated on June 04, 2022Comments
-
msc87 almost 2 years
I am trying to traverse a Binary Tree which is created in the following code. to be precise, the Binary Tree is a class and should include an iterator calling another function namely inorder(). this method should be a recursive generator and yield the value of nodes in every iteration.I tried to create a dictionary to follow the nodes but when I try to call the inorder() method, it doesn't work. Is there any missing point that I don't know? I used while and it creates the dictionary of left side of tree (it is a clumsy way). please help me accomplish this code.
d=[] # A binary tree class. class Tree(object): def __init__(self, label, left=None, right=None): self.label = label self.left = left self.right = right self.d=dict() def __repr__(self, level=0, indent=" "): s = level * indent + self.label if self.left: s = s + "\n" + self.left.__repr__(level + 1, indent) if self.right: s = s + "\n" + self.right.__repr__(level + 1, indent) return s def traverse(self): if self.left: lastLabel=self.label self.left.traverse() if self.right: lastLabel=self.label d.append(lastLabel) self.right.traverse() else: d.append(self.label) return d def __iter__(self): return inorder(self) # Create a Tree from a list. def tree(sequence): n = len(sequence) if n == 0: return [] i = n / 2 return Tree(sequence[i], tree(sequence[:i]), tree(sequence[i+1:])) # A recursive generator that generates Tree labels in in-order. def inorder(t): for i in range(len(d)): yield d[i] def test(sequence): # Create a tree. t = tree(sequence) # Print the nodes of the tree in in-order. result = [] for x in t: result.append(x) print x print result_str = ''.join(result) # Check result assert result_str == sequence del d[:] def main(): # Third test test("0123456789") print 'Success! All tests passed!' if __name__ == '__main__': main()
I changed my code again I accomplished the code but I'm sure it is not the best way to traverse a Binary tree. I defined a method -traverse()- in my class and returned a list of nodes in order now (which at first wasn't ordered, so I used sort() method.) then I made a loop over this list in my generator, inorder() function, to yield the element of it. All your comments are very welcome to optimize the code. please recommend a proper solution based on the specific Tree class in this code.