迭代树遍历

Question

自从我在大学里学习了数据结构和算法以来已经过了很长一段时间，所以最近听到一个建议说递归可能不是树遍历的"正确"方法，我感到很惊讶。出于某种原因，基于迭代、队列的遍历不是我曾经使用过的技术。

相比递归遍历，迭代遍历有哪些优势？在什么情况下我应该使用其中之一而不是另一种方法？

- vezult

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)

- RossFabricant

---

非常有帮助的答案，而且阐述得非常清晰明了。谢谢！ - vezult

Answer 2

如果您的栈内存是固定的，就像在许多Java JVM配置中一样，递归在具有深度树（或在任何其他情况下递归深度很高）时可能无法正常工作，它会导致堆栈溢出。如果这很重要，那么采用迭代方法，将要访问的节点推入队列（用于类似BFS的遍历）或堆栈（用于类似DFS的遍历）具有更好的内存性能。

递归的优点在于表达简单/优雅，而不是性能。记住这一点是选择适当的算法、问题规模和机器架构的关键。

- Matt J

---

+1 是在表达优雅和性能/避免堆栈溢出之间做出权衡的过程中，我刚想提交的内容。 - el2iot2

Answer 3

这取决于您想要进行深度优先遍历还是广度优先遍历。通过递归实现深度优先遍历最容易。对于广度优先遍历，您需要保持一个节点队列以在未来扩展。

- geofftnz

Answer 4

实际上，你应该使用队列来进行广度优先搜索，使用栈来进行深度优先搜索，并从 while 循环中运行算法。 如果在遍历时执行简单操作并进行递归函数调用，可能会显著拖慢程序，并导致堆栈溢出，但现在你需要非常努力才能看到这种情况。

只需在一侧使用哈希表来跟踪已访问的节点，以防它不是树而是一个连接良好的图形。

- Nikola Jevtic

Answer 5

使用递归，因为你实际上可能会遇到堆栈溢出错误，而这毕竟是stackoverflow.com。

- mtyson