Activités pratiques : Types de données récursives

Duration1h15

Contenu de l’activité

Dans cette activité, vous allez implémenter un arbre généalogique qui repose sur une structure de données récursive. Un arbre généalogique est un arbre où chaque nœud représente une personne, et les liens entre les nœuds représentent les relations familiales (parents, enfants, etc.).

Pour commencer, vous devez télécharger le squelette de code fourni dans le dossier compressé familytree.zip et le décompresser dans un dossier de votre choix. Puis, depuis VS Code Fichier > Ouvrir Dossier... sélectionnez le dossier décompressé.

Arborescence du dossier familytree
Le projet est organisé de la manière suivante :
  • le dossier .vscode contient dans le fichier settings.json la configuration de VS Code pour le projet,
  • le dossier genealogy contient le code source de l'arbre généalogique, à savoir les classes Person définie dans le fichier genealogy/person.py et FamilyTree définie dans le fichier genealogy/familytree.py,
  • le dossier tests contient les tests unitaires pour vérifier que votre implémentation fonctionne correctement.

Pour exécuter les tests, vous devez cliquer sur l’icône à gauche de l’éditeur, puis cliquer sur la double flèche en haut de la vue Tests pour exécuter tous les tests.

À ce stade, vous devriez voir un test échouer, car les classes Person et FamilyTree ne sont pas encore implémentées. Vous allez donc devoir compléter les classes Person et FamilyTree.

1 - Structure récursive

Un arbre généalogique est une structure de données récursive, car chaque personne peut avoir des enfants, qui sont eux-mêmes des personnes. Avant de vous lancer dans la programmation, vous devez réfléchir à la manière dont vous pourriez modéliser un arbre généalogique et les relations qui en découlent en utilisant une structure récursive. Vous devrez considérer le cas récursif ainsi que le(s) cas de base. Cette structure devra permettre d’ajouter, de supprimer et de rechercher des personnes dans l’arbre.

2 - Personne

Vous allez tout d’abord compléter la classe Person qui représentera une personne dans l’arbre généalogique. Cette classe devra contenir les informations suivantes :

  • Le nom de la personne, sous la forme d’une chaîne de caractères, nommée name,
  • La liste de ses enfants (qui seront également des instances de la classe Person), nommée children,
  • Ses deux parents, nommés parent1 et parent2.

Si un parent n’est pas connu, alors il sera défini à None.

Important

Vous devez respecter les conventions de nommage pour que les tests fonctionnent correctement.

3 - Arbre généalogique

Vous allez ensuite ouvrir la classe FamilyTree déclarée dans le fichier genealogy/familytree.py. Elle représente l’arbre généalogique lui-même. Cette classe déclare un constructeur qui initialise les éléments suivants :

  • Une instance de Person qui sera la racine de l’arbre, nommée __root,
Information

Il faut considérer que __root est une personne fictive qui n’a pas de parents connus, et qui n’est pas visible par l’utilisateur de l’arbre généalogique. Elle sert uniquement à simplifier la structure de l’arbre.

Ainsi, par convention, les personnes ajoutées à l’arbre ne déclarant aucun parent seront déclarées comme étant des enfants de __root, mais elles ne déclareront pas __root comme parent.

Un arbre généalogique vide est donc uniquement composé d’une instance de personne (__root) sans enfants, cachée de l’utilisateur.

Vous devez consulter le fichier indiqué et prendre connaissance des méthodes déjà déclarées dans la classe FamilyTree. Vous n’avez pas le droit de changer la signature des méthodes existantes, ceci afin de garantir que les tests fonctionneront correctement. Par contre, vous allez devoir compléter les méthodes existantes, et si besoin, en ajouter de nouvelles.

4 - Trouver une personne

  1. Vous allez maintenant implémenter une méthode find_person(self, name) dans la classe FamilyTree. Cette méthode devra parcourir l’arbre à partir de la racine et retourner l’instance de Person correspondante au nom recherché, ou None si la personne n’est pas trouvée.

    Cette méthode devra utiliser une approche récursive pour parcourir l’arbre.

  2. Vous ajouterez également une méthode contains(self, name) dans la classe FamilyTree qui renverra True si la personne existe dans l’arbre, et False sinon. Cette méthode utilisera la méthode find_person.

5 - Ajout de personnes

Vous allez maintenant implémenter une méthode add_person(self, name, parent1=None, parent2=None) dans la classe FamilyTree. Cette méthode devra permettre d’ajouter une nouvelle personne à l’arbre généalogique. Avant toute chose, vous devez vérifier si la personne existe déjà dans l’arbre. Si c’est le cas, vous ne devez pas l’ajouter à nouveau. Si la personne n’existe pas, vous devez l’ajouter à l’arbre. Si des parents sont fournis, la personne sera ajoutée à leurs listes d’enfants. Si aucun parent n’est spécifié, la personne sera ajoutée comme enfant de Lucy.

Pour alimenter votre arbre généalogique, nous avons fourni un exemple d’arbre généalogique de la famille Simpson. Le code se trouve à la fin du fichier genealogy/familytree.py.

Arbre généalogique de la famille Simpson (src: modelegenealogique.fr)

6 - Grands-parents, frères et sœurs

Vous allez maintenant implémenter deux méthodes supplémentaires:

  • get_grandparents(self, name) dans la classe FamilyTree. Cette méthode devra retourner une liste des grands-parents de la personne dont le nom est donné en paramètre. Si la personne n’existe pas ou n’a pas de grands-parents, la méthode devra retourner une liste vide.
  • get_siblings(self, name) dans la classe FamilyTree. Cette méthode devra retourner une liste des frères et sœurs de la personne dont le nom est donné en paramètre. Sont considérés comme frères et sœurs les personnes qui ont au moins un parent en commun avec la personne recherchée. Si la personne n’existe pas ou n’a pas de frères et sœurs, la méthode devra retourner une liste vide.

Pour aller plus loin

Vous pouvez aller plus loin en implémentant les fonctionnalités suivantes :

  • Ajouter une méthode get_ancestors(self, name) dans la classe FamilyTree. Cette méthode devra retourner une liste de tous les ancêtres de la personne dont le nom est donné en paramètre, en remontant jusqu’à la racine de l’arbre.
  • Ajouter une méthode get_descendants(self, name) dans la classe FamilyTree. Cette méthode devra retourner une liste de tous les descendants de la personne dont le nom est donné en paramètre, en descendant jusqu’aux feuilles de l’arbre.
  • Ajouter une méthode get_family_tree(self, name) dans la classe FamilyTree. Cette méthode devra retourner une représentation textuelle de l’arbre généalogique de la personne dont le nom est donné en paramètre, en incluant tous les ancêtres et descendants de cette personne.
  • Ajouter une méthode get_relationship(self, name1, name2) dans la classe FamilyTree. Cette méthode devra retourner le type de relation entre les deux personnes dont les noms sont donnés en paramètres (par exemple, “parent”, “enfant”, “frère/sœur”, “grand-parent”, etc.). Si les deux personnes ne sont pas liées, la méthode devra retourner None.
  • etc