TP - Implémenter une structure d'arbre binaire

Ce TP doit conduire à créer de A à Z un module utilisable tout le reste de l'année.

Téléchargez le fichier « à trous » arbres_binaires.py (clic droit -> [Enregistrer la cible du lien sous]) et enregistrez-le dans le répertoire courant.

Ce TP a pour but de définir une structure de données implémentant des arbres binaires muables en programmation orientée objet.

Remarque importante

La partie 1 va permettre d'implémenter une classe ArbreBinaire dont l'interface sera celle vue en cours.
La partie 2 va compléter cette implémentation par de nouvelles méthodes, ce qui pourra permettre de modifier l'interface.

Partie A - Classe ArbreBinaire

Les objets de la classe ArbreBinaire sont munis de trois attributs : noeud, fg et fd initialisés à None par défaut.

Remarque

On a muni cette classe d'une méthode affichage() déjà programmée qui permettra d'afficher l'arbre à l'aide du module turtle dans la Partie 2. Pour l'instant, cette méthode n'est pas utilisable et il est inutile de chercher à la modifier.

Complétez les méthodes de cette classe et vérifiez votre travail à l'aide du plan de test qui suit.

Le code à compléter

class ArbreBinaire:
    """
    Implémentation d'arbres binaires
    """

    def __init__(self, noeud=None, fg=None, fd=None):
        """
        Initialisation d'un arbre binaire
        """
        pass

    def est_vide(self):
        """
        Sortie: bool - lien True si l'arbre binaire est vide,
                False sinon
        """
        pass

    def racine(self):
        """
        Sortie: elt - valeur de la racine, éventuellement None
        """
        pass

    def fils_gauche(self):
        """
        Sortie: ArbreBinaire - lien vers le fils gauche (soit un ArbreBinaire, soit None)
                Attention aux effets de bord
        """
        pass

    def fils_droit(self):
        """
        Sortie: ArbreBinaire - lien vers le fils droit (soit un ArbreBinaire, soit None)
                Attention aux effets de bord
        """
        pass

    def __repr__(self):
        """
        Sortie: str - Chaîne d'affichage de l'arbre binaire "en ligne"
        """
        pass

Plan de test

On définit un arbre « à la main » :

if __name__ == "__main__":
    a = ArbreBinaire(7)
    b = ArbreBinaire(0)
    c = ArbreBinaire(1, a, b)
    d = ArbreBinaire(6)
    e = ArbreBinaire(5, None, d)
    f = ArbreBinaire(2, c, e)
    g = ArbreBinaire(8)
    h = ArbreBinaire(4, g)
    arbre = ArbreBinaire(3, f, h)

Puis on teste dans la console :

>>> arbre
(3, (2, (1, (7, (), ()), (0, (), ())), (5, (), (6, (), ()))), (4, (8, (), ()), ()))

>>> arbre.racine()
3

>>> arbre.fils_gauche()
(2, (1, (7, (), ()), (0, (), ())), (5, (), (6, (), ())))

>>> arbre.fils_droit().racine()
4

Partie B - Interface améliorée

Dans cette partie, il va falloir reprogrammer une partie des fonctions déjà étudiées dans le premier TP sous une forme « orientée objet ».

Conseil général

N'oubliez pas de gérer le fait que les fils peuvent valoir None...

1. Copiez, collez et complétez la définition de la méthode est_feuille() qui renvoie True pour un arbre réduit à une feuille.

   def est_feuille(self):
       """
       Sortie: bool - True si l'arbre binaire est réduit à une feuille,
               False sinon
       """
   

   Plan de test

   >>> a = ArbreBinaire()
   >>> a.est_feuille()
   False
   >>> b = ArbreBinaire(8)
   >>> b.est_feuille()
   True
   >>> c = ArbreBinaire(8, b)
   >>> c.est_feuille()
   False
   

2. Définissez la méthode hauteur() qui renvoie la hauteur de l'arbre (0 pour l'arbre vide, 1 pour un arbre réduit à une feuille).
   Vérifier que la méthode affichage() est dorénavant fonctionnelle.

3. Surchargez la méthode __len__() qui renvoie la taille (le nombre de nœuds) de l'arbre.

4. Définissez la méthode masse() qui renvoie la somme des noeuds de l'arbre, lorsque ces noeuds sont des nombres.

5. Afin d'effectuer des tests plus nombreux, vous allez programmer une méthode qui permette de générer aléatoirement un arbre binaire dont les noeuds seront des entiers.

   Algorithme

   Si l'arbre est vide, alors la racine prend pour valeur un entier aléatoire. Sinon, on « tire à pile ou face ».

   • Dans le premier cas, on descend dans le fils gauche (quitte à le créer) et on recommence la procédure.
   • Dans le second cas, on descend dans le fils droit...

   a. Complétez la définition de la méthode insere_alea() à l'aide de l'algorithme décrit ci-dessus.

   def insere_alea(self, mini, maxi):
       """
       Sortie: None - Insère un entier généré aléatoirement entre les entiers mini et maxi
               Ou bien le noeud est vide et on place l'entier
               Ou bien on tire à "pile ou face" et on va dans le fils gauche
               (ou dans le fils droit selon le résultat) pour insérer en créant
               un arbre vide si besoin
       """
   

   b. Complétez la définition de la méthode remplir_alea() en respectant ses spécifications.

   def remplir_alea(self, nb_noeuds, mini, maxi):
       """
       Sortie: None - Insère nb_noeud valeurs entières dans l'arbre
               Ces valeurs sont générées aléatoirement entre mini et maxi
       """
   

6. Programmez les méthodes suivantes qui renvoient des informations sur la nature de l'arbre binaire :

   a. est_degenere() qui renvoie True si l'arbre binaire est dégénéré (chaque noeud père a un unique fils).
   b. est_equilibre() qui renvoie True si l'arbre binaire est équilibré (hauteur minimale par rapport à la taille).
   c. est_strict() qui renvoie True si l'arbre binaire est strict (chaque noeud père a exactement deux fil).
   d. est_complet() qui renvoie True si l'arbre binaire est complet (arbre à la fois strict et équilibré).

7. Programmez les méthodes suivantes :

   a. feuilles() qui renvoie le tableau (éventuellement vide) des valeurs des feuilles de l'arbre binaire ;
   b. __contains__() qui renvoie True l'élément passé en paramètre est une valeur de nœud dans l'arbre, qui renvoie False sinon ;
   c. profondeur() qui renvoie la profondeur dans l'arbre de l'élément passé en paramètre, qui renvoie -1 si cet élément n'est pas dans l'arbre ;
   d. noeud_prof() qui renvoie le tableau (éventuellement vide) des valeurs des nœuds de l'arbre de profondeur p, où p est le paramètre de cette méthode ;
   e. copie() qui renvoie une copie de l'arbre sur lequel s'applique cette méthode ;
   f. vider() qui vide tous les nœuds de l'arbre binaire jusqu'à ce que cet arbre soit vide.