Python to go to flat list

Question

I created a method of the TreeNode class that I need to return a flat list of traversal of the order tree

My sample tree:

The output on the workaround should be: [1, 1, 0, 2, 1, 3, 1, 1, 0]

but I get: [2, 1, 1, 0, 1, 3, 1, 1, 0]

Here is my code:

 def in_order_list(self, r = []): hasLeft = self.left is not None hasRight = self.right is not None if self is None: return else: if hasLeft: self.left.in_order_list(r) r.append(self.value) if hasRight: self.right.in_order_list(r) return r 

Can anyone let me know why this is happening?

Thanks Alex

Answer 1

Instead of calling self.left/right. in _order_list() you call self.left/right. pre _order_list() .

To accomplish what you want to do, the generator function may be better (less memory and more pythonic) than accumulating values ​​in a list:

 class Tree(object): ... def in_order(self): if self.left is not None: for value in self.left.in_order(): yield value yield self.value # <-- yielding the value of the node, not the node itself if self.right is not None: for value in self.right.in_order(): yield value ... tree = Tree(...) in_order_values = list(tree.in_order()) 

This way you do not need to create a list if you only want to iterate over the values:

 for value in tree.in_order(): ... 

The algorithm works as follows: the generator first descends recursively along the left branch of each node until it reaches one without the left sub-node. Then it gives the current value of node. After that, he does the same on the right under the node, but starts with the current node, and not with the root of the node. If we assume that there are no cycles in the tree and there are no infinite branches, then there will definitely be leaf nodes, i.e. Nodes without left or right sub-node. IOW, for which both basic options have been achieved ( self.left/right is None ). Therefore, recursive calls return, I hope, before we go out of memory or reach the stack limit.

The loop over self.left/right.in_order() necessary due to the fact that the returned call in_order() is a generator, therefore the name generator function. The returned generator must be somehow exhausted, for example. through the loop. In the body of the loop, we return the values ​​one level, where they return again until they reach the top level. There we use the values.

If you want to get the nodes yourself, and not just your value fields, you can do this as follows:

 class Tree(object): ... def in_order(self): if self.left is not None: for node in self.left.in_order(): yield node yield self # <-- yielding the node itself if self.right is not None: for node in self.right.in_order(): yield node 

You probably want to do this because you can not only access the values ​​of the nodes:

 for node in tree.in_order(): do_something_with(node.value) 

but also you can do whatever you want with nodes:

 for node in tree.in_order(): whatever(node.some_other_attribute) 

Answer 2

This may be a problem with the default argument for r = []

Example:

 def foo(list=[]): list.append(1) print list foo() >>> [1] foo() >>> [1,1] 

Python keeps the same list across multiple function calls.

Try to do something like a function:

 def in_order_list(self, r=None): if r is None: r = [] 

You might want to post the rest of your code so that we can know what this pre_order function does.

Answer 3

You can write this thing really neatly as a generator and not have to process lists and add:

  def in_order(tree): if tree is None: return for value in in_order(tree.left): yield value yield tree.value for value in in_order(tree.right): yield value 

For instance:

 >>> class Node(object): ... def __init__(self, value, left=None, right=None): ... self.value, self.left, self.right = value, left, right ... >>> x = Node(3) >>> x.left = Node(2) >>> x.left.left = Node(1) >>> x.left.left.left = Node(1) >>> x.left.left.right = Node(0) >>> x.left.right = Node(1) >>> x.right = Node(1) >>> x.right.left = Node(1) >>> x.right.right = Node(0) >>> >>> in_order(x) <generator object in_order at 0xb742dbbc> >>> list(in_order(x)) [1, 1, 0, 2, 1, 3, 1, 1, 0] 

Answer 4

A), firstly, as campos.ddc noted, when assigning [] value of the parameter r is problematic. For more information see fooobar.com/questions/697 / ... (this is a big mistake very )

B) it would seem that your test is "if" no: "redundant", if "I" was "No", you will not be able to call the in_order_list method (if it is a method in the class, and not a separate function)

C) The code can be simplified:

 def in_order_list(self, r = None): if not r: r = [] if self.left: self.left.in_order_list(r) r.append(self.value) if self.right: self.right.in_order_list(r) 

D) Questions that are likely to be “homework” should be marked as such. >: (