árbol iterativo caminar

Question

Ha sido bastante tiempo desde que tomé estructuras de datos y algoritmos en la universidad, así que me sorprendió recientemente por una sugerencia de que la recursividad puede no ser la forma (tm) para hacer el recorrido del árbol. Por alguna razón iterativa, el recorrido basado en la cola no ha sido una técnica que haya usado alguna vez.

¿Cuáles son, si existen, las ventajas del recorrido iterativo frente al recursivo? ¿En qué situaciones podría usar uno en lugar de otro?

Answer 1

Si está haciendo una primera búsqueda de amplitud, la implementación natural es insertar nodos en una cola, no utilizar la recursión.

Si está haciendo una primera búsqueda en profundidad, la recursión es la forma más natural de codificar el recorrido. Sin embargo, a menos que su compilador optimice la repetición de cola en iteración, su implementación recursiva será más lenta que un algoritmo iterativo, y morirá con un desbordamiento de pila en un árbol lo suficientemente profundo.

Algunos Python rápida para ilustrar la diferencia:

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

Answer 2

Depende de si usted quiere hacer primero en profundidad o en amplitud de recorrido. La primera profundidad es la más fácil de implementar a través de la recursión. Con Breadth-first necesita mantener una cola de nodos para expandirse en el futuro.

Answer 3

Si tiene una cantidad fija de memoria dedicada a la pila, como suele hacer (esto es especialmente un problema en muchas configuraciones Java JVM), la recursión puede no funcionar bien si tiene un árbol profundo (o profundidad de recursión) es alto en cualquier otro escenario); causará un desbordamiento de la pila. Un enfoque iterativo, empujar nodos para visitar en una cola (para BFS-like transversal) o stack (para DFS-like transversal) tiene mejores propiedades de memoria de varias maneras, por lo que si esto importa, utilice un enfoque iterativo.

La ventaja de la recursividad es la simplicidad/elegancia de la expresión, no el rendimiento. Recordar que esa es la clave para elegir el enfoque apropiado para un algoritmo, tamaño de problema y arquitectura de máquina dados.

Answer 4

En realidad, debe utilizar la cola para la primera búsqueda de amplitud y apilar para la primera búsqueda de profundidad, y ejecutar su algoritmo desde un ciclo while. Realizar llamadas a funciones recursivas puede arrastrar su programa de manera significativa si realiza operaciones simples al atravesar, y puede causar un desbordamiento de la pila, pero en estos días debería tener que intentar realmente ver uno.

Solo tiene un hash en el lateral para realizar un seguimiento de los nodos ya visitados en caso de que no sea un árbol, pero un gráfico bien conectado.

Answer 5

Vaya con recursivo, porque en realidad podría obtener un error de desbordamiento de pila, y esto es stackoverflow.com, después de todo.