Définition
Un arbre binaire est une structure de données hiérarchique dans laquelle chaque nœud possède au maximum deux enfants, appelés enfant gauche et enfant droit.
Contrairement aux tableaux ou aux listes chaînées, les arbres permettent de représenter des relations hiérarchiques entre des données. Ils sont utilisés dans de nombreux domaines : les systèmes de fichiers, les bases de données, les compilateurs…
Terminologie
Racine (root) : le nœud au sommet de l'arbre, sans parent. Feuille : un nœud sans enfant. Hauteur : le nombre maximum de nœuds sur un chemin de la racine à une feuille.
Parcours d'un arbre
Il existe trois façons classiques de parcourir un arbre binaire : le parcours préfixe (nœud → gauche → droite), le parcours infixe (gauche → nœud → droite), et le parcours postfixe (gauche → droite → nœud).