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
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 
se représentent
simplement par des arbres comme dans la figure
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
