mardi 10 janvier 2012

5-Programmer avec le langage C# Arbres binaires

1. Notions générales sur les structures d'arbres

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

0 commentaires:

Enregistrer un commentaire

Share

Twitter Delicious Facebook Digg Stumbleupon Favorites

 

IP