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
def somme(une_liste):
resultat = 0
for un_entier in une_liste:
resultat += un_entier
return resultat
Recommandée.
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.
def somme(une_liste):
return sum(une_liste)
Ce serait un peu tricher...
somme = sum
Ou pour faire une blague...
5. La fonction parcourir(arbre)
pourrait se traduire en langage naturel par :
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 siarbre
est vide et renvoie un booléenTrue
ouFalse
.valeur_racine(arbre)
: renvoie la valeur numérique de la racine dearbre
;arbre_gauche(arbre)
: renvoie le sous arbre à gauche dearbre
;arbre_droite(arbre)
: renvoie le sous arbre à droite dearbre
.
Réponse
def somme(arbre):
if est_vide(arbre):
return 0
else:
return (
valeur_racine(arbre)
+ somme(arbre_gauche(arbre))
+ somme(arbre_droite(arbre))
)