Exo bac C5.EB1

Cet exercice porte sur les arbres binaires et leurs algorithmes associés

La fédération de badminton souhaite gérer ses compétitions à l’aide d’un logiciel.

Pour ce faire, une structure arbre de compétition a été définie récursivement de la façon suivante : un arbre de compétition est soit l’arbre vide, noté ∅, soit un triplet composé d’une chaîne de caractères appelée valeur, d’un arbre de compétition appelé sous-arbre gauche et d’un arbre de compétition appelé sous-arbre droit.

On représente graphiquement un arbre de compétition de la façon suivante :

Pour alléger la représentation d’un arbre de compétition, on ne notera pas les arbres vides, l’arbre précédent sera donc représenté par l’arbre A suivant :

Cet arbre se lit de la façon suivante :

Pour s’assurer que chaque finaliste ait joué le même nombre de matchs, un arbre de compétition a toutes ces feuilles à la même hauteur.

Les quatre fonctions suivantes pourront être utilisées :

• La fonction racine qui prend en paramètre un arbre de compétition arb et renvoie la valeur de la racine.
Exemple : avec l’exemple d’arbre de compétition présenté ci-dessus, racine(A) vaut "Kamel".

• La fonction gauche qui prend en paramètre un arbre de compétition arb et renvoie son sous-arbre gauche.
Exemple : avec l’exemple d’arbre de compétition présenté ci-dessus, gauche(A) vaut l’arbre représenté graphiquement ci-après :

• La fonction droit qui prend en argument un arbre de compétition arb et renvoie son sous-arbre droit.
Exemple : avec l’exemple d’arbre de compétition présenté ci-dessus, droit(A) vaut l’arbre représenté graphiquement ci-après :

• La fonction est_vide qui prend en argument un arbre de compétition et renvoie True si l’arbre est vide et False sinon.
Exemple : avec l’exemple d’arbre de compétition présenté ci-dessus, est_vide(A) vaut False.

Pour toutes les questions de l’exercice, on suppose que tous les joueurs d’une même compétition ont un prénom différent.

1.

1.a. On considère l’arbre de compétition B ci-contre. Indiquer la racine de cet arbre puis donner l’ensemble des valeurs des feuilles de cet arbre.

1.b. Proposer une fonction Python vainqueur prenant pour argument un arbre de compétition arb ayant au moins un joueur. Cette fonction doit renvoyer la chaîne de caractères constituée du nom du vainqueur du tournoi.
Exemple : vainqueur(B) vaut "Lea"

1.c. Proposer une fonction Python finale prenant pour argument un arbre de compétition arb ayant au moins deux joueurs. Cette fonction doit renvoyer le tableau des deux chaînes de caractères qui sont les deux compétiteurs finalistes.
Exemple : finale(B) vaut ["Lea", "Louis"]

2. Donner la liste des prénoms que l’on obtient avec un parcours postfixe (ou suffixe) de l’arbre.

3.

3.a. Proposer une fonction Python occurrences ayant pour paramètre un arbre de compétition arb et le nom d’un joueur nom et qui renvoie le nombre d’occurrences (d’apparitions) du joueur nom dans l’arbre de compétition arb.

Exemple : occurences(B, "Anne") vaut 2.

3.b. Proposer une fonction Python a_gagne prenant pour paramètres un arbre de compétition arb et le nom d’un joueur nom et qui renvoie le booléen True si le joueur nom a gagné au moins un match dans la compétition représentée par l’arbre de compétition arb.

Exemple : a_gagne(B,"Louis") vaut True

4. On souhaite programmer une fonction Python nombre_matchs qui prend pour arguments un arbre de compétition arb et le nom d’un joueur nom et qui renvoie le nombre de matchs joués par le joueur nom dans la compétition représentée par l’arbre de compétition arb.

Exemple : nombre_matchs(B,"Lea") doit valoir 3 et nombre_matchs(B,"Marc") doit valoir 1.

4.a. Expliquer pourquoi les instructions suivantes renvoient une valeur erronée. On pourra pour cela identifier le nœud de l’arbre qui provoque une erreur.

def nombre_matchs(arb ,nom ):
        """ arbre_competition , str -> int """
        return occurrences(arb ,nom )

4.b. proposer une correction pour la fonction nombre_matchs.

5. Recopier et compléter la fonction liste_joueurs qui prend pour argument un arbre de compétition arb et qui renvoie un tableau contenant les participants au tournoi, chaque nom ne devant figurer qu’une seule fois dans le tableau.

L’opération + à la ligne 9 permet de concaténer deux tableaux.
Exemple : Si L1 = [4, 6] et L2 = [3, 5], l’instruction L1 + L2 va renvoyer [4, 6, 3, 5]

def liste_joueurs(arb):
    """ arbre_competition -> tableau """
    if est_vide (arb ):
        return ______________
    elif ____________ and _____________ :
        return [ racine (arb )]
    else :
        return _______________ + liste_joueurs ( droit ( arb ))
Afficher la correction

1.a. La racine de l’arbre est "Léa".

L’ensemble des feuilles est donné par la liste : "Marc", "Lea", "Claire", "Theo", "Marie", "Louis", "Anne" et "Kevin".

1.b.

def vainqueur(arb):
    return racine(arb)

1.c.

def finale(arb):
    return [racine(gauche(arb)), racine(droit(arb))]

2. Marc Léa Léa Claire Théo Théo Léa Marie Louis Louis Anne Kevin Anne Louis Léa

3.a. On utilise, par exemple, un parcours en profondeur :

def occ(arb,nom):
    if est_vide(arb):
        return 0
    else:
        if racine(arb) == nom:
            return 1 + occ(gauche(arb),nom) + occ(droit(arb),nom)
        else :
            return occ(gauche(arb),nom) + occ(droit(arb),nom)

3.b. On peut utiliser l’algorithme de la question précédente.

def a_gagne(arb,nom):
    if occurrence(arb,nom)>1:
        return True
    else:
        return False

4.a. Le nombre d’occurrence d’apparition d’un nom dans l’arbre n’est pas le nombre de matchs joués. Le nœud racine n’est pas un match joué. Il y a donc des joueurs qui sont comptés une fois de trop s’il y a un match gagnant.

4.b. Il suffit d’enlever 1 aux nombres d’occurrence quand il y a au moins un match de gagner.

def nombre_matchs(arb,nom):
    """ arbre_competition , str-> int """
    if a_gagne(arb,nom):
        return occurrence(arb,nom)-1
    else:
        return occurrence(arb,nom)

5.

def liste_joueurs ( arb ):
    """ arbre_competition -> tableau """
        if est_vide ( arb ):
            return []
        elif est_vide(gauche(arb)) and est_vide(droit(arb)):
            return [ racine ( arb )]
        else :
            return liste_joueurs(gauche( arb ))+liste_joueurs(droit(arb))