Interface et implémentations (Bac 🎯)

Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

• le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen
• le manuel NSI chez Hachette sous la direction de Michel Beaudouin Lafon
• l'article sur les arbres en NSI de Sébastien Hoarau
• le cours de mon collègue Pierre Duclosson
• le cours de Gilles Lassus
• le cours de Franck Chambon

🔖 Synthèse de ce qu'il faut retenir pour le bac

Une classe Noeud

Point de cours 7

Un arbre binaire est un ensemble fini de noeuds donc il faut d'abord représenter un noeud.

Un noeud est constitué d'un élément, d'un fils gauche et d'un fils droit donc on peut représenter un noeud par un objet d'une classe Noeud avec trois attributs : element, gauche et droite.

On choisit de représenter l'absence de noeud par la valeur spéciale None

🐍 Script Python

class Noeud:
    """Noeud pour arbre binaire"""

    def __init__(self, g, e, d):
        self.gauche = g # lien vers fils gauche g éventuellement vide (None)
        self.element = e # élément e stocké dans le noeud
        self.droit = d # lien vers fils droit d éventuellement vide (None)

Du noeud à l'arbre binaire

Cette classe Noeud permet déjà de construire des arbres binaires. Par exemple l'expression :

🐍 Script Python

Noeud(Noeud(None, 'A', None), 'R', Noeud(Noeud(None, 'B', None), 'R', Noeud(None, 'E', None)))

permet de construire l'arbre binaire ci-dessous :

Cas de l'arbre binaire vide

Attention cette classe Noeud ne permet pas de représenter l'arbre binaire vide et ne suffit pas pour implémenter en paradigme objet (POO) un type abstrait arbre binaire.

Exercice 4

💻 Saisir ses réponses sur Capytale

énoncésolution

1. Représenter le noeud construit par l'instruction suivante :

   🐍 Script Python

   ac = Noeud(None, 'C', None)
   

2. On complète le code précédent. Représenter les deux arbres binaires construits par la séquence d'instructions :

   🐍 Script Python

   ab = Noeud(ac, 'B', None)
   aa = Noeud(None, 'A', ab)
   

3. Donner une séquence d'instructions permettant de construire avec la classe Noeud l'arbre binaire ci-dessous.

   

1. Arbre représentant ac = Noeud(None, 'C', None)

   

2. Deux arbres :

   • arbre représentant ab = Noeud(ac, 'B', None)

     

   • arbre représentant ab = Noeud(ac, 'B', None)

     

3. Code Python :

   🐍 Script Python

   Noeud(Noeud(Noeud(None, -1, None), 7, Noeud(None, 9, None)), 
           5,
           Noeud(None, 3, Noeud(None, 2, None))
       )
   

Interface et implémentation d'arbre binaire immuable

Point de cours 8

Pour le type abstrait arbre binaire on a besoin de représenter :

• l'arbre binaire vide : on peut choisir une valeur spéciale comme None
• un noeud par exemple avec un objet de la classe Noeud définie précédemment.

On peut alors définir un ensemble de fonctions constituant une interface fonctionnelle minimale pour le type abstrait arbre binaire. Le paramètre arbre désigne un arbre qui est de type Noeud s'il est non vide ou qui vaut None sinon.

Fonction	Signature	Description
arbre_vide	arbre_vide()	Renvoie un arbre vide représenté par None
est_vide	est_vide(arbre)	Renvoie un booléen indiquant si arbre est vide
element_racine	element_racine(arbre)	Renvoie l'élément à la racine de l'arbre s'il est non vide
gauche	gauche(arbre)	Renvoie le sous-arbre fils gauche de l'arbre s'il est non vide
droit	droit(arbre)	Renvoie le sous-arbre fils droit de l'arbre s'il est non vide
creer_arbre	creer_arbre(g, e, d)	Renvoie un noeud constitué de l'élément e, du sous-arbre gauche g et du sous-arbre droit d

A partir de cette interface fonctionnelle, on peut donner une implémentation d'arbre binaire immuable c'est-à-dire que chaque fonction renvoie un nouvel arbre binaire et ne modifie jamais l'arbre binaire passé en paramètre :

Implémentation d'un type d'arbre binaire immuable

codeexemple

