Parcours d'arbres - Tournoi

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é \(\emptyset\), soit un triplet composé d’une chaîne de caractères appelée étiquette, 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 :

Cet arbre se lit de la façon suivante :

4 participants se sont affrontés : Joris, Kamel, Carine, et Abdou. Leurs noms apparaissent en bas de l'arbre, se sont les étiquettes des feuilles de l'arbre.
Au premier tour, Kamel a battu Joris, et Carine a battu Abdou.
En finale, Kamel a battu Carine.
Le vainqueur de la compétition est Kamel.

Pour s'assurer que chaque finaliste ait joué le même nombre de matchs, un arbre de compétition a toutes ses feuilles à la même hauteur : il s'agit donc d'arbres parfaits. On suppose également que tous les joueurs de la compétition ont des noms différents.

On utilisera les fonctions usuelles pour représenter et manipuler les arbres : Arbre, est_vide, est_feuille, etiquette, gauche, et droit. L'arbre vide est représenté par la valeur None.

Exécuter le bloc ci-dessous pour charger l'interface du TP.

###

class Noeud:bksl-nl def py-undpy-undinitpy-undpy-und(self, etiquette, gauche, droit):bksl-nl self.etiquette = etiquettebksl-nl self.gauche = gauchebksl-nl self.droit = droitbksl-nlbksl-nldef creerpy-undvide(): return Nonebksl-nldef estpy-undvide(a): return a is Nonebksl-nldef etiquette(a): return a.etiquettebksl-nldef etiquettepy-undstr(a): return "•" if estpy-undvide(a) else str(etiquette(a))bksl-nldef gauche(a): return a.gauchebksl-nldef droit(a): return a.droitbksl-nldef Arbre(e, a1, a2): return Noeud(e, a1, a2)bksl-nlbksl-nl

L'arbre de l'énoncé est alors :

a = Arbre("Kamel",
          Arbre("Kamel",
                Arbre("Joris", None, None),
                Arbre("Kamel", None, None)),
          Arbre("Carine",
                Arbre("Carine", None, None),
                Arbre("Abdou", None, None)))

Informations sur le tournoi¶

Nombre de joueurs du tournoi¶

Écrire une fonction nb_joueurs qui étant donné un arbre de compétition a renvoie le nombre de joueurs ayant participé à cette compétition.

###

