Exercice 4 · Bac Numérique et Sciences Informatiques Mayotte-Liban 2022 (jour 1)

Cet exercice porte sur l'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.

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 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 N de type Noeud, dont on ne connaît pas les parents, on considérera que N.gauche et N.droit ont la valeur None.

1.

a)

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

b)

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

2.

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.

a)

b)

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:

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.droit)

c)

d)

3.

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.

a)

class Noeud():

def __init__ (prenom, nom):

self.identite = (prenom, nom)

self.gauche = None

self.droite = None

b)

É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.

4.

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

def mystere(N, affiche):

if N != None:

if affiche:

print( N.identite[0])

mystere(N.gauche, False)

mystere(N.droit, True)