🐍 Script Python

def arbre_vide():
    """Renvoie un arbre vide représenté par None"""
    return None

def est_vide(arbre):
    """Teste si un arbre est vide, renvoie un booléen"""
    return arbre is None

def gauche(arbre):
    """Renvoie le sous-arbre fils gauche de arbre 
    Provoque une erreur si arbre est vide"""
    assert not est_vide(arbre), "Arbre vide"
    return arbre.gauche

def droit(arbre):
    """Renvoie le sous-arbre fils droit de arbre 
    Provoque une erreur si arbre est vide"""
    assert not est_vide(arbre), "Arbre vide"
    return arbre.droit

def element_racine(arbre):
    """Renvoie l'élément à la racine de arbre
    Provoque une erreur si arbre est vide"""
    assert not est_vide(arbre), "Arbre vide"
    return arbre.element

def creer_arbre(g, e, d):
    """Construit et renvoie l'arbre binaire dont la racine est constituée
    par le noeud d'élément e, g sous-arbre gauche et d sous-arbre droit"""
    return Noeud(g, e, d)

# extension de l'interface pour afficher un arbre
def afficher_arbre(arbre):
    """Affichage syntaxiquement correct d'un arbre :
    vide ou avec le constructeur de  Noeud"""
    if arbre is None:
        return repr(None)
    return f"Noeud({afficher_arbre(arbre.gauche)}, {repr(arbre.element)}, {afficher_arbre(arbre.droit)})"

On peut construire le même arbre binaire que dans l'exemple du point de cours 7 avec :

🐍 Script Python

Noeud(Noeud(None, 'A', None), 'R', Noeud(Noeud(None, 'B', None), 'R', Noeud(None, 'E', None)))

Avec l'interface la séquence d'instructions sera :

🐍 Script Python

ac = creer_arbre(None, 'C', None)
assert element_racine(ac) == 'C'
assert est_vide(droit(ac)) == True
ab = creer_arbre(ac, 'B', None)
assert gauche(ab) == ac
aa = creer_arbre(None, 'A', ab)
assert droit(aa) == ab

Exercice 5

💻 Saisir ses réponses sur Capytale

énoncésolution

Représenter l'arbre binaire construit dans la variable a à la fin de la séquence d'instructions ci-dessous :

🐍 Script Python

sag = creer_arbre(None, '4', None)
sad = creer_arbre(None, '5', None)
sad = creer_arbre(sag, '-', sad)
sag = creer_arbre(None, '3', None)
sag = creer_arbre(sag, '*', sad)

sag2 = creer_arbre(None, '12', None)
sad2 = creer_arbre(None, '7', None)
sad2 = creer_arbre(sag2, '+', sad2)
sag2 = creer_arbre(None, '5', None)
sad2 = creer_arbre(sag2, '*', sad2)

a = creer_arbre(sag, '+', sad2)

Implémentation d'arbre binaire mutable avec une interface objet (POO)

Exercice 6

💻 Saisir ses réponses sur Capytale

On donne ci-dessous une implémentation d'arbre binaire mutable basée sur la classe Noeud. L'unique attribut racine peut être lié :

• à la valeur None pour représenter un arbre vide
• ou à un objet de la classe Noeud pour représenter le noeud racine d'un arbre non vide

Ainsi on peut intégrer comme méthodes de la classe AB l'ensemble des fonctions de l'interface donnée dans le Point de cours 8 à l'exception de creer_arbre qui est remplacée par ajout_racine.

La méthode ajout_racine fait de cette classe un type mutable : elle permet de muter un arbre vide en lui ajoutant un noeud racine.

Cette méthode ajout_racine n'est pas limitée aux arbres vides. En descendant dans l'arbre avec les méthodes gauche et droit on peut ajouter des enfants absents aux noeuds de l'arbre. La mutabilité est limitée, on ne peut pas modifier la valeur d'un noeud ou supprimer un noeud.

###

Lancer Télécharger Téléverser Recharger Sauvegarder

