打印树，而无需递归

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