Rappels sur les assertions en Python.¶

L'instruction assert permet de vérifier qu'une instruction Python renvoie bien le bon résultat

Par exemple si je souhaite vérifier que ma fonction somme renvoie bien le bon résultat :

def somme(a, b):
    return a + b

Je peux ajouter ces assertions :

assert somme(2, 3) == 5
assert somme(-2, 3) == 1

Si l'assertion est vérifiée alors aucune erreur n'est retournée, sinon une erreur est retournée :

Traceback (most recent call last):
  File "<input>", line 4, in <module>
AssertionError

Exercice 1 (10 points)¶

Pour cet exercice nous allons utiliser l'arbre (arbre 1) représenté ci-dessous.

Nous pouvons représenter un arbre binaire en Python de différentes manière. Nous allons commencer par représenter l'arbre binaire ci-dessus en utilisant des tuples.

1.1 Tuples¶

Un arbre vide est représenté par un tuple vide. Chaque nœud est un tuple de 3 valeurs contenant dans l’ordre :

L’étiquette du nœud ;
Le sous-arbre gauche (un tuple éventuellement vide) ;
Le sous-arbre droit (un tuple éventuellement vide).

Le cours de première sur les tuples (et surtout les listes): https://snt-nsi.net/nsi_premiere/types_construits/sequences/

Par exemple on peut représenter cet arbre:

Par ces tuples:

arbre = ( 4, (2, (1, (), ()), (3, (), ()) ), (7, (), ()) )

- Représentez l'arbre 1 sous forme de tuples.
- Affichez le sous arbre gauche et le sous arbre droit.

On rappelle que tuple_1[0] permet de récupérer le premier élément du tuple tuple_1.

1.2 Classes¶

On peut également représenter un arbre binaire par un ensemble de classes Noeuds.

En utilisant cette classe :

class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur
        self.gauche = None
        self.droite = None

Représentez l'arbre 1 en utilisant des classes.

Exercice 2 (4 points)¶

Complétez les fonctions taille et hauteur ci-dessous :

def taille(COMPLETER_ICI):
    if COMPLETER_ICI is None:
        return COMPLETER_ICI
    else:
        return 1 + taille(COMPLETER_ICI) + taille(COMPLETER_ICI)

def hauteur(COMPLETER_ICI):
    if COMPLETER_ICI is None:
        return COMPLETER_ICI
    else:
        return 1 + max(hauteur(COMPLETER_ICI), hauteur(COMPLETER_ICI))

En ajoutant des assertions vous allez utiliser la classe de l'exercice 1 pour vérifier les cas suivants :

Si l'arbre est vide alors la hauteur de l'arbre doit être de -1 et la taille de 0.
Créez un arbre contenant 3 noeuds. Vérifiez que la taille de l'arbre est bien correcte.

Exercice 3 (6 points)¶

En utilisant les pseudo-codes suivant:

parcours_prefixe(Arbre A) :
    visiter(A)
    Si nonVide(gauche(A))
          parcours_prefixe(gauche(A))
    Si nonVide (droite(A))
          parcours_prefixe(droite(A))

parcours_infixe(Arbre A) :
    Si nonVide(gauche(A))
       parcours_infixe(gauche(A))
    visiter(A)
    Si nonVide(droite(A))
       parcours_infixe(droite(A))

parcours_postfixe(Arbre A) :
    Si nonVide(gauche(A))
       parcours_postfixe(gauche(A))
    Si nonVide(droite(A))
       parcours_postfixe(droite(A))
    visiter(A)

Implémenter en Python les parcours prefixe, infixe et postfixe de l'arbre 1
Vérifier bien que le résultat est correct (sinon vous aurez zéro à cet exercice)