def testpy-undnbpy-undjoueurs():bksl-nl """ Tests pour la fonction nbpy-undjoueurs """bksl-nl print("Tests de nbpy-undjoueurs passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import nbpy-undjoueursbksl-nl# testpy-undnbpy-undjoueurs()bksl-nlbksl-nl 5/5

def nbpy-undjoueurs(a):bksl-nl """ Arbre -> intbksl-nl Renvoie le nombre de joueurs ayant participé à la compétition d'arbre a """bksl-nl passbksl-nlbksl-nl

Nombre de rounds d'un tournoi¶

Écrire une fonction nb_rounds qui étant donné un arbre de compétition a renvoie le nombre de rounds dont a été composée la compétition.

Remarque. Un round correspond à un "niveau" de la compétition : la finale, les demi-finales, les quarts de finale, etc. sont des rounds.

###

def testpy-undnbpy-undrounds():bksl-nl """ Tests pour la fonction nbpy-undrounds """bksl-nl print("Tests de nbpy-undrounds passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import nbpy-undroundsbksl-nl# testpy-undnbpy-undrounds()bksl-nlbksl-nl 5/5

def nbpy-undrounds(a):bksl-nl """ Arbre -> intbksl-nl Renvoie le nombre de rounds de la compétition a """bksl-nl passbksl-nlbksl-nl

Informations sur un joueur¶

Nombre d'occurrences du joueur dans l'arbre¶

Écrire une fonction occurrences qui étant donné un arbre a et le nom nom d'un joueur renvoie le nombre d'occurences de l'étiquette nom parmi les nœuds de l'arbre a.

###

def testpy-undoccurrences():bksl-nl """ Tests pour la fonction occurrences """bksl-nl assert occurrences(a, "Kamel") == 3bksl-nl assert occurrences(a, "Carine") == 2bksl-nl assert occurrences(a, "Joris") == 1bksl-nl assert occurrences(a, "Abdou") == 1bksl-nl assert occurrences(a, "Ada") == 0bksl-nl print("Tests de occurrences passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import occurrencesbksl-nltestpy-undoccurrences()bksl-nlbksl-nl 5/5

def occurrences(a, nom):bksl-nl """ Arbre, str -> intbksl-nl Renvoie le nombre d'occurrences de nom dans a """bksl-nl passbksl-nlbksl-nl

Nombre de matchs joués par le joueur¶

Déduire de la fonction occurrences, une fonction nombre_matchs qui étant donné un arbre de compétition a et un nom nom détermine le nombre de matchs joués par nom pendant à la compétition.

Attention aux cas particuliers

###

def testpy-undnombrepy-undmatchs():bksl-nl """ Tests pour la fonction nombrepy-undmatchs """bksl-nl assert nombrepy-undmatchs(a, "Kamel") == 2bksl-nl assert nombrepy-undmatchs(a, "Carine") == 2bksl-nl assert nombrepy-undmatchs(a, "Joris") == 1bksl-nl assert nombrepy-undmatchs(a, "Abdou") == 1bksl-nl assert nombrepy-undmatchs(a, "Ada") == 0bksl-nl print("Tests de nombrepy-undmatchs passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import nombrepy-undmatchsbksl-nltestpy-undnombrepy-undmatchs()bksl-nlbksl-nl 5/5

def nombrepy-undmatchs(a, nom):bksl-nl """ Arbre, str -> intbksl-nl Renvoie le nombre de matchs joués par le joueur nom dans la compétition d'arbre a """bksl-nl passbksl-nlbksl-nl

Informations sur les joueurs¶

Liste des joueurs du tournoi¶

Compléter le code de la fonction liste_joueurs qui étant donné un arbre de compétition a renvoie la liste des noms de tous les joueurs ayant participé à la compétition. On remarquera qu'il s'agit des étiquettes des feuilles de l'arbre a. Si jamais l'arbre de compétition est vide, on renverra la liste vide.

On rappelle que si l1 et l2 sont deux listes python, alors l1 + l2 renvoie la concaténation de l1 et de l2 : c'est la liste constituée de tous les éléments de l1 et de l2 mis bout à bout.

###

def testpy-undlistepy-undjoueurs():bksl-nl """ Tests pour la fonction listepy-undjoueurs """bksl-nl for j in ["Kamel", "Carine", "Joris", "Abdou"]:bksl-nl assert j in listepy-undjoueurs(a)bksl-nl assert not "ada" in listepy-undjoueurs(a)bksl-nl print("Tests de listepy-undjoueurs passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import listepy-undjoueursbksl-nltestpy-undlistepy-undjoueurs()bksl-nlbksl-nl 5/5

def listepy-undjoueurs(a):bksl-nl """ Arbre -> [str]bksl-nl Renvoie la liste des joueurs ayant participé à la compétition d'arbre a """bksl-nl # if estpy-undvide(a):bksl-nl # return ....................................bksl-nl # elif estpy-undfeuille(a):bksl-nl # return [..................................]bksl-nl # else:bksl-nl # return ....................................bksl-nlbksl-nl

Liste des joueurs par niveau¶

En vous inspirant de la fonction liste_joueurs, écrire une fonction niveau qui étant donné un entier i et un arbre de compétition a renvoie la liste des étiquettes des nœuds de profondeur i de l'arbre a.

On remarquera que :

Si un arbre de compétition a est vide alors pour tout entier i, niveau(i, a) doit renvoyer la liste vide.
le niveau \(0\) correspond à la racine de l'arbre.
le niveau i de l'arbre a correspond au niveau i - 1 du sous-arbre gauche de a et au niveau i - 1 du sous-arbre droit de a.

###

def testpy-undniveau():bksl-nl """ Tests pour la fonction niveau """bksl-nl print("Tests de niveau passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import niveaubksl-nl# testpy-undniveau()bksl-nlbksl-nl 5/5

def niveau(a, i):bksl-nl """ Arbre, int -> [str]bksl-nl Renvoie la liste des étiquettes des nœuds de profondeur i de l'arbre a """bksl-nl passbksl-nlbksl-nl

Liste des joueurs vaincus I¶

Écrire une fonction vaincus_gagnant qui étant donné un arbre de compétition a renvoie la liste des joueurs ayant été vaincus par le gagnant de la compétition.

###

def testpy-undvaincuspy-undjoueur():bksl-nl """ Tests pour la fonction vaincuspy-undjoueur """bksl-nl print("Tests de vaincuspy-undjoueur passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import vaincuspy-undjoueurbksl-nl# testpy-undvaincuspy-undjoueur()bksl-nlbksl-nl 5/5

def vaincuspy-undgagnant(a):bksl-nl """ Arbre -> [str]bksl-nl Renvoie la liste des joueurs ayant joué un match contre le gagnant de la compétition d'arbre a """bksl-nl passbksl-nlbksl-nl

Parcours en largeur¶

Algorithme de cours¶

En vous inspirant de l'algorithme vu en cours, écrire une fonction parcours_largeur qui étant donné un arbre a en renvoie la liste des étiquettes, telles qu'obtenues à l'aide d'un parcours en largeur de l'arbre.

On utilisera un objet file de type list pour représenter la file d'attente des éléments à traiter :

la file est vide lorsque file est la liste [] ;
on enfile l'élément a à l'aide de l'instruction file.append(a) ;
on défile le premier élément de la file à l'aide de l'instruction file.pop(0)
on accède sans défiler au premier élément de la file à l'aide de l'instruction file_noeud[0]

On utilisera un objet liste_etiquettes de type list pour stocker la liste des étiquettes de l'arbre a dans l'ordre du parcours. Initialement celle-ci sera vide. L'opération de traitement sur le nœud parcouru sera l'ajout de son étiquette à la liste liste_etiquettes (lorsque cela est possible).

###

def testpy-undparcourspy-undlargeur():bksl-nl """ Tests pour la fonction parcourspy-undlargeur """bksl-nl print("Tests de parcourspy-undlargeur passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import parcourspy-undlargeurbksl-nl# testpy-undparcourspy-undlargeur()bksl-nlbksl-nl 5/5

def parcourspy-undlargeur(a):bksl-nl """ Arbre -> [str]bksl-nl Renvoie la liste des étiquettes des nœuds de l'arbre a, telle qu'obtenue à l'aide d'un parcours en largeur """bksl-nl passbksl-nlbksl-nl

Liste des joueurs vaincus II¶

On souhaite établir la liste des joueurs ayant été vaincus par un joueur donné dans la compétition d'arbre a. Pour cela, on utilise l'algorithme suivant :

on détermine le nœud n de profondeur minimale de l'arbre de compétition a dont l'étiquette est égale au nom du joueur recherché ;
la liste des joueurs vaincus par nom dans la compétition d'arbre a est la liste des joueurs vaincus par le gagnant de la compétition dont l'arbre est le sous-arbre de a de racine n.

Par exemple, dans l'arbre de compétition de l'énoncé, si on souhaite établir la liste des joueurs ayant été vaincus par Carine :

le nœud de profondeur minimal n est alors le nœud à la profondeur 1 et d'étiquette "Carine" ;
le sous-arbre de racine n est constitué de trois éléments. Dans cette sous-compétition, Carine n'a vaincu qu'un seul joueur, Abdou.

Ainsi la liste des joueurs vaincus par Carine est donc ["Abdou"].

Recherche d'un nœud de profondeur minimale¶

Écrire une fonction recherche_noeud qui étant donné un arbre a et un nom renvoie le nœud de profondeur minimal de a dont l'étiquette est nom. On utilisera pour cela un parcours en largeur d'abord et on s'arrêtera dès que l'étiquette du nœud courant est le nom recherché.

Dans le cas où nom n'est pas une étiquette de l'arbre a, on renverra None.

###

def testpy-undrecherchepy-undnoeud():bksl-nl """ Tests pour la fonction recherchepy-undnoeud """bksl-nl print("Tests de recherchepy-undnoeud passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import recherchepy-undnoeudbksl-nl# testpy-undrecherchepy-undnoeud()bksl-nlbksl-nl 5/5

def recherchepy-undnoeud(a, nom):bksl-nl """ Arbre, str -> Arbrebksl-nl Renvoie le sous-arbre de a dont la racine a pour étiquette nom et est de profondeur minimale dans a """bksl-nl passbksl-nlbksl-nl

Liste des joueurs vaincus¶

Écrire une fonction joueurs_vaincus qui étant donné un arbre de compétition a et le nom d'un joueur nom renvoie la liste des joueurs vaincus par nom dans la compétition. On utilisera pour cela l'algorithme décrit en section 4.2 ainsi que les fonctions vaincus_gagnant et recherche_noeud précédemment écrites.

###

def testpy-undjoueurspy-undvaincus():bksl-nl """ Tests pour la fonction joueurspy-undvaincus """bksl-nl print("Tests de joueurspy-undvaincus passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import joueurspy-undvaincusbksl-nl# testpy-undjoueurspy-undvaincus()bksl-nlbksl-nl 5/5

def joueurspy-undvaincus(a, nom):bksl-nl """ Arbre, str -> [str]bksl-nl Renvoie la liste des joueurs vaincus par nom dans la compétition d'arbre a """bksl-nl passbksl-nlbksl-nl