ARBRES BINAIRES
PARCOURS D'APPRENTISSAGE
Avec le cours/TP « Arbres binaires » et les exercices, je comprends :
- ce qu'est une structure arborescente (racine, noeuds, sous-arbres), récursive par définition ;
- la relation entre taille et hauteur d'un arbre binaire ;
et je sais :
- déterminer la taille et la hauteur d'un arbre binaire ;
- représenter divers situations à l'aide d'un arbre binaire ;
- implémenter une structure d'arbre binaire en Python avec une classe ;
- écrire et utiliser des fonctions récursives opérant sur les arbres.
Avec le cours/TP « Parcours d'un arbre binaire » et les exercices, je sais :
- Parcourir un arbre binaire en profondeur (par ordre préfixe, infixe et post-fixe) et en largeur,
- Écrire une fonction récursive correspondant à chacun des parcours en profondeur,
- Utiliser une file pour effectuer en largeur.
Avec l'activité d'introduction « Construction d'un Arbre Binaire de Recherche », je comprends :
- la propriété caractéristique d'un ABR ;
- que l'efficacité d'une opération sur un ABR dépend de sa structure (filiforme, plein, ...).
- comment exprimer le coût en temps d'une opération simple comme l'insertion d'une valeur ;
et je sais :
- implémenter une fonction récursive de construction d'un ABR par insertions successives.
À partir du cours/TP « Recherche d'une valeur dans un ABR », je comprend :
- la notion d'ABR équilibré ;
- comment exprimer le coût en temps de l'algorithme de recherche d'une valeur dans un ABR, en fonction de sa hauteur ou de sa taille ;
et je sais :
- implémenter une fonction de recherche récursive opérant sur un ABR.