Aller au contenu

Somme des valeurs d'un arbre binaire⚓︎

D'après 2022, Métropole, J1, Ex. 4

Cet exercice traite du calcul de la somme d'un arbre binaire. Cette somme consiste à additionner toutes les valeurs numériques contenues dans les nœuds de l'arbre.

L'arbre utilisé dans les parties A et B est le suivant :

graph TD
    N0(3) --> N1(6)
    N0    --> N2(2)
    N1    --> N4(7)
    N1    --> N5(4)
    N2    --> N6(9)
    N2    --> N7(1)

Partie A : Parcours d'un arbre⚓︎

1. Donner la somme de l'arbre précédent. Justifier la réponse en explicitant le calcul qui a permis de l'obtenir.

Réponse

La somme de l'arbre est \(3 + 6 + 2 + 7 + 4 + 9 + 1 = 32\)

2. Indiquer la lettre correspondante aux noms « racine », « feuille », « nœud », « SAG » (Sous Arbre à Gauche) et « SAD » (Sous Arbre à Droite). Chaque lettre A, B, C, D et E ne devra être utilisée qu'une seule fois.

flowchart TD
    subgraph G0 ["Arbre avec des lettres à associer                                      "]

        N0(3) --> N1(6)
        N0    --> N2(2)
        subgraph G2 [ ]
            N2    --> N6(9)
            N2    --> N7(1)
        end
        subgraph G3 [ ]
            N1    --> N4(7)
            N1    --> N5(4)
        end

        A>A] -.- N0
        B>B] -.- N1
        C>C] -.- N4
        G3 -.- D>D]
        G2 -.- E>E]
    end
Réponse
Lettre Nom
A racine
B nœud
C feuille
D SAG
E SAD

3. Parmi les quatre propositions A, B, C et D ci-dessous, donnant un parcours en largeur de l'arbre, une seule est correcte. Indiquer laquelle.

  • Proposition A : 7 - 6 - 4 - 3 - 9 - 2 - 1
  • Proposition B : 3 - 6 - 7 - 4 - 2 - 9 - 1
  • Proposition C : 3 - 6 - 2 - 7 - 4 - 9 - 1
  • Proposition D : 7 - 4 - 6 - 9 - 1 - 2 - 3
Réponse

On lit chaque niveau, de la gauche vers la droite.

  • 3, puis
  • 6, 2, puis
  • 7, 4, 9, 1.

La proposition C est la bonne.

4. Écrire en langage Python la fonction somme qui prend en paramètre une liste de nombres et qui renvoie la somme de ses éléments.

Exemple : somme([1, 2, 3, 4]) est égale à 10.

Réponse

Plusieurs réponses possibles

🐍 Script Python
def somme(une_liste):
    resultat = 0
    for un_entier in une_liste:
        resultat += un_entier
    return resultat

Recommandée.

🐍 Script Python
def somme(une_liste):
    resultat = 0
    for i in range(len(une_liste)):
        resultat += une_liste[i]
    return resultat

Inutile, ici, d'utiliser un indice.

🐍 Script Python
def somme(une_liste):
    return sum(une_liste)

Ce serait un peu tricher...

🐍 Script Python
somme = sum

Ou pour faire une blague...

5. La fonction parcourir(arbre) pourrait se traduire en langage naturel par :

📋 Pseudo-code
parcourir(A):
    L = liste_vide
    F = file_vide
    enfiler A dans F
    Tant que F n'est pas vide
        défiler S de F
        ajouter la valeur de la racine de S dans L
        Pour chaque sous arbre SA non vide de S
            enfiler SA dans F
    renvoyer L

Donner le type de parcours obtenu grâce à la fonction parcourir.

Réponse

Si, à un moment du traitement, la file ne contient que des éléments d'un certain niveau, puis (éventuellement) du niveau suivant, alors on enfile pendant le traitement des éléments du niveau suivant, ce qui fait que cette propriété est conservée.

Au départ, la propriété est de mise avec un seul élément. Elle le restera pendant tout le parcours, ainsi on traite les éléments niveau par niveau.

Il s'agit d'un parcours en largeur.

Partie B : Méthode « diviser pour régner »⚓︎

6. Parmi les quatre propositions A,B, C et D ci-dessous, indiquer la seule proposition correcte. En informatique, le principe diviser pour régner est associé à :

  • Proposition A : diviser une fonction en deux fonctions de plus petit code.
  • Proposition B : utiliser plusieurs modules
  • Proposition C : séparer les informations en fonction de leur type
  • Proposition D : découper un problème initial en sous-problèmes, à résoudre, puis combiner leurs solutions
Réponse

Proposition D

En informatique, diviser pour régner (du latin « Divide ut imperes », divide and conquer en anglais) est une technique algorithmique consistant à :

  • Diviser : découper un problème initial en sous-problèmes ;
  • Régner : résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits) ;
  • Combiner : calculer une solution au problème initial à partir des solutions des sous-problèmes.

7. L'arbre présenté dans le problème peut être décomposé en racine et sous arbres :

graph TD
    N0(3) --> N1(6)
    N0    --> N2(2)
    subgraph "SAD                     "
    N2    --> N6(9)
    N2    --> N7(1)
    end
    subgraph "SAG                     "
    N1    --> N4(7)
    N1    --> N5(4)
    end

Indiquer dans l'esprit de « diviser pour régner » l'égalité donnant la somme d'un arbre en fonction de la somme des sous arbres et de la valeur numérique de la racine.

Réponse

somme(arbre) est égal à valeur_racine(arbre) + somme(SAG(arbre)) + somme(SAD(arbre))

8. Écrire en langage Python une fonction récursive somme(arbre). Cette fonction renvoie la somme de l'arbre passé en paramètre.

Les fonctions suivantes sont disponibles :

  • est_vide(arbre) : détermine si arbre est vide et renvoie un booléen True ou False.
  • valeur_racine(arbre) : renvoie la valeur numérique de la racine de arbre ;
  • arbre_gauche(arbre) : renvoie le sous arbre à gauche de arbre ;
  • arbre_droite(arbre) : renvoie le sous arbre à droite de arbre.
Réponse
🐍 Script Python
def somme(arbre):
    if est_vide(arbre):
        return 0
    else:
        return (
            valeur_racine(arbre)
            + somme(arbre_gauche(arbre))
            + somme(arbre_droite(arbre))
        )