Tree.
Analyse
Un arbre est un graphe particulier (sans cycle, aux noeuds sont liés et de degré
3 max).
Il peut donc être caractérisé par :
- un noeud racine (root node)
- des noeuds intermédiaires
- des noeuds "feuilles" (leaves) n'ayant plus aucun fils
Chaque noeud a donc une profondeur par rapport la racine.
Parcours
Lors d'un traitement (recherche d'un noeud particulier ou autre), un arbre peut être parcouru de diverses
manières :
- préfixé/préordre : noeud d'abord, puis fils gauche et fils droit
- infixé/inordre : fils gauche d'abord, puis noeud et fils droit
- postfixé/postordre : fils droit d'abord, puis fils gauche et noeud
- profondeur d'abord
- en largeur d'abord
- ou selon une autre règle spécifique à l'arbre (en fonction de la valeur du noeud par exemple, comme dans un BST)