打印樹，而無需遞歸

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