Parcours d'arbre
classes d'algorithmes De Wikipédia, l'encyclopédie libre
classes d'algorithmes De Wikipédia, l'encyclopédie libre
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.
É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].
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.
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].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
