Structures hiérarchiques : les arbres

Chapitre 9

Au programme

…de la partie « Structures de données »

Contenus Capacités attendues Commentaires
- Arbres : structures hiérarchiques.
- Arbres binaires : nœuds, racines, feuilles, sous-arbres gauches, sous-arbres droits.		 - Identifier des situations nécessitant une structure de données arborescente.
- Évaluer quelques mesures des arbres binaires (taille, encadrement de la hauteur, etc.).		 - On fait le lien avec la rubrique « algorithmique ».

…de la partie « Algorithmique »

Contenus Capacités attendues Commentaires
- Algorithmes sur les arbres binaires et sur les arbres binaires de recherche. - 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é. - 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.

Documents