Breadth-first search / Recherche en profondeur
BFS parcourt l’arbre en augmentant la profondeur jusqu’à la racine.
BFS(Graph G, Node s):
{
f = CreateQueue();
f.stack(s);
mark(s);
while non f.empty()
s = f.pop();
print(s);
for each children t of s in G
if t unmarked DO
f.stack(t);
mark(t);
end if
end for
end while
}In-depth search : pre-order
Les algorithmes en profondeur sont récursifs. Dans le chemin du préfixe, nous parcourons toujours le sous-arbre de gauche avant de traiter le sous-arbre de droite.
- Vérifiez si le nœud actuel est vide ou nul.
- Affiche la partie données de la racine (ou du nœud actuel).
- Parcourez le sous-arbre de gauche en appelant de manière récursive la fonction de pré-ordre.
- Parcourez le sous-arbre de droite en appelant de manière récursive la fonction de pré-ordre.
In-depth search : in-order
Le LNR parcourt le plus à gauche possible, et affiche les branches de gauche à droite. Cet algorithme affiche les diagonales de bas en haut.
- Vérifiez si le nœud actuel est vide ou nul.
- Parcourez le sous-arbre de gauche en appelant de manière récursive la fonction in-order.
- Affiche la partie données de la racine (ou du nœud actuel).
- Parcourez le sous-arbre de droite en appelant de manière récursive la fonction in-order.
In-depth search : out-order
Il s’agit d’une navigation en diagonale de haut en bas.
- Vérifiez si le nœud actuel est vide ou nul.
- Parcourez le sous-arbre de gauche en appelant de manière récursive la fonction de post-ordre.
- Parcourez le sous-arbre de droite en appelant de manière récursive la fonction de post-ordre.
- Affiche la partie données de la racine (ou du nœud actuel).
