Structures arborescentes : arbres binaires, parcours, arbres binaires de recherche

En 30 secondes

• Arbre binaire : nœuds avec au plus deux enfants (sous-arbre gauche, sous-arbre droit), à partir d'une racine.
• Trois parcours, seule la position de la racine change : préfixe (racine, gauche, droite), infixe (gauche, racine, droite), postfixe (gauche, droite, racine).
• Arbre binaire de recherche : gauche inférieur, droite supérieur, à chaque nœud ; le parcours infixe donne alors l'ordre croissant.

Ce que tu sauras faire

• Décrire la structure d'un arbre binaire (racine, nœuds, feuilles, sous-arbres).
• Réaliser les parcours préfixe, infixe et postfixe d'un arbre binaire.
• Définir un arbre binaire de recherche et sa propriété d'ordre.

Les mots à connaître

Arbre binaire

une structure hiérarchique composée de nœuds, où chaque nœud a au plus deux enfants (un sous-arbre gauche et un sous-arbre droit), à partir d'un nœud de départ appelé racine.

Racine

le nœud de départ d'un arbre, qui n'a pas de parent.

Nœud

l'élément de base d'un arbre, qui stocke une valeur et des liens vers ses enfants (au plus deux dans un arbre binaire).

Le piège classique

Oublier que le parcours infixe visite TOUJOURS le sous-arbre gauche en entier avant de noter la racine, même si ce sous-arbre contient plusieurs niveaux.

L'astuce

Parcours infixe = « Gauche, Racine, Droite » (G-R-D) : retiens ces trois lettres dans cet ordre précis.