Aller au contenu

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 :

🐍 Script Python
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
🐍 Console Python
>>> 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 :

🐍 Script Python
def somme(poids):
    # style itératif simple
    cumul = 0
    for clef in poids:
        cumul += poids[clef]
    return cumul
🐍 Script Python
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 :

🐍 Script Python
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.

🐍 Script Python
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.

🐍 Script Python
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

Algorithme : CALCUL
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.

Algorithme : VISITE
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.