Al caminar por un árbol, primero el padre

Question

¿Cuál es la mejor forma de visitar todos los nodos de un árbol vinculado (todos los nodos tienen referencias a padres y todos los secundarios, los nodos raíz tienen nulo como padre), de modo que no se visita ningún nodo antes de sus antepasados? Brownie señala por no recursivo.

Answer 1

pseudo código:

NodesToVisit = some stack or some list 
NodesToVisit.Push(RootNode) 

While NodesToVisit.Length > 0 
{ 
    CurNode = NodesToVisit.Pop() 
    For each Child C in CurNode 
     NodesToVisit.Push(C) 
    Visit(CurNode) (i.e. do whatever needs to be done) 
} 

Editar: recursiva o no?
Para ser técnicamente correcto, y como se ha señalado por AndreyT y otros en este puesto, este enfoque es una forma de un algoritmo recursivo, por lo que una pila administrada de forma explícita se utiliza en lugar de la pila de la CPU y donde la recursión se lleva a cabo en el nivel del ciclo While. Dicho esto, se diferencia de una implementación recursiva per se en un par de maneras sutiles pero importantes:

• Sólo las "variables" se inserta en la pila; no hay un "marco de pila" y una dirección de retorno asociada en la pila, la única "dirección de retorno" está implícita en el ciclo while, y solo hay una instancia de la misma.
• La "pila" podría usarse como una lista por la cual el siguiente "marco" podría tomarse en cualquier lugar de la lista, sin frenar la lógica de ninguna manera.

Answer 2

Cree una lista de nodos en la raíz (nivel 0), itere sobre cada nodo por turno y busque hijos directos (cuyo nodo padre es el nodo que estamos buscando actualmente) (nivel 1), cuando termine con nivel 0 pase a iterar el nivel 1, y así sucesivamente hasta que no tenga nodos restantes no visitados.

Answer 3

Usa un conjunto de nodos. Coloque la raíz en el conjunto para comenzar. Luego, en un bucle, saca un nodo del conjunto, visítalo y luego coloca sus hijos en el conjunto. Cuando el conjunto está vacío, has terminado.

Answer 4

En pseudocódigo:

currentList = list(root) 
nextList = list() 
while currentList.count > 0: 
    foreach node in currentList: 
     nextList.add(node.children) 
    currentList = nextList 

Answer 5

Usted está buscando un recorrido en preorden. Creo que puedes hacerlo de forma no recursiva con una cola :. En pseudocódigo:

Cree una cola vacía, luego presione el nodo raíz.

while nonempty(q) 
    node = pop(q) 
    visit(node) 
    foreach child(node) 
    push(q,child) 

Answer 6

Breadth First Search

Answer 7

Si se inicia en el nodo raíz, y sólo visita los padres/hijos de nodos que ya ha visitado, no hay ninguna manera a recorrer el árbol de tal manera que se visita un nodo antes de visitar a sus antepasados.

Cualquier tipo de recorrido, la profundidad primero (recursiva/basada en la pila), la amplitud primero (basada en la cola), la profundidad limitada, o simplemente sacarlos de un conjunto desordenado, funcionará.

El "mejor" método depende del árbol. La amplitud primero funcionaría bien para un árbol muy alto con pocas ramas. La profundidad primero funcionaría bien para los árboles con muchas ramas.

Dado que los nodos en realidad tienen punteros a sus padres, también hay un algoritmo de memoria constante, pero es mucho más lento.

Answer 8

Si tiene enlaces a todos los niños y al padre también, entonces el algoritmo no recursivo es bastante trivial. Solo olvida que tienes un árbol. Piense que es un labirynth donde cada enlace padre-hijo es un corredor bidireccional ordinario de una unión a la otra. Todo lo que necesita hacer para recorrer todo el laberinto es girar al siguiente corredor a la izquierda en cada cruce. (Alternativamente, piense que camina por el laberinto con la mano izquierda tocando siempre la pared del lado izquierdo). Si comienzas desde la unión raíz (y te mueves en cualquier dirección), caminarás por todo el árbol siempre visitando a los padres antes que a los niños. Cada "corredor" en este caso será recorrido dos veces (en una dirección y en la otra), y cada "cruce" (nodo) será visitado tantas veces como muchos "corredores" se unan a él.

Answer 9

No estoy de acuerdo con la primera búsqueda de amplitud ya que la complejidad del espacio suele ser la perdición de ese algoritmo de búsqueda específico. Posiblemente el uso del algoritmo de profundización iterativa sea una mejor alternativa para este tipo de uso, y cubre el mismo tipo de recorrido que la primera búsqueda de amplitud. Hay pequeñas diferencias al tratar con el margen desde la búsqueda de ancho, sin embargo, no debería ser demasiado difícil (pseudo) descifrar el código.

Referencia: http://en.wikipedia.org/wiki/Iterative_deepening

Answer 10

Aquí hay una verdadera enfoque no recursivo: sin pila, espacio constante. Este código Python supone que cada nodo contiene una lista de los niños, y que los objetos de nodo no definen la igualdad, por lo que la función de 'índice' es la comparación de identidades:

def walkTree(root, visit_func): 
    cur = root 
    nextChildIndex = 0 

    while True: 
     visit_func(cur) 

     while nextChildIndex >= len(cur.children) and cur is not root: 
      nextChildIndex = cur.parent.children.index(cur) + 1 
      cur = cur.parent 

     if nextChildIndex >= len(cur.children): 
      break 

     cur = cur.children[nextChildIndex] 
     nextChildIndex = 0 

Estoy seguro de que podría ser pulida hasta un poco, hecho más conciso y fácil de leer, pero esa es la esencia.