Les arbres binaires #

Travaux dirigés #

• énoncé au format pdf
• énoncé sur le site

Arbres #

Programme structure de données #

Contenus : Arbres : structures hiérarchiques. Arbres binaires : nœuds, racines, feuilles, sous-arbres gauches, sous-arbres droits.

Capacités attendues : Identifier des situations nécessitant une structure de données arborescente. Évaluer quelques mesures des arbres binaires (taille, encadrement de la hauteur, etc.).

Commentaires : On fait le lien avec la rubrique « algorithmique ».

Programme algorithmique #

Contenus : Algorithmes sur les arbres binaires et sur les arbres binaires de recherche.

Capacités attendues : Calculer la taille et la hauteur d’un arbre. Parcourir un arbre de différentes façons (ordres infixe, préfixe ou suffixe ; ordre en largeur d’abord). Rechercher une clé dans un arbre de recherche, insérer une clé.

Commentaires : Une structure de données récursive adaptée est utilisée. L’exemple des arbres permet d’illustrer la programmation par classe. La recherche dans un arbre de recherche équilibré est de coût logarithmique.