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.
La figure suivante 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. Les racines des sous-arbres sont les
n
uds de l'arbre ; cet arbre a 13
nuds. Les feuilles d'un arbre sont des
sous-arbres dont les deux fils sont des arbres vides; les feuilles de
cet arbre sont étiquetées par 8, 5, 9, 12, 13, 11. Les nuds qui ne
sont pas des feuilles sont dits internes .
