Solution de Taille d'un arbre binaire - Sujet 47 - EP NSI 2025

Résoudre ce problème
Moyen Officiel
Python (3.14.0)

Énoncé du problème

Exercice 1

EXERCICE 1 (10 points)

Dans cet exercice, un arbre binaire de caractères non vide est stocké sous la forme d’un dictionnaire où les clefs sont les caractères des nœuds de l’arbre et les valeurs, pour chaque clef, la liste des caractères des fils gauche et droit du nœud. On utilise la valeur '' pour représenter un fils vide.

Par exemple, l’arbre

flowchart TD
    F((F)) -->|gauche| B((B))
    F -->|droit| G((G))
    B -->|gauche| A((A))
    B -->|droit| D((D))
    D -->|gauche| C((C))
    D -->|droit| E((E))
    G -->|droit| I((I))
    I -->|droit| H((H))

[Figure : arbre binaire dont les nœuds sont représentés par des cercles étiquetés. La racine est F. Le fils gauche de F est B, son fils droit est G. B a pour fils gauche A et pour fils droit D. D a pour fils gauche C et pour fils droit E. G a pour fils droit I (pas de fils gauche). I a pour fils droit H (pas de fils gauche).]

est stocké dans

a = {'F':['B','G'], 'B':['A','D'], 'A':['',''], 'D':['C','E'], \
     'C':['',''], 'E':['',''], 'G':['','I'], 'I':['','H'], \
     'H':['','']}

Écrire une fonction récursive taille prenant en paramètres un arbre binaire arbre non vide sous la forme d’un dictionnaire et un caractère lettre qui est la valeur du sommet de l’arbre, et qui renvoie la taille de l’arbre à savoir le nombre total de nœuds.

On observe que, par exemple, arbre[lettre][0], respectivement arbre[lettre][1], permet d’atteindre la clé du sous-arbre gauche, respectivement droit, de l’arbre arbre de sommet lettre.

Exemples :

>>> taille(a, 'F')
9
>>> taille(a, 'B')
5
>>> taille(a, 'I')
2

Exercice 2

EXERCICE 2 (10 points)

On considère l’algorithme de tri de tableau suivant : à chaque étape, on parcourt le sous-tableau des éléments non rangés et on place le plus petit élément en première position de ce sous-tableau.

Exemple avec le tableau : t = [41, 55, 21, 18, 12, 6, 25]

  • Étape 1 : on parcourt tous les éléments du tableau, on permute le plus petit élément avec le premier.

    Le tableau devient t = [6, 55, 21, 18, 12, 41, 25]

  • Étape 2 : on parcourt tous les éléments sauf le premier, on permute le plus petit élément trouvé avec le second.

    Le tableau devient : t = [6, 12, 21, 18, 55, 41, 25]

Et ainsi de suite.

Le programme ci-dessous implémente cet algorithme.

def echange(tab, i, j):
    '''Echange les éléments d'indice i et j dans le tableau tab.'''
    temp = ...
    tab[i] = ...
    tab[j] = ...

def tri_selection(tab):
    '''Trie le tableau tab dans l'ordre croissant
    par la méthode du tri par sélection.'''
    N = len(tab)
    for k in range(...):
        imin = ...
        for i in range(..., N):
            if tab[i] < ...:
                imin = i
        echange(tab, ..., ...)

Compléter ce code de façon à obtenir :

>>> tab = [41, 55, 21, 18, 12, 6, 25]
>>> tri_selection(tab)
>>> tab
[6, 12, 18, 21, 25, 41, 55]

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

Exercice 1

Contraintes :

  • arbre est un dictionnaire non vide : 1 <= len(arbre) <= 100
  • chaque clé de arbre est une chaîne d’un seul caractère, et toutes les clés sont distinctes
  • chaque valeur de arbre est une liste de deux chaînes [fils_gauche, fils_droit]
  • la chaîne vide '' représente un fils absent ; '' n’est jamais une clé de arbre
  • toute chaîne non vide figurant comme fils est une clé de arbre
  • lettre est une chaîne d’un seul caractère et est toujours une clé de arbre
  • la hauteur de l’arbre est au plus 100, donc la profondeur de récursion reste faible
  • taille renvoie un entier : le nombre de nœuds du sous-arbre de sommet lettre

Exercice 2

