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
-
Chapitre 9,1 : Structures de données abstraites arborescentes : les arbres
-
Chapitre 9,2 : Les arbres binaires
-
Chapitre 9,3 : Les arbres binaire de recherche
-
Chapitre 9,4 : Le codage de Huffman
-
Chapitre 9,5 : Le problème du sac à dos
-
Chapitre 9,6 : TP révision : Le rendu de monnaie