Parcours d'arbre
En algorithmique, un parcours d'arbre est type d'algorithme effectué sur un arbre (au sens mathématique). C'est un cas particulier de parcours de graphe, c'est-à-dire un processus de visite des sommets du graphe, qui est ici un arbre. C'est un concept fondamental en algorithmique.
Définition modifier
Étant donné un arbre, un parcours est un processus qui part d'un nœud, et visite tous les nœuds du graphe une seule fois, avec la contrainte qu'un nœud ne peut être visité que si l'un de ses voisins a été visité. Dans le cas des arbres, le nœud de départ est souvent la racine, et le parcours passe donc des parents aux enfants. On peut désigner par parcours une numérotation des sommets calculée à partir de ce processus (et qui ne suit pas toujours la propriété)[1].
Types modifier
Les principaux types de parcours d'arbre sont les parcours en profondeur et les parcours en largeur[1]. Un autre type, utilisé en apprentissage automatique est la recherche arborescente Monte-Carlo.
Applications modifier
Les parcours permettent notamment de générer des représentations linéaires des arbres et d'effectuer une recherche dans une structure arborescente[2].
Notes et références modifier
- Olivier Carton, « Parcours d'arbres », sur Université Paris Diderot.
- Olivier Bournez, « Cours 3: Arbres. Parcours. », sur École polytechnique (France)
