迭代树行走

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

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

实际上,您应该使用队列进行广度优先搜索,使用堆栈进行深度优先搜索, 并从while循环运行算法。 遍历时执行操作,可能会导致堆栈溢出,但现在你会 需要非常努力才能看到一个。

只需在旁边添加一个哈希值,以跟踪已访问的节点,以防没有访问 一棵树,但却是一个连接良好的图。

使用递归方法,因为实际上可能会出现堆栈溢出错误,毕竟这是stackoverflow.com。