Un tableau ou une liste chaînée se parcourent dans un seul ordre naturel : du premier au dernier. Un arbre, lui, se divise : après la racine, on va à gauche ou à droite ? On finit tout un côté avant l'autre, ou on avance étage par étage ?

Parcourir un arbre, c'est visiter chacun de ses nœuds exactement une fois (pour l'afficher, le compter, chercher une valeur...). Il existe deux grandes familles de parcours :

• le parcours en largeur : étage par étage, comme on lit un texte, ligne par ligne ;
• les parcours en profondeur : on descend le plus loin possible dans un côté avant de passer à l'autre. Il y en a trois, préfixe, infixe et suffixe, qui diffèrent par le moment où on écrit le nœud.

Toutes les animations de ce chapitre utilisent cet arbre. Tu verras que les quatre parcours donnent quatre ordres différents.