Taille et hauteur d'un arbre binaire - Sujet 17 - EP NSI 2025

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

Énoncé du problème

Exercice 1

Exercice 2