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

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

Énoncé du problème

Exercice 1

Exercice 2