迭代树行走 [英] 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.

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

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屋！