Arbre enraciné - Définition

Construction

Pour construire un arbre à partir de cases ne contenant que des informations, on peut procéder de l'une des trois façons suivantes :

1. Créer une structure de données composée de :
   1. l'étiquette (la valeur contenue dans le nœud),
   2. un lien vers chaque nœud fils,
   3. un arbre particulier, l'arbre vide, qui permet de caractériser les feuilles. Une feuille a pour fils des arbres vides uniquement.
2. Créer une structure de données composée de :
   1. l'étiquette (la valeur contenue dans le nœud),
   2. un lien vers le « premier » nœud fils (nœud fils gauche le cas échéant),
   3. un autre lien vers le nœud frère (le « premier » nœud frère sur la droite le cas échéant).
3. Créer une structure de données composée de :
   1. l'étiquette (la valeur contenue dans le nœud),
   2. un lien vers le nœud père.

On note qu'il existe d'autres types de représentation propres à des cas particuliers d'arbres. Par exemple, le tas est représenté par un tableau d'étiquettes.