Aller au contenu

Implémentation des Arbres binaires en Poo

Python ne propose pas de façon native l’implémentation des arbres binaires.

On va utiliser la POO pour créer une classe AB (pour Arbre Binaire), en utilisant le caractère récursif d'un arbre: une racine, et éventuellement un sous-arbre gauche et un sous-arbre droit.

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class AB():
    def __init__(self, racine=None):
        self.racine = racine
        if self.racine is not None:
            self.gauche = AB()
            self.droit = AB()
    def affiche(self, indent = 0):
        s = ' '*2*indent + '|_' + str(self.racine) + '\n'
        if not self.gauche.est_vide():
            s += self.gauche.affiche(indent + 1)
        if self.gauche.est_vide() and not self.droit.est_vide():
            s += ' '*(2*indent+2) + '|' + '_' + 'None' + '\n'     

        if not self.droit.est_vide():
            s += self.droit.affiche(indent + 1)
        if self.droit.est_vide() and not self.gauche.est_vide():
            s += ' '*(2*indent+2) + '|' + '_' + 'None' + '\n'  
        return s

    def __repr__(self):
        return self.affiche(0)

On peut alors créer l'arbre ci-après de cette manière:

🐍 Script Python
1
2
3
4
5
6
7
a = AB(4)
a.gauche = AB(3)
a.droit = AB(1)
a.droit.gauche = AB(2)
a.droit.droit = AB(7)
a.gauche.gauche = AB(6)
a.droit.droit.gauche = AB(9)

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)

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...

Taille et hauteur

  1. Écrire une méthode renvoyant la taille d'un arbre binaire.
  2. Écrire une méthode renvoyant la hauteur d'un arbre binaire.
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def taille(self):
    if self.est_vide():
        return 0
    else:
        return 1 + self.gauche.taille() + self.droit.taille()

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

```

DFS

É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).

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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=" ")

recherche d'une valeur

É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é:

🐍 Script Python
1
2
3
4
5
6
7
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)