algorithm - 迭代树行走

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)