Exercice 1

EXERCICE 1 (10 points)

Un arbre binaire est soit vide, représenté en Python par la valeur None, soit un nœud, contenant une étiquette et deux sous-arbres gauche et droit et représenté par une instance de la classe Noeud donnée ci-dessous.

class Noeud:
    def __init__(self, etiquette, gauche, droit):
        self.v = etiquette
        self.gauche = gauche
        self.droit = droit

flowchart TD
    n1((1)) --> n4((4))
    n1 --> n0((0))
    n0 --> n7((7))

[Figure : schéma d’un arbre binaire dont la racine porte l’étiquette 1 ; son fils gauche est une feuille d’étiquette 4 ; son fils droit porte l’étiquette 0 et possède un unique fils droit, feuille d’étiquette 7.]

L’arbre ci-dessus sera donc implémenté de la manière suivante :

a = Noeud(1, Noeud(4, None, None),
             Noeud(0, None,
                      Noeud(7, None, None)))

Écrire une fonction récursive taille prenant en paramètre un arbre a et qui renvoie la taille de l’arbre que cette instance implémente.

Écrire de même une fonction récursive hauteur prenant en paramètre un arbre a et qui renvoie la hauteur de l’arbre que cette instance implémente.

On considère que la hauteur d’un arbre vide est -1 et la taille d’un arbre vide est 0.

Exemples :

>>> hauteur(a)
2
>>> taille(a)
4
>>> hauteur(None)
-1
>>> taille(None)
0
>>> hauteur(Noeud(1, None, None))
0
>>> taille(Noeud(1, None, None))
1

Exercice 2

EXERCICE 2 (10 points)

On rappelle que les tableaux sont représentés par des listes en Python du type list.

Le but de cet exercice est d’écrire une fonction ajoute qui prend en paramètres trois arguments indice, element et tab et renvoie un tableau tab_ins dans lequel les éléments sont ceux du tableau tab avec, en plus, l’élément element à l’indice indice.

On considère que les variables indice et element sont des entiers positifs et que les éléments de tab sont également des entiers.

En réalisant cette insertion, Les éléments du tableau tab dont les indices sont supérieurs ou égaux à indice apparaissent décalés vers la droite dans le tableau tab_ins.

Si indice est égal au nombre d’éléments du tableau tab, l’élément element est ajouté dans tab_ins après tous les éléments du tableau tab.

Exemples :

>>> ajoute(1, 4, [7, 8, 9])
[7, 4, 8, 9]
>>> ajoute(3, 4, [7, 8, 9])
[7, 8, 9, 4]
>>> ajoute(0, 4, [7, 8, 9])
[4, 7, 8, 9]

Compléter et tester le code ci-dessous :

def ajoute(indice, element, tab):
    '''Renvoie un nouveau tableau obtenu en insérant
    element à l'indice indice dans le tableau tab.'''
    nbre_elts = len(tab)
    tab_ins = [0] * (nbre_elts + 1)
    for i in range(indice):
        tab_ins[i] = ...
    tab_ins[...] = ...
    for i in range(indice + 1, nbre_elts + 1):
        tab_ins[i] = ...
    return tab_ins

Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.

Exercice 1

Contraintes :

• a est soit None (arbre vide), soit une instance de Noeud
• le nombre de nœuds de l’arbre vérifie 0 <= n <= 10^3
• la hauteur de l’arbre vérifie -1 <= h <= 100
• chaque étiquette est un entier avec -10^9 <= etiquette <= 10^9
• pour un nœud, gauche et droit sont chacun soit None, soit une instance de Noeud
• taille(None) vaut 0 et hauteur(None) vaut -1

Exercice 2

Contraintes :

• tab est une liste d’entiers avec 0 <= len(tab) <= 10^3
• -10^9 <= tab[i] <= 10^9
• element est un entier avec 0 <= element <= 10^9
• indice est un entier avec 0 <= indice <= len(tab) (bornes incluses)
• tab n’est pas modifié : la fonction renvoie un nouveau tableau de longueur len(tab) + 1

Solution

Exercice 1 - taille et hauteur d’un arbre binaire

L’idée. Un arbre est soit vide (None), soit un noeud avec deux sous-arbres. C’est exactement la forme d’une fonction récursive : on traite d’abord le cas vide, puis on répond pour un noeud en supposant qu’on sait déjà répondre pour ses deux sous-arbres.

