Traversée d’arbres

Contrairement aux listes chaînées, aux tableaux unidimensionnels et aux autres structures de données linéaires, qui sont canoniquement traversées dans un ordre linéaire, les arbres peuvent être traversés de plusieurs façons. Ils peuvent être parcourus dans l’ordre profondeur-première ou largeur-première. Il existe trois façons courantes de les parcourir en ordre de profondeur : en ordre, en pré-ordre et en post-ordre. Au-delà de ces traversées de base, divers schémas plus complexes ou hybrides sont possibles, tels que les recherches limitées en profondeur comme la recherche itérative en profondeur et en premier. Cette dernière, ainsi que la recherche breadth-first, peut également être utilisée pour traverser des arbres infinis, voir ci-dessous.

Structures de données pour la traversée d’arbresEdit

Traverser un arbre implique d’itérer sur tous les nœuds d’une certaine manière. Parce qu’à partir d’un nœud donné, il y a plus d’un nœud suivant possible (ce n’est pas une structure de données linéaire), alors, en supposant un calcul séquentiel (pas parallèle), certains nœuds doivent être différés-stockés d’une certaine manière pour être visités plus tard. Cela se fait souvent via une pile (LIFO) ou une file d’attente (FIFO). Comme un arbre est une structure de données autoréférentielle (définie de manière récursive), la traversée peut être définie par récursion ou, plus subtilement, par corecursion, de manière très naturelle et claire ; dans ces cas, les nœuds différés sont stockés implicitement dans la pile d’appel.

La recherche en profondeur d’abord est facilement mise en œuvre via une pile, y compris de manière récursive (via la pile d’appel), tandis que la recherche en largeur d’abord est facilement mise en œuvre via une file d’attente, y compris de manière corecursive.:45-61

Recherche en profondeur d’un arbre binaireEdit

Traversée en profondeur (chemin pointillé) d’un arbre binaire:

• Pré-ordre (accès au nœud en position rouge ●) :

  F, B, A, D, C, E, G, I, H;

• En ordre (accès aux nœuds en position vert ●):

  A, B, C, D, E, F, G, H, I;

• Post-ordre (accès aux nœuds en position bleu ●):

  A, C, E, D, B, H, I, G, F.

Ces recherches sont dites depth-first search (DFS), car l’arbre de recherche est approfondi autant que possible sur chaque enfant avant de passer au frère ou à la sœur suivant(e). Pour un arbre binaire, elles sont définies comme des opérations d’accès à chaque nœud, en commençant par le nœud courant, dont l’algorithme est le suivant :

Le schéma récursif général pour traverser un arbre binaire est le suivant :

1. Descendre d’un niveau jusqu’à l’argument récursif N. Si N existe (est non vide), exécuter les trois opérations suivantes dans un certain ordre : L : parcourir récursivement le sous-arbre gauche de N. R : Parcourt récursivement le sous-arbre droit de N. N : Accéder (visiter) le nœud courant N lui-même.
2. Retourner en remontant d’un niveau et en arrivant au nœud parent de N.

Il existe trois méthodes (motifs) à quelle position du parcours (traversée) par rapport au nœud (dans la figure : rouge, vert ou bleu) la visite (l’accès) du nœud doit avoir lieu. Le choix d’une seule couleur détermine exactement une visite d’un nœud, comme décrit ci-dessous. L’accès aux trois couleurs entraîne une triple visite du même nœud donnant la séquentialisation « tout-ordre » :

F-B-A-A-B-D-C-C-D-E-E-D-F-G-G- I-H-H- I- I-G-F

Pré-ordre, NLREdit

1. Accéder à la partie données du nœud courant (dans la figure : position rouge).
2. Traverser le sous-arbre gauche en appelant récursivement la fonction de préordre.
3. Traverser le sous-arbre droit en appelant récursivement la fonction de préordre.

La traversée en pré-ordre est une traversée topologiquement triée, car un nœud parent est traité avant que l’un de ses nœuds enfants ne le soit.

En ordre, LNREdit

1. Traverser le sous-arbre gauche en appelant récursivement la fonction en ordre.
2. Accéder à la partie données du nœud courant (dans la figure : position verte).
3. Traverser le sous-arbre droit en appelant récursivement la fonction in-order.

Dans un arbre de recherche binaire ordonné de telle sorte que dans chaque nœud la clé est supérieure à toutes les clés de son sous-arbre gauche et inférieure à toutes les clés de son sous-arbre droit, la traversée in-order récupère les clés dans l’ordre trié croissant.

Traversée en ordre inverse, RNLEdit

1. Traverser le sous-arbre droit en appelant récursivement la fonction de traversée en ordre inverse.
2. Accéder à la partie données du nœud actuel.
3. Traverser le sous-arbre gauche en appelant récursivement la fonction de traversée en ordre inverse.

Dans un arbre de recherche binaire, la traversée en ordre inverse récupère les clés dans l’ordre trié décroissant.

Post-ordre, LRNEdit

1. Traverser le sous-arbre gauche en appelant récursivement la fonction post-ordre.
2. Traverser le sous-arbre droit en appelant récursivement la fonction post-ordre.
3. Accéder à la partie données du nœud courant (dans la figure : position bleu).

La trace d’une traversée est appelée une séquentialisation de l’arbre. La trace de la traversée est une liste de chaque nœud visité. Aucune séquentialisation selon le pré-, l’in- ou le post-ordre ne décrit l’arbre sous-jacent de manière unique. Étant donné un arbre avec des éléments distincts, le pré-ordre ou le post-ordre associé au in-ordre est suffisant pour décrire l’arbre de manière unique. Cependant, le pré-ordre avec le post-ordre laisse une certaine ambiguïté dans la structure de l’arbre.

Générique treeEdit

Pour parcourir n’importe quel arbre avec une recherche en profondeur, effectuez les opérations suivantes à chaque nœud :

1. Si le nœud n’est pas présent, retour.
2. Accès (= visite) au nœud (position de pré-ordre).
3. Pour chaque i de 1 à nombre_d’enfants – 1 faire :
   1. Recourir le i-ième enfant.
   2. Noeud d’accès (position in-order).
4. Recursivement traverse le dernier enfant.
5. Noeud d’accès (position post-order).

Selon le problème posé, les opérations de pré-ordre, post-ordre, et surtout l’une des (nombre_d’enfants – 1) dans l’ordre peuvent être nulles, ou l’accès seulement à un enfant spécifique est voulu, donc ces opérations sont facultatives. En outre, dans la pratique, plus d’une des opérations pre-order, in-order et post-order peut être nécessaire. Par exemple, lors de l’insertion dans un arbre ternaire, une opération de pré-ordre est effectuée en comparant les éléments. Une opération de post-ordre peut être nécessaire ensuite pour rééquilibrer l’arbre.

Recherche en largeur-première, ou ordre de niveauEdit

Ordre de niveau : F, B, G, A, D, I, C, E, H.

Les arbres peuvent également être parcourus dans l’ordre des niveaux, où nous visitons chaque nœud d’un niveau avant de passer à un niveau inférieur. Cette recherche est appelée breadth-first search (BFS), car l’arbre de recherche est élargi autant que possible sur chaque profondeur avant de passer à la profondeur suivante.

Autres typesEdit

Il existe également des algorithmes de traversée d’arbres qui ne se classent ni dans la recherche en profondeur ni dans la recherche en largeur. L’un de ces algorithmes est la recherche d’arbre de Monte Carlo, qui se concentre sur l’analyse des coups les plus prometteurs, en basant l’expansion de l’arbre de recherche sur un échantillonnage aléatoire de l’espace de recherche.

.