Implémentation en Python des algorithmes sur les arbres binaires

Le but est d'implémenter en Python les algorithmes sur les arbres binaires précédemment étudiés. Il sera donc sans doute nécessaire de reprendre ce qui a été vu sur la structure de données "arbre".

Comme nous l'avons déjà dit, Python ne propose pas de structure de données permettant d'implémenter directement les arbres binaires.
Il va donc être nécessaire de créer cette structure.
Pour programmer ce type de structure, nous allons utiliser le paradigme objet.

Pour cela nouys allons utiliser la vidéo du cours précédent.

Activité 1

A partir de la vidéo, créer la classe vous permettant d'implémenter un arbre binaire.
Tester votre taravail avec l'exemple fournis dans la vidéo.

Correction ?

...CORRECTION...


class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur
        self.enfant_gauche = None
        self.enfant_droit = None

    def insert_gauche(self, valeur):
        if self.enfant_gauche == None:
            self.enfant_gauche = Noeud(valeur)
        else:
            new_node = Noeud(valeur)
            new_node.enfant_gauche = self.enfant_gauche
            self.enfant_gauche = new_node

    def insert_droit(self, valeur):
        if self.enfant_droit == None:
            self.enfant_droit = Noeud(valeur)
        else:
            new_node = Noeud(valeur)
            new_node.enfant_droit = self.enfant_droit
            self.enfant_droit = new_node

   def get_valeur(self):
        return self.valeur

   def get_gauche(self):
        return self.enfant_gauche

   def get_droit(self):
        return self.enfant_droit

Activité 2

Étudiez attentivement la classe "Noeud" (méthodes et attributs).

Voici un exemple d'utilisation de cette classe pour construire un arbre binaire :

Soit l'arbre binaire suivant :

Arbre 1

On veut construire cet arbre à l'aide de la classe "Noeud".
Ecrire les commandes permettant de faire cette construction

Correction ?

...CORRECTION...


######début de la construction de l'arbre binaire###########

racine = ArbreBinaire('A')
racine.insert_gauche('B')
racine.insert_droit('F')

b_node = racine.get_gauche()
b_node.insert_gauche('C')
b_node.insert_droit('D')

f_node = racine.get_droit()
f_node.insert_gauche('G')
f_node.insert_droit('H')

c_node = b_node.get_gauche()
c_node.insert_droit('E')

g_node = f_node.get_gauche()
g_node.insert_gauche('I')

h_node = f_node.get_droit()
h_node.insert_droit('J')

######fin de la construction de l'arbre binaire###########

Activité 3

Étudiez attentivement la correction ci-dessus afin de comprendre le principe de "construction d'un arbre binaire"

Il est possible d'afficher un arbre binaire dans la console Python, pour cela, nous allons utiliser la fonction "affiche" définie à l'activité 1.


def affiche(arbre):
   if arbre != None:
      return (arbre.get_valeur(),affiche(arbre.get_gauche()),affiche(arbre.get_droit()))

Cette fonction renvoie une série de tuples de la forme (valeur,arbre_gauche, arbre_droite), comme "arbre_gauche" et "arbre_droite" seront eux-mêmes affichés sous forme de tuples, on aura donc un affichage qui ressemblera à : (valeur,(valeur_gauche,arbre_gauche_gauche,arbre_gauche_droite),(valeur_droite,arbre_droite_gauche,arbre_droite_droite)), mais comme "arbre_gauche_gauche" sera lui-même représenté par un tuple... Nous allons donc avoir des tuples qui contiendront des tuples qui eux-mêmes contiendront des tuples...

Pour l'arbre binaire défini ci-dessus, on aura :


('A', ('B', ('C', None, ('E', None, None)), ('D', None, None)), ('F', ('G', ('I', None, None), None), ('H', None, ('J', None, None))))

Vérifiez que "affiche(racine)" renvoie bien :


('A', ('B', ('C', None, ('E', None, None)), ('D', None, None)), ('F', ('G', ('I', None, None), None), ('H', None, ('J', None, None))))

N.B : la fonction "affiche" n'a pas une importance fondamentale, elle sert uniquement à vérifier que les arbres programmés sont bien corrects.

Activité 4

Programmez à l'aide de la classe "Noeud", l'arbre binaire suivant :

Arbre 2

Vérifiez votre programme à l'aide de la fonction "affiche"

Activité 5

Programmez à l'aide de la classe "Noeud", l'arbre binaire définie dans la vidéo :

Utiliser votre fonction sur cet arbre.

Vous allez maintenant pouvoir commencer à travailler sur l'implémentation des algorithmes sur les arbres binaires :

Activité 6

Programmez la fonction "hauteur" qui prend un arbre binaire T en paramètre et renvoie la hauteur de T.
Ci-dessous algorithme correspondant :


VARIABLE
T : arbre
x : noeud

DEBUT
HAUTEUR(T) :
  si T ≠ NIL :
    x ← T.racine
    renvoyer 1 + max(HAUTEUR(x.gauche), HAUTEUR(x.droit))
  sinon :
    renvoyer 0
  fin si
FIN

N.B. la fonction max renvoie la plus grande valeur des 2 valeurs passées en paramètre (exemple : max(5,6) renvoie 6)

Cet algorithme est loin d'être simple, n'hésitez pas à écrire votre raisonnement sur une feuille de brouillon.

Testez votre fonction en utilisant l'arbre vu plus haut (schéma "Arbre 1") et sur l'arbre de la vidéo.

Activité 7

Programmez la fonction "taille" qui prend un arbre binaire T en paramètre et renvoie la taille de T,
Ci-dssous algorithme correspondant :


VARIABLE
T : arbre
x : noeud

DEBUT
TAILLE(T) :
  si T ≠ NIL :
    x ← T.racine
    renvoyer 1 + TAILLE(x.gauche) + TAILLE(x.droit)
  sinon :
    renvoyer 0
  fin si
FIN

Testez votre fonction en utilisant l'arbre vu plus haut (schéma "Arbre 1") et sur l'arbre de la vidéo.