Pour la taille : un arbre vide contient 0 noeud ; sinon on compte 1 pour la racine, plus la taille du sous-arbre gauche, plus celle du sous-arbre droit.

Pour la hauteur : un arbre vide a pour hauteur -1 ; sinon la hauteur vaut 1 de plus que la plus grande des hauteurs des deux sous-arbres. Le choix de -1 pour l’arbre vide n’est pas un hasard : il fait tomber juste le cas de la feuille, dont les deux sous-arbres sont vides, donc 1 + (-1) = 0.

Un petit exemple. Avec a = Noeud(1, Noeud(4, None, None), Noeud(0, None, Noeud(7, None, None))) : la branche gauche est une feuille, de hauteur 0 ; la branche droite est un noeud dont le fils droit est une feuille, donc de hauteur 1. La hauteur de a vaut 1 + max(0, 1) = 2, et sa taille vaut 1 + 1 + 2 = 4.

class Noeud:
    def __init__(self, etiquette, gauche, droit):
        self.v = etiquette
        self.gauche = gauche
        self.droit = droit


def taille(a):
    # Un arbre vide ne contient aucun noeud : c'est le cas qui arrête la récursion
    if a is None:
        return 0
    return 1 + taille(a.gauche) + taille(a.droit)


def hauteur(a):
    # La hauteur d'un arbre vide vaut -1, ce qui donne bien 0 pour une feuille
    if a is None:
        return -1
    hauteur_gauche = hauteur(a.gauche)
    hauteur_droite = hauteur(a.droit)
    if hauteur_gauche > hauteur_droite:
        return 1 + hauteur_gauche
    return 1 + hauteur_droite

Explications. Dans les deux fonctions, le if a is None est le cas d’arrêt : sans lui, les appels ne s’arrêteraient jamais. Dans hauteur, hauteur_gauche et hauteur_droite retiennent les deux réponses des sous-arbres pour ne pas les recalculer, puis on garde la plus grande avant d’ajouter 1 pour la racine. On écrit a is None plutôt que a == None : c’est la manière usuelle de tester qu’un arbre est vide.

Exercice 2 - insérer un élément dans un tableau

L’idée. On ne modifie pas tab : on remplit case par case un nouveau tableau tab_ins, plus long d’une case. Le code donné par le sujet dit déjà dans quel ordre : d’abord les cases avant indice, qui sont recopiées telles quelles ; ensuite la case indice, qui reçoit element ; enfin les cases suivantes, qui reprennent les valeurs de tab mais décalées d’un cran vers la droite.

C’est ce décalage qui explique le - 1 : la case i de tab_ins contient la valeur qui était à la case i - 1 de tab, puisqu’une case a été insérée avant elle.

Un petit exemple. Pour ajoute(1, 4, [7, 8, 9]) : tab_ins[0] = tab[0] = 7, puis tab_ins[1] = 4, puis tab_ins[2] = tab[1] = 8 et tab_ins[3] = tab[2] = 9, soit [7, 4, 8, 9].

def ajoute(indice, element, tab):
    '''Renvoie un nouveau tableau obtenu en insérant
    element à l'indice indice dans le tableau tab.'''
    nbre_elts = len(tab)
    tab_ins = [0] * (nbre_elts + 1)
    for i in range(indice):
        tab_ins[i] = tab[i]
    tab_ins[indice] = element
    for i in range(indice + 1, nbre_elts + 1):
        # À partir de l'insertion, chaque valeur de tab glisse d'une case vers la droite
        tab_ins[i] = tab[i - 1]
    return tab_ins

Explications. nbre_elts est la longueur de tab, et tab_ins est créé tout de suite à la bonne taille, nbre_elts + 1. La première boucle s’arrête à indice exclu : la case indice est justement celle qu’on remplit ensuite avec element. La seconde boucle va jusqu’à nbre_elts inclus, c’est-à-dire la dernière case de tab_ins.

Les deux cas limites fonctionnent sans traitement particulier : si indice vaut 0, la première boucle ne tourne pas et element se retrouve en tête ; si indice vaut len(tab), c’est la seconde boucle qui ne tourne pas et element se retrouve en queue.