Marcher un arbre, parent d'abord

Question

Quel est le meilleur moyen de visiter tous les noeuds d'une arborescence liée (tous les noeuds ont des références au parent et tous les enfants, les noeuds racine ont la valeur null en tant que parent), afin qu'aucun noeud ne soit visité avant aucun de ses ancêtres? Points Brownie pour non-récursif.

Answer 1

Pseudo-code:

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

Modifier : récursif ou non?
Pour être techniquement correct, et comme le signalent AndreyT et d’autres dans ce billet, cette approche est une forme de algorithme récursif, dans lequel une pile explicitement gérée est utilisée de la pile du processeur et où la récursivité a lieu au niveau de la boucle While. Cela dit, elle diffère d'une implémentation récursive per se de deux manières subtiles mais néanmoins significatives:

• Uniquement les " variables " sont poussés sur la pile; il n'y a pas de "cadre de pile". et l'adresse de retour associée sur la pile, la seule "adresse de retour". est implicite dans la boucle while, et il n'en existe qu'une instance.
• La & pile; pile " pourrait être utilisé comme une liste par laquelle le prochain "cadre" pourraient être prises n’importe où dans la liste, sans freiner la logique de quelque manière que ce soit.

Answer 2

Recherche en profondeur d'abord

Answer 3

Vous recherchez une traversée en pré-commande. Je pense que vous pouvez le faire de manière non récursive avec une queue:. En pseudocode:

Créez une file d'attente vide, puis poussez le nœud racine.

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

Answer 4

Si vous avez des liens vers tous les enfants et le parent également, l'algorithme non récursif est plutôt trivial. Oublie que tu as un arbre. Pensez-y, c'est un labyrinthe où chaque lien parent-enfant est un couloir bidirectionnel ordinaire d'une jonction à l'autre. Tout ce que vous devez faire pour parcourir tout le labyrinthe est de passer dans le prochain couloir à gauche à chaque intersection. (Sinon, imaginez que vous marchez dans le labyrinthe avec votre main gauche touchant toujours le mur du côté gauche). Si vous partez de la jonction des racines (et que vous vous dirigez dans n'importe quelle direction), vous parcourrez tout l'arbre en visitant toujours les parents avant les enfants. Chaque " corridor " dans ce cas, il sera parcouru deux fois (dans un sens et dans l’autre), et chaque "jonction" (nœud) seront visités autant de fois que de "corridors". rejoignez-le.

Answer 5

Utilisez un ensemble de nœuds. Mettez la racine dans le jeu pour commencer. Puis, en boucle, retirez un nœud de l'ensemble, visitez-le, puis mettez ses enfants dans l'ensemble. Lorsque l'ensemble est vide, vous avez terminé.

Answer 6

En pseudocode:

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

Answer 7

Si vous commencez au nœud racine et ne visitez que les parents / enfants des nœuds que vous avez déjà visités, il n'y a aucun moyen de parcourir l'arbre de sorte que vous visitiez un nœud avant de rendre visite à ses ancêtres. .

Toute sorte de traversée, profondeur d'abord (basée sur la pile récursive), largeur d'abord (basée sur la file d'attente), limite limitée ou tout simplement extraite d'un ensemble non ordonné fonctionnera.

Le "meilleur" méthode dépend de l'arbre. La largeur en premier conviendrait bien pour un très grand arbre avec quelques branches. La profondeur d’abord conviendrait aux arbres à nombreuses branches.

Comme les nœuds ont en fait des pointeurs sur leurs parents, il existe également un algorithme à mémoire constante, mais il est beaucoup plus lent.

Answer 8

Je ne suis pas d'accord avec la recherche en largeur d'abord, car la complexité de l'espace est souvent le fléau de cet algorithme de recherche spécifique. L’utilisation de l’algorithme d’approfondissement itératif est peut-être une meilleure alternative pour ce type d’utilisation et couvre le même type de parcours que la recherche en profondeur. Il existe des différences mineures dans la gestion de la frange de la recherche approfondie en largeur, il ne devrait toutefois pas être trop difficile de (pseudo) coder en sortie.

Référence: http://en.wikipedia.org/wiki/Iterative_deepening

Answer 9

Voici une approche vraiment non récursive: pas de pile, espace constant. Ce code Python suppose que chaque nœud contient une liste d'enfants et que les objets de nœud ne définissent pas l'égalité, de sorte que la fonction 'index' compare les identités:

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

Je suis sûr qu'il pourrait être peaufiné, rendu plus concis et plus facile à lire, mais c'est l'essentiel.

Answer 10

Créez une liste de nœuds à la racine (niveau 0), parcourez chaque nœud à tour de rôle et recherchez les enfants directs (dont le nœud parent est le nœud que nous recherchons actuellement) (niveau 1), lorsque vous avez terminé le niveau 0 passez au niveau 1 itératif, et ainsi de suite jusqu'à ce qu'il ne reste plus de nœuds non visités.