C5.4 : Implémentation des arbres à l'aide de classes

Implémentation des arbre binaires

Code de la classe

On choisit d'implémenter les arbres binaires à l'aide de la classe Arbre ci-dessous.

class Arbre:
    def __init__(self, etiquette):
        self.__valeur = etiquette
        self.__gauche = None
        self.__droit = None

    def get_v(self):
        return self.__valeur

    def get_g(self):
        return self.__gauche

    def get_d(self):
        return self.__droit

    def est_feuille(self):
        return not self.__gauche and not self.__droit

    def greffe_gauche(self, arbre_greffe):
        self.__gauche = arbre_greffe

    def greffe_droit(self, arbre_greffe):
        self.__droit = arbre_greffe

Avec cette classe, l'arbre ci-contre se construit avec les lignes suivantes :

arb = Arbre("S")
n = Arbre("N")
i = Arbre("I")
arb.greffe_gauche(n)
arb.greffe_droit(i)

Q1 : Écrire le code qui permet de construire l'arbre ci-dessous :

Parcours infixe

Q2 : Écrire une fonction récursive qui permet de placer toutes les étiquettes d'un arbre dans une liste avec un parcours infixe. Tester votre fonction sur l'arbre précédent.

Implémentation des arbres binaires de recherche

Q3 : Sur le modèle de la classe Arbre ci-dessus, écrire une classe ABR dont l'interface est décrite ci-dessous.