迭代树行走

如果要进行宽度优先搜索,自然实现是将节点推送到队列中,而不是使用递归。

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

一些快速的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)

如果您有一个固定的内存专用于堆栈,正如您经常做的那样(这在许多Java JVM配置中尤其是一个问题),如果您有一个深树(或者如果在任何其他场景中递归深度都很高),递归可能无法正常工作;它会导致堆栈溢出。一种迭代方法,将节点推送到队列(对于bfs,如遍历)或堆栈(对于df,如遍历)上,在若干方面具有更好的内存属性,因此如果这很重要,请使用迭代方法。

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

这取决于您是想进行深度优先遍历还是宽度优先遍历。深度优先是最容易通过递归实现的。在宽度优先的情况下,您需要保留一个节点队列,以便将来扩展。

实际上,您应该使用队列进行广度优先搜索,使用堆栈进行深度优先搜索, 从while循环运行您的算法。 如果执行简单的操作,进行递归函数调用可以显著地拖动程序。 遍历时的操作,可能会导致堆栈溢出,但现在 需要努力去看。

只需在边上有一个哈希,以跟踪已经访问的节点,以防它不是 一棵树,但是一个连接良好的图。

使用递归,因为实际上可能会出现堆栈溢出错误,这就是stack overflow.com。