Caminando un árbol, padre primero

Question

¿Cuál es la mejor manera de visitar todos los nodos de un árbol vinculado (todos los nodos tienen referencias a padre y todos los hijos, los nodos raíz tienen nulo como padre), para que no se visite ningún nodo antes que cualquiera de sus antepasados? Brownie puntos por no recursivo.

Answer 1

Pseudocó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 : ¿Recursivo o no?
Para ser técnicamente correcto, y como lo señalaron AndreyT y otros en esta publicación, este enfoque es una forma de un algoritmo recursivo, mediante el cual se utiliza una pila explícitamente administrada en lugar de la pila de CPU y dónde tiene lugar la recursividad al nivel del bucle While. Dicho esto, difiere de una implementación recursiva per se en un par de formas sutiles pero significativas:

• Solo las " variables " son empujados a la pila; no hay "marco de pila" y la dirección de retorno asociada en la pila, la única " dirección de retorno " está implícito en el ciclo while, y solo hay una instancia de él.
• La " pila " podría usarse como una lista en la que el próximo "marco" podría llevarse a cualquier parte de la lista, sin frenar la lógica de ninguna manera.

Answer 2

Breadth First Search

Answer 3

Estás buscando un recorrido previo al pedido. Creo que puedes hacerlo de forma no recursiva con una fila:. 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 4

Si tiene enlaces a todos los hijos y también a los padres, entonces el algoritmo no recursivo es bastante trivial. Solo olvida que tienes un árbol. Piense en esto es un labirynth donde cada enlace padre-hijo es un corredor bidireccional ordinario de un cruce a otro. Todo lo que necesita hacer para caminar por todo el laberinto es girar hacia el siguiente corredor a la izquierda en cada cruce. (Alternativamente, piense en ello como caminar por el laberinto con la mano izquierda siempre tocando la pared del lado izquierdo). Si comienza desde la unión de la raíz (y se mueve en cualquier dirección), caminará todo el árbol siempre visitando a los padres antes que a los niños. Cada " corredor " en este caso se viajará dos veces (en una dirección y en la otra), y cada '' cruce '' (nodo) se visitará tantas veces como '' corredores '' únete.

Answer 5

Use un conjunto de nodos. Ponga la raíz en el conjunto para comenzar. Luego, en un bucle, extraiga un nodo del conjunto, visítelo y luego coloque a sus hijos en el conjunto. Cuando el conjunto está vacío, ya está.

Answer 6

En pseudocódigo:

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

Answer 7

Si comienza en el nodo raíz y solo visita a los padres / hijos de los nodos que ya ha visitado, no hay forma de atravesar el árbol de modo que visite un nodo antes de visitar a sus antepasados .

Cualquier tipo de recorrido, primero en profundidad (recursivo / basado en pila), primero en ancho (basado en cola), limitado en profundidad, o simplemente sacándolos de un conjunto desordenado, funcionará.

El " mejor " El 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 á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

No estaría de acuerdo con la primera búsqueda de amplitud ya que la complejidad del espacio es a menudo la ruina de ese algoritmo de búsqueda específico. Posiblemente, el uso del algoritmo de profundización iterativa es una mejor alternativa para este tipo de uso, y cubre el mismo tipo de recorrido que la primera búsqueda de amplitud. Existen pequeñas diferencias en el tratamiento de los márgenes de la búsqueda de amplitud, aunque no debería ser demasiado difícil (pseudo) codificar.

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

Answer 9

Aquí hay un enfoque verdaderamente no recursivo: sin pila, espacio constante. Este código de Python supone que cada nodo contiene una lista de elementos secundarios y que los objetos del nodo no definen la igualdad, por lo que la función 'índice' está comparando 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 pulirse un poco, hacerse más conciso y más fácil de leer, pero esa es la esencia.

Answer 10

Cree una lista de nodos en la raíz (nivel 0), itere sobre cada nodo a su vez y busque hijos directos (cuyo nodo principal es el nodo desde el que estamos buscando actualmente) (nivel 1), cuando termine con el nivel 0 pase al nivel iterativo 1, y así sucesivamente hasta que no queden nodos no visitados.