迭代树走

Question

它已经相当一段时间，因为我把数据结构和算法在大学，所以我很惊讶最近一项建议是递归可能不是方式（TM）做树的遍历。出于某种原因迭代，基于队列的遍历不是我曾经使用过的技术。

什么，如果有的话，是迭代与递归遍历的优点？在什么情况下我可以使用一种而不使用另一种？

Answer 1

如果您在进行宽度优先搜索，自然实现是将节点推入队列，而不是使用递归。

如果您正在进行深度优先搜索，则递归是编码遍历的最自然的方式。但是，除非您的编译器将迭代的尾部递归优化，否则您的递归实现将比迭代算法慢，并且会在足够深的树上发生堆栈溢出而死亡。

一些快速的Python来说明的区别：

#A tree is a tuple of an int and a tree. 
t = (1, (2,(4, (6), (7, (9)))), (3, (5, (8)))) 
def bfs(t): 
    to_visit = [t] 
    while len(to_visit) > 0: 
     c = to_visit[0] 
     if type(c) is int: 
      print c 
     else: 
      print c[0] 
      to_visit.append(c[1]) 
      if len(c) > 2: to_visit.append(c[2]) 
     to_visit = to_visit[1:] 

def dfs(t): 
    if type(t) is int: 
     print t 
     return 
    print t[0] 
    dfs(t[1]) 
    if len(t) > 2: dfs(t[2]) 

bfs(t) 
dfs(t) 

Answer 2

这取决于你是否想要做的是深度优先还是广度优先遍历。深度优先是通过递归最容易实现的。通过宽度优先，您需要保留一个节点队列以便将来扩展。

Answer 3

如果您拥有固定数量的专用于堆栈的内存（与许多Java JVM配置中的问题相同），但如果您的树较深（或者递归深度不足，递归可能无法正常工作在任何其他情况下都很高）;它会导致堆栈溢出。迭代方法，推动节点访问队列（用于类似BFS的遍历）或堆栈（用于类似DFS的遍历）具有更好的内存属性，因此如果这很重要，请使用迭代方法。

递归的优点是简单/高雅的表达，而不是表现。记住这是为给定算法，问题大小和机器体系结构选择适当方法的关键。

Answer 4

实际上，你应该使用队列中的广度优先搜索和堆栈进行深度优先搜索， 并从while循环运行你的算法。 如果在遍历期间执行简单的 操作，并且可能导致堆栈溢出，则进行递归函数调用会显着拖动程序，但这些日子您需要尝试真正难以看到其中的一个。

只要有一个哈希值来跟踪已访问的节点，以防它不是一棵树，而是一个连接良好的图。

Answer 5

去递归，因为你实际上可能会得到一个堆栈溢出错误，毕竟这是stackoverflow.com。