← Retour au chapitre

Fiche à trous · Terminale · NSI

Arbres binaires et arbres binaires de recherche

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.

  1. 6.
  2. 7.
  3. 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

  1. 10.
  2. 11.
  3. 12.
  4. 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. 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. 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. 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. 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. 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. 6. 8 est la racine.
  7. 7. 3 < 8 : à gauche ; 10 > 8 : à droite.
  8. 8. 1 < 8 puis 1 < 3 : gauche de 3 ; 6 < 8 puis 6 > 3 : droite de 3.
  9. 9. On descend en comparant à chaque nœud ; le parcours infixe donnera 1, 3, 6, 8, 10.
  10. 10. Traiter le cas de l'arbre vide.
  11. 11. Appeler la fonction sur le sous-arbre gauche.
  12. 12. Traiter le nœud au moment voulu (avant, entre, après).
  13. 13. Appeler la fonction sur le sous-arbre droit.