Contraintes :

  • 0 <= len(tab) <= 300
  • tab est un tableau (liste Python) d’entiers, éventuellement répétés
  • -10^9 <= tab[i] <= 10^9
  • pour echange(tab, i, j) : 0 <= i < len(tab) et 0 <= j < len(tab) ; i et j peuvent être égaux
  • echange et tri_selection modifient tab sur place et renvoient None
  • après appel de tri_selection(tab), tab contient les mêmes éléments triés dans l’ordre croissant

Solution

Exercice 1 - taille d’un arbre binaire

L’idée. Compter les nœuds d’un arbre, c’est compter son sommet (1 nœud), puis ajouter le nombre de nœuds de son sous-arbre gauche et celui de son sous-arbre droit. Ces deux sous-arbres sont eux-mêmes des arbres : on peut donc leur appliquer taille, et c’est exactement ça, la récursivité. Il reste à dire quand on s’arrête : quand un fils est absent, c’est-à-dire quand la lettre vaut la chaîne vide '', il n’y a aucun nœud à compter, donc on renvoie 0.

Un petit exemple. Dans l’arbre a du sujet, 'I' a pour fils gauche '' et pour fils droit 'H'. Donc taille(a, 'I') vaut 1 + taille(a, '') + taille(a, 'H'), soit 1 + 0 + 1, soit 2.

def taille(arbre, lettre):
    # Un fils absent est noté '' : ce sous-arbre est vide, il ne contient aucun nœud
    if lettre == '':
        return 0
    # Sinon le sommet compte pour 1, plus les nœuds du sous-arbre gauche et du droit
    return 1 + taille(arbre, arbre[lettre][0]) + taille(arbre, arbre[lettre][1])

arbre[lettre] est la liste des deux fils de lettre : arbre[lettre][0] est le fils gauche, arbre[lettre][1] le fils droit. Le code ne fait donc que traduire la phrase de l’idée, ligne pour ligne. Le test if lettre == '': est le cas d’arrêt : sans lui, la fonction s’appellerait indéfiniment et Python signalerait une erreur de récursion.

Attention : taille compte le sous-arbre de sommet lettre, pas tout le dictionnaire. C’est pour cela que taille(a, 'B') vaut 5 et non 9 : renvoyer len(arbre) serait faux.

Exercice 2 - tri par sélection

L’idée. À chaque étape k, la partie du tableau située avant l’indice k est déjà triée et définitive. On cherche alors le plus petit élément parmi ceux qui restent, entre les indices k et N - 1, et on l’échange avec celui qui occupe la position k. On recommence avec le k suivant, et le tableau se trie de la gauche vers la droite.

Un petit exemple. Pour [41, 55, 21, 18, 12, 6, 25] avec k = 0, le plus petit élément est 6, à l’indice 5. On échange les positions 0 et 5 : le tableau devient [6, 55, 21, 18, 12, 41, 25], exactement l’étape 1 du sujet.

def echange(tab, i, j):
    '''Echange les éléments d'indice i et j dans le tableau tab.'''
    temp = tab[i]
    tab[i] = tab[j]
    tab[j] = temp

def tri_selection(tab):
    '''Trie le tableau tab dans l'ordre croissant
    par la méthode du tri par sélection.'''
    N = len(tab)
    for k in range(N):
        imin = k
        for i in range(k + 1, N):
            if tab[i] < tab[imin]:
                imin = i
        echange(tab, k, imin)

Dans echange, la variable temp met de côté la valeur de tab[i] avant qu’elle ne soit écrasée par tab[j]. Sans elle, les deux cases finiraient avec la même valeur.

Dans tri_selection, imin retient l’indice du plus petit élément trouvé depuis le début de l’étape. On lui donne d’abord la valeur k, le premier élément non encore rangé, puis la boucle interne compare tous les suivants, de k + 1 jusqu’à N - 1, avec tab[imin] : dès qu’un élément est plus petit, imin prend son indice. Quand cette boucle est terminée, imin est bien l’indice du minimum de la partie non triée, et echange(tab, k, imin) le place en position k.

Remarque : les deux fonctions modifient tab sur place et ne renvoient rien. Après tri_selection(tab), c’est tab lui-même qui est trié ; il ne faut donc pas écrire tab = tri_selection(tab), qui donnerait None.