class Noeud:bksl-nl """Noeud pour arbre binaire"""bksl-nl bksl-nl def py-undpy-undinitpy-undpy-und(self, g, e, d):bksl-nl self.gauche = g # lien vers fils gauche g éventuellement vide (None)bksl-nl self.element = e # élément e stocké dans le noeudbksl-nl self.droit = d # lien vers fils droit d éventuellement vide (None)bksl-nlbksl-nlbksl-nlclass AB:bksl-nl """Classe d'arbre binaire mutable"""bksl-nl bksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl """Constructeur, self.racine pointe vers None si arbre videbksl-nl ou le noeud racine"""bksl-nl self.racine = Nonebksl-nlbksl-nl def estpy-undvide(self):bksl-nl """Teste si l'arbre est vide, renvoie un booléen"""bksl-nl return self.racine is Nonebksl-nlbksl-nl def droit(self):bksl-nl """Renvoie le sous-arbre (de type Arbre) fils droit de l'arbre bksl-nl Provoque une erreur si arbre est vide"""bksl-nl assert not self.estpy-undvide()bksl-nl return self.racine.droitbksl-nl bksl-nl def gauche(self):bksl-nl """Renvoie le sous-arbre (de type Arbre) fils gauche de l'arbre bksl-nl Provoque une erreur si arbre est vide"""bksl-nl assert not self.estpy-undvide()bksl-nl return self.racine.gauchebksl-nl bksl-nl def ajoutpy-undracine(self, element):bksl-nl """Ajoute un noeud stockant element à la racine de l'arbrebksl-nl Provoque une erreur si arbre est non vide"""bksl-nl assert self.estpy-undvide()bksl-nl self.racine = Noeud(AB(), element, AB())bksl-nl bksl-nl def elementpy-undracine(self):bksl-nl """Renvoie l'élément stocké dans le noeud racine de l'arbre bksl-nl Provoque une erreur si arbre est vide"""bksl-nl assert not self.estpy-undvide()bksl-nl return self.racine.elementbksl-nl bksl-nl # extension de l'interfacebksl-nl bksl-nl def extremepy-undgauche(self):bksl-nl """Renvoie None si l'arbre est videbksl-nl ou la valeur du noeud atteinte en descendant toujours dans le bksl-nl sous-arbre gauchebksl-nl """bksl-nl # à compléterbksl-nl ...bksl-nl bksl-nlbksl-nldef test():bksl-nl a = AB()bksl-nl a.ajoutpy-undracine('+')bksl-nl a.gauche().ajoutpy-undracine('py-str')bksl-nl a.gauche().gauche().ajoutpy-undracine(3)bksl-nl a.gauche().droit().ajoutpy-undracine('-')bksl-nl a.gauche().droit().gauche().ajoutpy-undracine(4)bksl-nl a.gauche().droit().droit().ajoutpy-undracine(5)bksl-nl a.droit().ajoutpy-undracine('py-str')bksl-nl a.droit().gauche().ajoutpy-undracine(5)bksl-nl a.droit().droit().ajoutpy-undracine('+')bksl-nl a.droit().droit().gauche().ajoutpy-undracine(12)bksl-nl a.droit().droit().droit().ajoutpy-undracine(7)bksl-nl assert a.extremepy-undgauche() == 3bksl-nl assert a.elementpy-undracine() == '+'bksl-nl assert a.gauche().elementpy-undracine() == 'py-str'bksl-nl assert a.gauche().droit().droit().elementpy-undracine() == 5bksl-nl print("tests réussis")bksl-nl

Question 1

énoncésolution

Écrire un code permettant de construire l'arbre binaire représenté ci-dessous :

🐍 Script Python

a = AB()
a.ajout_racine(5)
a.gauche().ajout_racine(7)
a.gauche().gauche().ajout_racine(-1)
a.gauche().droit().ajout_racine(9)
a.droit().ajout_racine(3)
a.droit().droit().ajout_racine(2)

Question 2

énoncésolution

Complétez la méthode extreme_gauche pour qu'elle renvoie la valeur de l'élément du noeud atteint en descendant depuis la racine toujours dans le sous-arbre gauche. La fonction doit renvoyer None si l'arbre est vide.

🐍 Script Python

def extreme_gauche(self):
    if self.est_vide(): # cas de l'arbre vide
        return None
    if self.gauche().est_vide(): # on ne peut plus descendre à gauche
        return self.element_racine()
    return self.gauche().extreme_gauche()