Cette structure de données est définie de façon récursive : un arbre binaire est soit l'arbre vide, soit formé de deux arbres binaires, appelés fils gauche et fils droit.
Les arbres que l'on utilise en informatique sont de plus étiquetés par
des objets (dans les exemple qui suivent, ces objets seront des entiers,
mais les étiquettes peuvent être de n'importe quel type) : un
arbre binaire étiqueté (en anglais labelled binary tree),
ce qu'on abrégera par la suite en << arbre >>, est soit l'arbre vide,
soit formé d'une étiquette et de deux arbres, appelés fils gauche et
fils droit. Un sous-arbre d'un arbre est soit un fils, soit un
sous-arbre d'un fils. Un arbre vide n'a pas de sous-arbre. Les racines
des sous-arbres sont les n
uds de
l'arbre. Les feuilles d'un arbre sont des
sous-arbres dont les deux fils sont des arbres vides. Les nuds qui
ne sont pas des feuilles sont dits internes.
La figure 20 représente un arbre binaire étiqueté par des
entiers. Cet arbre est non vide ; il a donc une
racine, étiquetée par 1, et deux fils ; ses
nuds internes sont étiquetés par 1, 2, 3, 4, 6, 7, 10 ; ses
feuilles sont étiquetées par 8, 5, 9, 12, 13, 11 ; il a en tout 13
nuds.
