自从我在大学学习 数据结构和算法 以来已经有一段时间了，所以最近令我惊讶的是，有人提出递归可能不是进行树遍历 的方式 （tm）。由于某种原因，基于队列的遍历并不是我一直使用的技术。
如果有的话，迭代遍历与递归遍历的优点是什么？在什么情况下我可以使用一种而不是另一种？
如果您要进行广度优先搜索，自然的实现是将节点推入队列，而不是使用递归。
如果要进行深度优先搜索，则递归是编码遍历的最自然的方法。但是，除非您的编译器将尾部递归优化到迭代中，否则递归实现将比迭代算法慢，并且将死于足够深的树上的堆栈溢出。
一些快速的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)
