2022, Amérique du Nord, sujet 1, exercice 3

Thème : Arbres binaires recherche et leurs algorithmes associés

Les arbres binaires de recherche considérés ici sont des arbres binaires où les nœuds désignent des chaines de caractères et pour lesquels la valeur de chaque nœud est supérieure à celles des nœuds de son enfant gauche, et inférieure à celles des nœuds de son enfant droit.

La relation d'ordre notée $<$ est ici la relation d'ordre alphabétique.

Dans cet exercice, les arbres binaires de recherche ne contiennent ques de noms de pays tous distincts.

On considère l'arbre binaire de recherche suivant :

ABR de pays

Question 1a

Donner sans justification la hauteur de cet arbre.

Réponse

La hauteur est $3$

Question 1b

Donner sans justification la valeur booléenne de l'expression "Allemagne" < "Portugal".

Réponse

La valeur booléenne est True

Question 1c

Recopier l'arbre après ajout de "Allemagne", "Portugal" et "Luxembourg" dans cet ordre.

Réponse

Pour les questions 2, 3, et 4, on traite l'arbre initial, donc sans l'ajout de "Allemagne", "Portugal" et "Luxembourg".

Question 2

On souhaite parcourir l'arbre. Indiquer l'ordre de visite des nœuds lors d'un parcours en largeur.

Réponse

Parcourus en largeur les valeurs sont :

"Italie", "France", "Suede", "Autriche", "Hongrie", "Norvage"

On souhaite écrire une fonction pour déterminer si le nom d'un pays est dans l'arbre. On dispose pour cela de :

• la fonction est_vide qui prend en paramètre un arbre arb. Cette fonction renvoie True si l'arbre arbest vide, False sinon ;
• la fonction gauche qui prend en paramètre un arbre arb et renvoie son sous-arbre gauche.

Sous-arbre gauche

Si A est notre arbre initial, gauche(A) renvoie :

• la fonction droit qui prend en paramètre un arbre arb et renvoie son sous-arbre droit.

Sous-arbre droit

Si A est notre arbre initial, droit(A) renvoie :

• la fonction racine qui prend en paramètre un arbre arb et renvoie la valeur de la racine de l'arbre.

Racine

Si A est notre arbre initial, racine(A) renvoie : "Italie"

Question 3

Recopier, en complétant les lignes 2, 6, 7 et 10, la fonction recherche donnée ci-dessous et écrite en Python. Cette fonction prend en paramètres un arbre arb et une valeur val. L'appel recherche(arb, val) renvoie un booléen (True si la valeur val est dans l'arbre arb,False` sinon).

def recherche(arb, val):
    """_ _ _ _ _ _ _ _ _ _ _ _ _"""
    if est_vide(arb):
        return False
    if val == racine(arb):
        return _ _ _ _ _
    if val _ _ _ _ _:
        return recherche(gauche(arb), val)
    else:
        return _ _ _ _ _ _ _ _ _

Réponse

def recherche(arb, val):
    """Renvoie True si val est dans l'arbre arb, False sinon"""
    if est_vide(arb):
        return False
    if val == racine(arb):
        return True
    if val < racine(arb):
        return recherche(gauche(arb), val)
    else:
        return recherche(droit(arb), val)

Question 4

Écrire une fonction récursive taille permettant de déterminer le nombre de pays présent dans un arbre. Cette fonction prendra en paramètre un arbre arb et renverra un entier.

Réponse

def taille(arb):
    """Renvoie un entier qui est le nombre de pays présent dans arb"""
    if est_vide(arb):
        return 0
    else:
        return 1 + taille(gauche(arb)) + taille(droit(arb))

Remarque

Un sujet sans maladresse : le fait de ne pas implémenter via la POO évite le piège de l'arbre ou du nœud valant None avec donc un traitement particulier à faire. Ici, on nous donne une interface sous la forme de fonctions et notamment une fonction est_vide qui nous permet de savoir si l'arbre qu'on traite est vide ou pas ; sans se soucier que cet arbre vide est implémenté par None ou autre chose.