Arbres binaires

Activités

1. Trouvez les feuilles
2. Taille et hauteur
3. Parcours en largeur d'abord
4. Parcours préfixe
5. Parcours infixe
6. Parcours suffixe
7. Choix de parcours aléatoire
8. Parcours chronométrés
9. Insérer dans un arbre binaire de recherche
10. Valeurs possibles dans un arbre binaire de recherche

Implémentations

Sous forme d'un tableau :

1. Étude préalable sur papier
2. TP sur Capytale

Sous forme de triplet :

1. Étude préalable sur papier
2. TP sur Capytale

Idées de projets

• Codage de Huffman
• Arbre généalogique
• Transformation d'un arbre quelconque en arbre binaire
• Nombre de Strahler
• Arbre de décision
• Arbre syntaxique
• Équilibrer un arbre binaire de recherche
• Arborescence des fichiers dans un système d'exploitation Linux
• Partition binaire de l'espace
• Convertir un arbre binaire en chaîne de caractères pour affichage, par exemple :

          _______0__
         /          \
      __1____        7
     /       \      / \
    2        3     8    1
   / \      /            \
  4   6    2              9
  

• Dessiner récursivement une plante avec la tortue. Vous pouvez exécuter et étudier le code suivant, puis l'améliorer :

  from turtle import *
  
  def arbre(hauteur):
      if hauteur > 1:
          forward(100)
          right(25)
          arbre(hauteur-1)
          left(50)
          arbre(hauteur-1)
          right(25)
          back(100)
  penup()
  left(90)
  back(150)
  pendown()
  color("brown")
  arbre(5)
  done()
  

  Voir ci-dessous un exemple de plante qu'on peut obtenir.