I am trying to write all entries of a search tree into a list. In unchanged order, nodes before children. But I mix the order up somewhere along the way.
def n(value, children=[]):
return [value,children]
#I want to keep this order in the list
tree = (n(5,[n(2,[n(3)]),n(6),n(8,[n(7),n(9)])]))
def is_empty(tree) :
return tree == []
def to_list_iter(tree) :
stack = []
stack.append(tree)
l = []
while stack != [] :
tree = stack.pop()
if not is_empty(tree) :
l.append(tree[0])
n = len(tree[1])
while n > 0:
stack.append(tree[1][len(tree[1])-n])
n -= 1
return l
print (to_list_iter(tree))
# This will print the following output:
# [5, 8, 9, 7, 6, 2, 3]
# Instead of the desired [5, 2, 3, 6, 8, 7, 9]
The solution is quite close to your code, though simplified:
def n(value, children=[]):
return [value,children]
tree = (n(5,[n(2,[n(3)]),n(6),n(8,[n(7),n(9)])]))
def to_list_iter(tree) :
stack = [tree]
l = []
while stack :
tree = stack.pop()
if tree:
l.append(tree[0])
stack.extend(reversed(tree[1]))
return l
print (to_list_iter(tree))
The main difference is that you need to extend the stack with a reversed list of children, because the stack is always popped from at the back of the list.