Contenus
ToggleParcours de Graphes et Parcours d'Arbres
Breadth-first search / Recherche en profondeur
BFS parcourt l’arbre en augmentant la profondeur jusqu’à la racine.
![Searching In A Tree (Data Structure) 1 Breadth first search Parcours de Graphes](https://complex-systems-ai.com/wp-content/uploads/2016/02/arbre5.png)
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.
![Searching In A Tree (Data Structure) 2 In-depth search : pre-order](https://i0.wp.com/complex-systems-ai.com/wp-content/uploads/2016/02/arbre6.png?resize=198%2C187)
- 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.
![Searching In A Tree (Data Structure) 3 In-depth search : in-order](https://i0.wp.com/complex-systems-ai.com/wp-content/uploads/2016/02/arbre7.png?resize=193%2C196)
- 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.
![Searching In A Tree (Data Structure) 4 In-depth search : out-order](https://i0.wp.com/complex-systems-ai.com/wp-content/uploads/2016/02/arbre8.png?resize=209%2C190)
- 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).