Aller au contenu

2022, Mayotte-Liban, sujet 1, exercice 4⚓︎

Thème : Algorithmique (arbres binaires en profondeurs préfixe et infixe)

On s'intéresse dans cet exercice à l'étude d'un arbre généalogique.

Voici un extrait de l'arbre généalogique fictif d'une personne nommée Albert Normand.

L'arbre généalogique est présenté avec les parents vers le bas et les enfants vers le haut.

Albert Normand est considéré comme la génération 0. On considère ses parents comme la génération 1, ses grands-parents comme la génération 2 et ainsi de suite pour les générations précédentes.

L'arbre généalogique d'Albert Normand

généalogie

Remarque

Il faut être prudent lorsqu'on parle d'arbre binaire à propos d'un arbre généalogique puisque justement, formellement ce n'en n'est pas un. En effet, il existe forcément une génération où un individu aura 2 parents (au sens de l'arbre binaire).

Modélisation de l'arbre⚓︎

L'arbre généalogique d'un individu est modélisé par un arbre :

  • chaque nœud de l'arbre représente un individu ;
  • le premier nœud du sous-arbre gauche d'un individu est associé à son père ;
  • le premier nœud du sous-arbre droit d'un individu est associé à sa mère.

Implémentation de l'arbre⚓︎

Pour implémenter l'arbre, on utilise des notions de programmation orientée objet. Chaque nœud de l'arbre est représenté par un objet qui est l'instance d'une classe Noeud ayant trois attributs. Ainsi, l'objet N de type Noeud aura les attributs suivants :

  • N.identite de type tuple : (prenom, nom) de l'individu référencé par l'objet N;
  • N.gauche de type arbre binaire : le sous-arbre gauche de l'objet N ;
  • N.droit de type arbre binaire : le sous-arbre droit de l'objet N.

Pour un individu, référencé par l'objet Nde type Noeud, dont on ne connait pas les parents, on considèrera que N.gauche et N.droit ont la valeur None.

Remarque

L'implémentation est bancale : on parle du type arbre binaire pour les attributs gauche et droit mais ce type n'a pas été défini. Il s'agit en fait du type Noeud.

Question 1a

Expliquer en quoi cet arbre généalogique est un arbre binaire.

Réponse

La question met explicitement en avant le problème évoqué dans notre première remarque.

L'arbre de l'exemple est certes un arbre binaire : chaque individu est le père ou la mère d'un unique individu (donc chaque nœud a un seul parent au sens d'arbre binaire) et un individu à un père et une mère (donc au plus 2 successeurs au sens des nœuds).

Néanmoins, rien n'interdirait qu'un individu de la génération \(n\) soit relié à plus d'un individu de la génération \(n-1\) : par exemple Camélia Charentais pourrait bien être la mère d'Hélène Breton mais aussi de Thibaut Comtois. On aurait alors un graphe et non plus un arbre.

Question 1b

Pourquoi un arbre généalogique n'est pas un arbre binaire de recherche (ABR) ?

Réponse

Parce qu'un arbre généalogique ne classe pas ses nœuds suivant un ordre sur les étiquettes : ici les nœuds de gauche sont les pères, ceux de droite sont les mères.

On souhaite obtenir la liste de tous les ascendants (ancêtres) d'Albert Normand. Pour cela, on utilise un parcours en profondeur de l'arbre.

Question 2a

Écrire les sept premières personnes (nom et prénom) rencontrées si on utilise le parcours en profondeur préfixe.

Réponse

7 premières personnes lors d'un parcours préfixe : Albert Normand, Jules Normand, Michel Normand, Jules Normand, Odile Picard, Hélène Breton, Evariste Breton.

Question 2b

Écrire les sept premières personnes (nom et prénom) rencontrées si on utilise le parcours en profondeur infixe.

Réponse

7 premières personnes lors d'un parcours infixe : Jules Normand, Michel Normand, Odile Picard, Jules Normand, Evariste Breton, Hélène Breton, Camélia Charentais.

On donne ci-dessous le code incomplet de la fonction d'un parcours en profondeur de l'arbre, dans lequel il manque la ligne correspondant à l'instruction d'affichage du prénom et du nom de l'individu :

Parcours en profondeur à compléter...
def parcours(racine_de_l_arbre):
    if racine_de_l_arbre != None:
        noeud_actuel = racine_de_l_arbre
        parcours(noeud_actuel.gauche)
        parcours(noeud_actuel.droite)
Remarque

Pourquoi d'un coup l'attribut s'appelle droite ? Pourquoi un tel nom de variable : racine_de_l_arbre ? Pourquoi passer par une autre variable : noeud_actuel ? Tout cela alourdit le code.

Question 2c

Recopier et compléter l'algorithme ci-dessus en y insérant au bon endroit la ligne contenant l'instruction d'affichage pour que cet algorithme corresponde à un parcours en profondeur préfixe.

Réponse
Parcours en profondeur préfixe
def parcours(racine):
    if racine != None:
        prenom, nom = racine.identite
        print(prenom, nom)
        parcours(racine.gauche)
        parcours(racine.droite)
Question 2d

Recopier et compléter l'algorithme ci-dessus en y insérant au bon endroit la ligne contenant l'instruction d'affichage pour que cet algorithme corresponde à un parcours en profondeur infixe.

Réponse
Parcours en profondeur infixe
def parcours(racine):
    if racine != None:
        prenom, nom = racine.identite
        print(prenom, nom)
        parcours(racine.gauche)
        print(prenom, nom)
        parcours(racine.droite)

On souhaite maintenant préciser la génération d'un individu dans l'implémentation de l'arbre généalogique. Lors de la création de l'instance, on donnera la valeur 0 par défaut.

Question 3a

Recopier et compléter la définition de la classe Noeud pour ajouter un attribut generation qui indique la génération d'un individu.

Classe Noeud à compléter...
class Noeud:
    def __init__(self, prenom, nom):
        self.identite = (prenom, nom)
        self.gauche = None
        self.droite = None
        ........................
Réponse
Classe Noeud avec generation
class Noeud:
    def __init__(self, prenom, nom):
        self.identite = (prenom, nom)
        self.gauche = None
        self.droite = None
        self.generation = 0
Question 3b

Écrire la fonction récursive numerotation qui parcourt l'arbre et modifie l'attribut generation de tous les ancêtres d'Albert Normand, de sorte que les parents d'Albert Normand soient la génération 1 etc...

Cette fonction prend en paramètres racine_de_l_arbre de type Noeud et num_gen de type entier.

Réponse
def numerotation(racine, num_gen=0):
    if racine != None:
        racine.generation = num_gen
        numerotation(racine.gauche, num_gen+1)
        numerotation(racine.droite, num_gen+1)

On donne la fonction suivante qui prend en paramètres l'objet N de type Noeud et la variable affiche de type booléen :

Fonction mystère
def mystere(N, affiche):
    if N != None:
        if affiche:
            print(N.identite[0])
        mystere(N.gauche, False)
        mystere(N.droite, True)
Question 4

Écrire, dans l'ordre d'affichage, le résultat de l'exécution de mystere(racine_de_l_arbre, False)racine_de_l_arbre est le noeud qui référence Albert Normand.

Réponse

La fonction mystère n'affiche que les prénoms des mères :

Odile
Hélène
Camélia
Marie
Eulalie
Gabrielle
Janet