Complétez de mémoire, puis vérifiez avec la page de corrigé.
L'arborescence des dossiers, l'arbre généalogique, le tableau d'un tournoi : beaucoup de données sont hiérarchiques. Les arbres binaires les représentent, et les arbres binaires de recherche permettent de retrouver une valeur très vite.
Vocabulaire
Définition — arbre binaire :
Définition — taille et hauteur :
Parcours
Règle
Arbre binaire de recherche
Définition — ABR :
Règle
Exemple
Insère 8, 3, 10, 1, 6 dans un ABR vide.
6.
7.
8.
Résultat :
Piège
Confondre parcours préfixe et infixe.
Repérer à quel moment on traite le nœud.
Écrire un parcours récursif
10.
11.
12.
13.
Ai-je défini le vocabulaire ?
Mon code est-il testé sur un exemple ?
Ai-je traité les cas limites ?
Ai-je justifié la complexité ou le résultat ?
Corrigé · à détacher
Arbres binaires et arbres binaires de recherche
1.Structure formée de nœuds ; chaque nœud a au plus deux fils (gauche et droit). Le nœud de départ est la racine, un nœud sans fils est une feuille.
2.La taille est le nombre de nœuds ; la hauteur est le nombre de nœuds (ou d'arêtes, selon la convention annoncée) sur la plus longue branche de la racine à une feuille.
3.Préfixe : nœud, gauche, droit. Infixe : gauche, nœud, droit. Suffixe : gauche, droit, nœud. En largeur : niveau par niveau (avec une file). Les parcours en profondeur s'écrivent naturellement de façon récursive.
4.Arbre binaire où, pour chaque nœud, les valeurs du sous-arbre gauche sont inférieures et celles du sous-arbre droit supérieures.
5.Recherche et insertion : comparer à la racine et descendre à gauche ou à droite ; le coût dépend de la hauteur. Le parcours infixe d'un ABR donne les valeurs triées.
6.8 est la racine.
7.3 < 8 : à gauche ; 10 > 8 : à droite.
8.1 < 8 puis 1 < 3 : gauche de 3 ; 6 < 8 puis 6 > 3 : droite de 3.
9.On descend en comparant à chaque nœud ; le parcours infixe donnera 1, 3, 6, 8, 10.
10.Traiter le cas de l'arbre vide.
11.Appeler la fonction sur le sous-arbre gauche.
12.Traiter le nœud au moment voulu (avant, entre, après).