How can I traverse a binary tree using a recursive generator?
I am trying to traverse a binary tree which is created in the following code. to be precise, a binary tree is a class and must include an iterator that calls another function, namely inorder (). this method should be a recursive generator and give the value of the nodes in each iteration. I tried to create a dictionary to track nodes, but when I try to call the inorder () method it doesn't work. Is there a missing point that I don't know? I used while and it creates a dictionary of the left side of the tree (this is a clumsy way). please help me to execute 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 followed the code, but I'm pretty sure this is not the best way to traverse a binary tree. I defined the -traverse () - method in my class and now returned a list of nodes in order (which was not ordered at first, so I used the sort () method.) Then I made a loop over that list in my generator, inorder (), so that get its item. All your comments are very much appreciated for code optimization. please recommend the correct solution based on the specific Tree class in this code.
source to share
I may be missing something, but I'm not sure why the dictionary matters in inorder()
. Think what the workaround looks like in order:
def inorder(t):
# Process left sub tree
# Process t
# Process right sub tree
and so in terms of generators it would look like this:
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
source to share
I am completely confused by your thinking. First, there are actually no dictionaries in this code, and I don't understand why you entered d
global.
All you have to do to traverse the binary tree in order is to move to the left, the current label, and to the right:
def inorder(tree):
for label in tree.left:
yield label
yield tree.label
for label in tree.right:
yield label
What is 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()
source to share