La structure d'arbre est très utilisée en informatique. Sur le fond on peut considérer un arbre comme une généralisation d'une liste car les listes peuvent être représentées par des arbres. La complexité des algorithmes d'insertion de suppression ou de recherche est généralement plus faible que dans le cas des listes ( cas particulier des arbres équilibrés). Les mathématiciens voient les arbres eux-même comme des cas particuliers de graphes non orientés connexes et acycliques, donc contenant des sommets et des arcs :
fig-1 fig-2 fig-3
Ci dessus 3 représentations graphiques de la même structure d'arbre : dans la figure fig-1 tous les sommets ont une disposition équivalente, dans la figure fig-2 et dans la figure fig-3 le sommet "cerclé" se distingue des autres.
Lorsqu'un sommet est distingué par rapport aux autres, on le dénomme racine et la même structure d'arbre s'appelle une arborescence, par abus de langage dans tout le reste du document nous utliserons le vocable arbre pour une arborescence.
Enfin certains arbres particuliers nommés arbres binaires sont les plus utilisés en informatique et les plus simples à étudier. En outre il est toujours possible de "binariser" un arbre non binaire, ce qui nous permettra dans ce chapitre de n'étudier que les structures d'arbres binaires.
Télécharger le livre ici :
Livret_08_ArbreCsharp
Jeu de briques
Snake
Pacman
Bubble