algorithm - implement - tree structure architecture
Caminando por un árbol, padres primero (10)
¿Cuál es la mejor manera de visitar todos los nodos de un árbol vinculado (todos los nodos tienen referencias a padres y todos los hijos, los nodos raíz tienen nulo como primario), de modo que ningún nodo se visita antes que ninguno de sus antepasados? Brownie señala por no recursivo.
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 en el que estamos actualmente buscando) (nivel 1), cuando termine con el nivel 0 siga adelante para iterar el nivel 1, y así sucesivamente hasta que no tenga nodos restantes no visitados.
En pseudocódigo:
currentList = list( root )
nextList = list()
while currentList.count > 0:
foreach node in currentList:
nextList.add(node.children)
currentList = nextList
Está buscando un recorrido de 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)
No estaría 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
Si comienza en el nodo raíz y solo visita los padres / hijos de los nodos que ya ha visitado, no hay forma de recorrer el árbol de manera que visite un nodo antes de visitar a sus antepasados.
Cualquier tipo de recorrido, profundidad primero (recursivo / basado en pila), ancho primero (basado en cola), 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.
Como los nodos en realidad tienen punteros hacia sus padres, también hay un algoritmo de memoria constante, pero es mucho más lento.
Use 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.
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.
Aquí hay un enfoque verdaderamente no recursivo: sin apilamiento, 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 ''index'' 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, ser más conciso y fácil de leer, pero esa es la esencia.
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)
}
Edición : ¿Recursivo o no?
Para ser técnicamente correcto, y como lo señalan AndreyT y otros en esta publicación, este enfoque es una forma de algoritmo recursivo, mediante el cual se utiliza una pila explícitamente administrada en lugar de la pila de la CPU y donde la recursión tiene lugar a nivel de el bucle While. Dicho esto, difiere de una implementación recursiva per se en un par de formas sutiles pero significativas:
- Solo las "variables" son empujadas a 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 "cuadro" podría tomarse en cualquier parte de la lista, sin frenar la lógica de ninguna manera.