Arbres



next up previous contents index
Next: Files de priorité Up: Index Previous: Table des matières

Arbres

Nous avons déjà vu la notion de fonction récursive dans le chapitre 2. Considérons à présent son équivalent dans les structures de données: la notion d'arbre. Un arbre est soit un arbre atomique (une feuille), soit un n ud et une suite de sous-arbres. Graphiquement, un arbre est représenté comme suit      

 
Figure: Un exemple d'arbre

   

Le n ud est la racine de l'arbre, , , , , , sont les feuilles, , , , , les n uds internes. Plus généralement, l'ensemble des n uds est constitué des n uds internes et des feuilles. Contrairement à la botanique, on dessine les arbres avec la racine en haut et les feuilles vers le bas en informatique. Il y a bien des définitions plus mathématiques des arbres, que nous éviterons ici. Si une branche relie un n ud à un n ud plus bas, on dira que est un ancêtre de . Une propriété fondamentale d'un arbre est qu'un n ud n'a qu'un seul père. Enfin, un n ud peut contenir une ou plusieurs valeurs, et on parlera alors d'arbres étiquetés et de la valeur (ou des valeurs) d'un n ud. Les arbres binaires   sont des arbres tels que les n uds ont au plus 2 fils. La hauteur, on dit aussi la profondeur d'un n ud est la longueur du chemin qui le joint à la racine, ainsi la racine est elle même de hauteur , ses fils de hauteur et les autres n uds de hauteur supérieure à .

Un exemple d'arbre très utilisé en informatique est la représentation des expressions arithmétiques et plus généralement des termes dans la programmation symbolique. Nous traiterons ce cas dans le chapitre sur l'analyse syntaxique, et nous nous restreindrons pour l'instant au cas des arbres de recherche ou des arbres de tri. Toutefois, pour montrer l'aspect fondamental de la structure d'arbre, on peut tout de suite voir que les expressions arithmétiques calculées dans la section gif se représentent simplement par des arbres comme dans la figure gif pour (* (+ 5 (* 2 3)) (+ (* 10 10) (* 9 9))). Cette représentation contient l'essence de la structure d'expression arithmétique et fait donc abstraction de toute notation préfixée ou postfixée.

 
Figure: Représentation d'une expression arithmétique par un arbre 





next up previous contents index
Next: Files de priorité Up: Index Previous: Table des matières