▶ TP Arbres binaires

Objectif

Dans ce TP, il s'agit d'utiliser l'implémentation POO d'un arbre binaire et d'implémenter des fonctions:

• de calcul de taille
• de calcul de hauteur
• de parcours (largeur, préfixe, infixe, postfixe)

Reprendre le fichier arbre_binaire.py et compléter au fur et à mesure la classe AB.

Stratégie

Dès que possible, il s'agit d'exploiter le caractère récursif de la structure d'arbre pour écrire les méthodes suivantes...

Exercice 1: Taille et hauteur

ÉnoncéCorrection

1. Écrire une méthode renvoyant la taille d'un arbre binaire.

2. Écrire une méthode renvoyant la hauteur d'un arbre binaire.

   Indice en bas de votre écran: la fonction max est autorisée.

#1.
def taille(self):
    if self.est_vide():
        return 0
    else:
        return 1 + self.gauche.taille() + self.droit.taille()
#2.
def hauteur(self):
    if self.est_vide():
        return 0
    else:
        return 1 + max(self.gauche.hauteur(), self.droit.hauteur())

Exercice 2: BFS

ÉnoncéCorrection

Écrire une méthode qui effectue un parcours en largeur d'abord de l'arbre et qui renvoit l'ordre de parcours des nœuds (sous forme d'une liste par exemple).

Rappel: l'algorithme (donné à la page précédente) nécessite l'utilisation d'une file. Pour cela vous pouvez:

• utiliser «votre» objet File créé plus tôt dans l'année;
• utiliser une simple liste de Python (bof bof);
• utiliser la classe Queue du module queue, qui possède les méthodes empty, put (pour enfiler) et get (pour défiler).

Exercice 3 : DFS

ÉnoncéCorrection

Écrire les méthodes prefixe, infixe et postfixe parcourant l'arbre en profondeur d'abord selon les algorithmes correspondants (page précédente). Le traitement de la racine consistera en un affichage (print).

def prefixe(self):
    if not self.est_vide():
        print(self.racine, end=)
        self.gauche.prefixe()
        self.droit.prefixe()

def infixe(self):
    if not self.est_vide():
        self.gauche.infixe()
        print(self.racine, end=)
        self.droit.infixe()

def postfixe(self):
    if not self.est_vide():            
        self.gauche.postfixe()
        self.droit.postfixe()
        print(self.racine, end=)

Exercice 4 : recherche d'une valeur

ÉnoncéCorrection

Écrire une méthode permettant de déterminer si un arbre contient une valeur donnée. La méthode renverra un booléen selon le résultat de la recherche.

Avec un parcours préfixe adapté:

def recherche(self, valeur):
    if self.est_vide():
        return False
    elif self.racine == valeur:
        return True
    else:
        return self.gauche.recherche(valeur) or self.droit.recherche(valeur)

Avec un parcours en largeur adapté:

def recherche_bfs(self, valeur) -> bool:
    file = queue.Queue()
    file.put(self) 
    while not file.empty():
        t = file.get()        
        if not t.est_vide():
            if t.racine == valeur:
                return True 
            file.put(t.gauche)
            file.put(t.droit)               
    return False