Premier algorithme de recherche de profondeur non récursif

Question

Je cherche un premier algorithme de recherche de profondeur non récursive pour un arbre non binaire. Toute aide est fortement appréciée.

Answer 1

DFS:

 list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
  currentnode = nodes_to_visit.first();
  nodes_to_visit.prepend( currentnode.children );
  //do something
}
 

BFS:

 list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
  currentnode = nodes_to_visit.first();
  nodes_to_visit.append( currentnode.children );
  //do something
}
 

La symétrie des deux est assez cool.

Answer 2

Vous utiliseriez une pile contenant les nœuds non encore visités:

 stack.push(root)
while !stack.isEmpty() do
    node = stack.pop()
    for each node.childNodes do
        stack.push(stack)
    endfor
    // …
endwhile
 

Answer 3

Si vous avez des pointeurs sur les nœuds parents, vous pouvez le faire sans mémoire supplémentaire.

 def dfs(root):
    node = root
    while True:
        visit(node)
        if node.first_child:
            node = node.first_child      # walk down
        else:
            while not node.next_sibling:
                if node is root:
                    return
                node = node.parent       # walk up ...
            node = node.next_sibling     # ... and right
 

Notez que si les nœuds enfants sont stockés sous forme de tableau plutôt que via des pointeurs frères, le frère suivant peut être trouvé comme suit:

 def next_sibling(node):
    try:
        i =    node.parent.child_nodes.index(node)
        return node.parent.child_nodes[i+1]
    except (IndexError, AttributeError):
        return None
 

Answer 4

Utilisez une pile pour suivre vos nœuds

 Stack<Node> s;

s.prepend(tree.head);

while(!s.empty) {
    Node n = s.poll_front // gets first node

    // do something with q?

    for each child of n: s.prepend(child)

}
 

Answer 5

Bien que "utiliser une pile" puisse fonctionner comme une réponse à une question d'entrevue inventée, en réalité, il s'agit simplement de faire explicitement ce qu'un programme récursif fait en coulisse.

La récursivité utilise la pile intégrée aux programmes. Lorsque vous appelez une fonction, il pousse les arguments de la fonction sur la pile et, lorsque la fonction retourne, il le fait en vidant la pile du programme.