🌳 Arbre binaire

🎯 Objectifs pédagogiques

• Comprendre les structures de données de type arbre binaire.
• Savoir implémenter un arbre binaire en Python.
• Apprendre à parcourir un arbre binaire (préfixe, infixe, postfixe).
• Savoir insérer et supprimer des nœuds dans un arbre binaire.

📜 Énoncé

Vous allez créer un arbre binaire de recherche (Binary Search Tree - BST), c’est-à-dire un arbre binaire tel que pour chaque nœud :

• les valeurs du sous-arbre gauche sont strictement inférieures à la valeur du nœud,
• les valeurs du sous-arbre droit sont supérieures ou égales à la valeur du nœud.

🧩 Partie 1 — Implémentation de la structure

1. Implémentez une classe Node représentant un nœud de l’arbre avec :

   • un attribut val (valeur),
   • un attribut left (fils gauche),
   • un attribut right (fils droit).

2. Implémentez une classe BinarySearchTree avec :

   • un attribut root (racine de l’arbre),
   • une méthode insert(val) pour insérer une valeur selon les règles du BST,
   • une méthode delete(val) pour supprimer un nœud (voir note plus bas).
   • une méthode contains(val) qui retourne True si la valeur est dans l’arbre.
   • une méthode height() qui retourne la hauteur de l’arbre. C'est-à-dire le nombre maximal de niveaux de l'arbre, où la racine est au niveau 0.

La suppression doit gérer trois cas :

• Le nœud à supprimer est une feuille (aucun enfant),
• Le nœud a un seul enfant (remplacer par l’enfant),
• Le nœud a deux enfants (remplacer par son successeur immédiat, c’est-à-dire la plus petite valeur de son sous-arbre droit).

🔁 Partie 2 — Parcours de l’arbre

Ajoutez à la classe BinarySearchTree trois méthodes pour parcourir l’arbre et afficher les valeurs dans l’ordre approprié :

• traverse_inorder(): parcours infixe (gauche, racine, droite),
• traverse_preorder(): parcours préfixe (racine, gauche, droite),
• traverse_postorder(): parcours postfixe (gauche, droite, racine).

🧪 Partie 3 — Tests et démonstration

Créez des tests pour vérifier le bon fonctionnement de votre implémentation. Par exemple :

1. Créez un arbre à partir des valeurs suivantes, insérées dans cet ordre : 50, 30, 70, 20, 40, 60, 80

2. Afficher et vérifier l’arbre selon les trois types de parcours.

3. Supprimez les nœuds suivants dans cet ordre : 20, 30, 50

4. Réaffichez et revérifier l’arbre après chaque suppression.

📝 Pour vous aidez

Si vous êtes bloqué, voici quelques ressources utiles :

attention

Attention, ne pas simplement copier-coller le code de ces ressources. Essayez de l'écrire par vous-même en vous inspirant des exemples.

• GeeksforGeeks - Binary Search Tree
• w3schools