迭代树遍历 [英] Iterative tree walking

问题描述

它已经相当长一段时间，因为我带的的数据结构，并在大学算法的，所以最近我很惊讶一个建议，递归可能不是方式（TM）做树的遍历。出于某种原因，迭代，基于队列遍历一直没有，我曾经使用过的技术。

It's been quite a while since I took data structures and algorithms in college, so I was surprised recently by a suggestion that recursion may not be the way (tm) to do tree traversal. For some reason iterative, queue based traversal has not been a technique that I've ever used.

什么，如果有的话，这些优点的迭代与递归遍历？在什么情况下，我可能会用一个而不是其他？

What, if any, are the advantages of iterative vs. recursive traversal? In what situations might I use one rather than the other?

推荐答案

如果你正在做一个广度优先搜索自然的实现是节点推到一个队列中，不使用递归。

If you are doing a breadth first search the natural implementation is to push nodes into a queue, not to use recursion.

如果你正在做一个深度优先搜索，然后递归是最自然的方式，以$ C C遍历$。但是，除非你的编译器尾递归优化成循环，你的递归实现会比迭代算法慢，而且会死与一个足够深树堆栈溢出。

If you are doing a depth first search then recursion is the most natural way to code the traversal. However, unless your compiler optimizes tail recursion into iteration, your recursive implementation will be slower than an iterative algorithm, and will die with a stack overflow on a deep enough tree.

一些快速的Python来说明差异：

Some quick Python to illustrate the difference:

#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)

这篇关于迭代树遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！