迭代树走

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

如果你有一个固定数量的内存专用于堆栈,就像你经常做的那样(这在许多Java JVM配置中尤其是一个问题),如果你有一个深树(或者如果任何一个递归深度很高),递归可能效果不好其他情况); 它会导致堆栈溢出.推动节点访问队列(用于类似BFS的遍历)或堆栈(用于类似DFS的遍历)的迭代方法在几个方面具有更好的内存属性,因此如果这很重要,请使用迭代方法.

递归的优点是表达的简单/优雅,而不是性能.记住,这是为给定算法,问题规模和机器架构选择适当方法的关键.