Exercice 4 · Bac Numérique et Sciences Informatiques Amérique du Nord 2022 (jour 2)

Exercice 4 (4 points)

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

Un éleveur de chiens gère les informations sur ses animaux à l'aide d'un logiciel qui mémorise le pédigrée de chacun de ses chiens. Le pédigrée d'un chien correspond à son arbre généalogique. Une structure arbre de pédigrée est définie récursivement, soit par un arbre vide, noté $\emptyset$, soit par un arbre binaire où:

la valeur du nœud est une chaîne de caractères qui représente le nom de l'animal;

le sous-arbre gauche est l'arbre de pédigrée du père du chien;

le sous-arbre droit est l'arbre de pédigrée de la mère du chien.

On représente donc graphiquement un arbre de pédigrée comme l'arbre A suivant:

Pour alléger la représentation d'un arbre de pédigrée, on ne notera pas les arbres vides, l'arbre précédent sera donc représenté comme ci-dessous.

Dans cet arbre,

le père de Mango est Domino et sa mère Pinkie;

les parents de Douchka ne sont pas connus;

Iris est la mère de Pinkie;

la mère de Tango n'est pas connue.

Pour manipuler les arbres de pédigrée, on dispose des quatre fonctions suivantes:

La fonction racine qui prend en paramètre un arbre de pédigrée non vide et renvoie la valeur de la racine.

Exemple: en reprenant l'exemple d'arbre de pédigrée A, racine(A) vaut "Mango".

La fonction gauche qui prend en paramètre un arbre de pédigrée non vide et renvoie son sous-arbre gauche correspondant à l'arbre de pédigrée du père.

Exemple: en reprenant l'exemple d'arbre de pédigrée A, gauche(A) est l'arbre représenté graphiquement ci-après:

La fonction droit qui prend en paramètre un arbre de pédigrée non vide et renvoie son sous-arbre droit correspondant à l'arbre de pédigrée de la mère.

Exemple: en reprenant l'exemple d'arbre de pédigrée A, droit(A) vaut l'arbre représenté graphiquement ci-après:

La fonction est_vide qui prend en paramètre un arbre de pédigrée et renvoie True si l'arbre est vide ou False sinon.

Exemple: en reprenant l'exemple d'arbre de pédigrée A, est_vide(A) vaut False.

Pour toutes les questions de l'exercice, on suppose que tous les chiens d'un même pédigrée ont un nom différent.

1.

On considère l'arbre de pédigrée B suivant:

a)

b)

On appelle feuille d'un arbre de pédigrée, un nœud dont les sous-arbres gauche et droit sont vides.

c)

d)

2.

a)

Recopier et compléter la fonction récursive Python present ayant pour paramètres un arbre de pédigrée arb et le nom d'un chien nom et qui renvoie True si ce nom est présent dans l'arbre de pédigrée ou False sinon.

def present(arb, nom):

if est_vide(arb):

return...

elif racine(arb) ==...:

return...

else:

return present(...,...) or present(...,...)

Pour toute la suite de l'exercice, on pourra utiliser la fonction present même si la question 2.(a) n'a pas été traitée.

b)

Écrire une fonction Python parents ayant pour paramètre un arbre de pédigrée arbre d'un chien et qui renvoie le p-uplet des deux parents de ce chien dans l'ordre père, mère. Si un des parents est inconnu, il sera noté "".

Exemple: parents(B) vaut ("Eclair", "Nougat").

3.

a)

On dit que deux chiens sont frères et sœurs s'ils ont le même père ou la même mère. On considère les trois arbres de pédigrée suivants:

b)

Écrire une fonction Python frere_soeur ayant pour paramètres deux arbres de pédigrée arbre1 et arbre2 correspondant à deux chiens. Cette fonction renvoie True si les deux chiens ont le même père ou la même mère ou False sinon.

4.

Étant donné l'arbre de pédigrée d'un chien, on considère que:

le niveau 0 est le niveau de la racine contenant le nom du chien;

le niveau 1 est le niveau des parents du chien;

le niveau 2 est le niveau des grands-parents du chien;

etc.

Proposer une fonction Python nombre_chiens ayant pour paramètres un arbre de pédigrée arb et un entier n et qui renvoie le nombre de noms connus dans l'arbre de pédigrée arb au niveau n.

Exemple: nombre_chiens(B, 3) vaut 4 car les noms des chiens mentionnés dans l'arbre de pédigrée au niveau 3 sont "Ulk", "Maya", "Museau" et "Noisette".