Parcours d'arbre binaire⚓︎
D'après 2022, Nouvelle-Calédonie, J2, Ex. 2
On crée un jeu dans lequel les personnages doivent se déplacer. Le personnage Mélusine se déplace et se retrouve devant deux chemins possibles. Le schéma 1 ci-dessous illustre la situation.
Mélusine part du point A
et peut se rendre à n'importe quel autre point repéré par une lettre.
Sous chaque lettre, se cache un objet à récupérer. Chaque objet est associé à une valeur.
Schéma 1
graph TD
A(A) --> Ag(B)
A --> Ad(F)
Ag --> Agg(C)
Ag --> Agd(D)
Agg --> Aggg(" ")
style Aggg fill:none,stroke-width:0px
linkStyle 4 stroke-width:0px
Agg --> Aggd(E)
Ad --> Adg(G)
Ad --> Add(H)
Adg --> Adgg(I)
Adg --> Adgd(" ")
style Adgd fill:none,stroke-width:0px
linkStyle 9 stroke-width:0px
Add --> Addg(" ")
style Addg fill:none,stroke-width:0px
linkStyle 10 stroke-width:0px
Add --> Addd(J)
1.) Indiquer pourquoi il s'agit d'un arbre binaire.
Réponse
À chaque position, Mélusine peut éventuellement se déplacer à gauche ou à droite, en descendant ; certains choix n'aboutissant pas.
On peut donc considérer qu'il s'agit d'un arbre binaire où chaque position indique deux nouvelles directions : une à droite, une à gauche qui conduisent à un nouvel arbre binaire, éventuellement vide.
2.) À chaque lettre, on attribue une valeur positive. On définit la variable valeur_lettre
suivante contenant les valeurs associées aux lettres :
valeur_lettre = {
'A': 1 , 'B': 2 , 'C': 3 , 'D': 5 , 'E': 10 ,
'F': 15 , 'G': 4 , 'H': 5 , 'I': 5 , 'J': 7,
}
2.a) Indiquer le type de la variable valeur_lettre
.
Réponse
valeur_lettre
est un dictionnaire.
- Ses clés sont des chaines de caractères de longueur 1, des lettres.
- Les valeurs associées sont des entiers positifs.
2.b) Écrire l'instruction permettant d'accéder à la valeur 7
stockée dans cette
variable.
Réponse
>>> valeur_lettre['J']
7
2.c) Écrire une fonction somme
en langage Python qui prend un paramètre poids
du même
type que la variable valeur_lettre
vue précédemment et qui renvoie la somme des valeurs de poids
.
Réponse
Il plusieurs méthodes :
def somme(poids):
# style itératif simple
cumul = 0
for clef in poids:
cumul += poids[clef]
return cumul
def somme(poids):
# style fonctionnel
return sum(poids.values())
Et surement d'autres encore.
2.d) Écrire une fonction poids_lourd
en langage Python qui prend un paramètre poids
du même type que la variable valeur_lettre
, non vide, et qui renvoie l'élément ayant la valeur maximale de poids
. On supposera que toutes les valeurs sont des entiers positifs.
Réponse
Il y a plusieurs méthodes :
def poids_lourd(poids):
# style itératif simple
valeur_maxi = 0
for element in poids:
valeur = poids[cle]
if valeur_maxi <= valeur:
valeur_maxi = valeur
element_lourd = element
return element_lourd
if valeur_maxi <= valeur:
cette condition sera évaluée positivement au moins une fois, le dictionnaire est non vide et ses valeurs sont positives. Ainsi element_lourd
sera bien défini. Notons que un tel element_lourd
n'est peut-être pas unique.
def poids_lourd(poids):
# FAUX
valeur_maxi = 0
for element in poids:
valeur = poids[cle]
if valeur_maxi < valeur:
valeur_maxi = valeur
element_lourd = element
return element_lourd
Si les valeurs sont toutes nulles, alors element_lourd
ne sera jamais défini.
def poids_lourd(poids):
# style un peu fonctionnel
valeur_maxi = 0
for element, valeur in poids.items():
if valeur_maxi <= valeur:
valeur_maxi = valeur
element_lourd = element
return element_lourd
3.) Indiquer, en justifiant la réponse, le rôle de l'algorithme suivant
CALCUL(T : arbre) :
VARIABLE
x : nœud
DÉBUT
si T n'est pas un arbre vide :
x ← racine de T
renvoyer (
1
+ CALCUL(sous arbre à gauche de x)
+ CALCUL(sous arbre à droite de x)
)
sinon :
renvoyer 0
fin si
FIN
Réponse
Cet algorithme renvoie la taille de arbre
, c'est le nombre de nœuds de cet arbre. En effet,
- un arbre vide ne possède aucun nœud,
- un arbre non vide possède un nœud (sa racine), et ceux des ses sous arbres à gauche et à droite, obtenus de manière récursive.
4.) On applique l'algorithme ci-dessous à l'arbre du schéma 1.
VISITE(T : arbre) :
VARIABLE
x : nœud
DÉBUT
si T n'est pas un arbre vide :
x ← racine de T
affiche clé de x
VISITE(sous arbre à gauche de x)
VISITE(sous arbre à droite de x)
fin si
FIN
4.a) Indiquer l'affichage obtenu.
Réponse
On obtient l'affichage de A, B, C, E, D, F, G, I, H, J.
4.b) Indiquer le type de parcours réalisé par l'algorithme VISITE.
Réponse
VISITE est un algorithme qui réalise un parcours préfixe : on traite la racine de l'arbre avant de traiter le sous-arbre à gauche puis le sous-arbre à droite.