печати дерево без рекурсии

Question

У меня есть этот код, который печатает данные каждого узла в дереве:

class Node: 
    def __init__(self,data, children=[]): 
     self.data = data 
     self.children = children 
    def __repr__(self): 
     return str(self.data) 

n1 = Node(1) 
n2 = Node(2) 
n3 = Node(3) 
n4 = Node(4) 
n5 = Node(5) 
n6 = Node(6) 
n7 = Node(7) 


n1.children=[n2,n3,n4] 
n3.children = [n5,n6] 
n6.children=[n7] 

def print_rec(node): 
    print node 
    if not node.children: return 
    for c in node.children: 
     printer(c) 

, как я могу написать print_rec метод без использования рекурсии?

Answer 1

Вы бы использовать очередь для отслеживания узлов еще обработать, добавив к нему, как вы их обработать:

def print_nonrec_breathfirst(node): 
    queue = [node] 
    while queue: 
     node, queue = queue[0], queue[1:] 
     print node 
     for c in node.children: 
      queue.append(c) 

или вы могли бы использовать стек, обработка детей первых:

def print_nonrec_depthfirst(node): 
    stack = [node] 
    while stack: 
     node = stack.pop() 
     print node 
     for c in node.children: 
      stack.append(c) 

В любом случае, вы отслеживаете, какие узлы вы еще не распечатали, и при обработке узлов вы также также выяснить, какие дочерние узлы вам еще нужно обработать.

Демо:

>>> print_nonrec_breathfirst(n1) 
1 
2 
3 
4 
5 
6 
7 
>>> print_nonrec_depthfirst(n1) 
1 
4 
3 
6 
7 
5 
2