Kursliste Logg inn

Informasjon

Forfatter(e) Pierre Dupont
Frist 19/08/2025 13:15:00
Innleveringsgrense Ingen begrensning

Logg inn

Logg inn

Tâche 3


On vous demande d'écrire le corps de la fonction count_bst(...) qui retourne le nombre d'occurrences
d'une clé key passée en paramètre dans un arbre binaire, sachant que l'arbre satisfait l'invariant d'un arbre binaire de recherche (ABR).

def count_bst(tree, key):
    """
    pre: 'tree' une instance de BinaryTree vérifiant l'invariant d'un ABR
    post: renvoie le nombre d'occurrences de 'key' dans 'tree'.

          L'arbre `tree`, passé en argument, ne peut *pas* être modifié.
    """
On vous demande d'écrire le corps de la fonction count_bst en respectant les spécifications de cette fonction.
Vous pouvez faire l'hypothèse que les préconditions de cette fonction sont vérifiées et votre code sera testé sous cette hypothèse.

Notez que votre code Python (sous-question 4) ne sera évalué que lorsque vous aurez correctement répondu aux sous-questions de validation proposées.
Ces exercices de validation ont pour but d'assurer que vous avez correctement compris la représentation d'un ABR et les spécifications de la fonction count_bst.

Vous êtes invité.e à répondre à ces questions de validation et à cliquer sur submit avant toute modification du corps de la fonction count_bst (sous-question 4).

Spørsmål 1: Question de validation 1
L'invariant d'un ABR impose où une clé peut être mémorisée dans l'arbre, relativement aux autres clés présentes dans l'arbre.
Parmi les 2 arbres suivants, lequel satisfait l'invariant d'un ABR ?


Arbre 1 :

https://inginious.info.ucl.ac.be/course/LINFO1103-0825/exam_3/bt_2B.png

Arbre 2 :

https://inginious.info.ucl.ac.be/course/LINFO1103-0825/exam_3/bt_2.png

Répondez 0 si aucun de ces 2 arbres ne satisfait l'invariant d'un ABR, répondez 1 si le premier arbre est un ABR, répondez 2 si le second arbre est un ABR.

Note: votre réponse ne doit contenir qu'un nombre, ni espace, ni ponctuation.
Spørsmål 2: Question de validation 2
L'arbre binaire dessiné ci-dessous satisfait l'invariant d'un ABR.

https://inginious.info.ucl.ac.be/course/LINFO1103-0825/exam_3/bt_4.png

Observez où se trouve la clé 7 dans cet ABR.
Quel est le nombre d'occurrences de cette clé dans cet ABR ?


Note: votre réponse ne doit contenir qu'un nombre, ni espace, ni ponctuation.
Spørsmål 3: Question de validation 3
Que doit renvoyer la fonction count_bst si on l'appelle avec key = 3 dans l'ABR dessiné ci-dessous ?

https://inginious.info.ucl.ac.be/course/LINFO1103-0825/exam_3/bt_2.png


Spørsmål 4: Code python à produire

On vous demande d'écrire le corps de la fonction count_bst en respectant les spécifications de cette fonction.

Attention : votre implémentation doit être récursive pour être efficace et obtenir la bonne profondeur de la récursion en utilisant l'invariant d'un ABR (il faut donc tirer parti dans votre implémentation de l'ordre particulier sur les clés mémorisées dans un ABR).

Pour répondre à cette sous-question, vous avez besoin d'une implémentation d'un arbre binaire.
Une implémentation d'un arbre binaire sous la forme d'une classe BinaryTree vous est fournie en suivant ce lien.
Cette classe a été importée pour vous.
Dès lors, dans le code de la fonction count_bst, vous pouvez faire directement appel aux méthodes de la classe BinaryTree.

Par défaut, vous êtes invité.e à écrire et tester votre code préalablement et, lorsque vous serez prêt.e, vous devrez copier/coller le corps de la fonction count_bst ci-dessous. Vous pouvez tester votre code en utilisant l'interpréteur python disponible dans une console de test. Attention: c'est le code que vous soumettrez ci-dessous qui sera évalué, pas celui de vos tests (donc pas ceux de la console de test).

Les évaluations de votre implémentation sont faites en supposant les préconditions de count_bst vérifiées.

def count_bst(tree, key):
    """
    pre: 'tree' une instance de BinaryTree vérifiant l'invariant d'un ABR
    post: renvoie le nombre d'occurrences de 'key' dans 'tree'.

          L'arbre `tree`, passé en argument, ne peut *pas* être modifié.
    """

Copiez-collez le corps de votre fonction (pas la signature qui est la première ligne commençant par def) en lieu et place du mot clé pass ci-dessous.