Parcours d'arbre binaire de recherche⚓︎

D'après 2022, Métropole, septembre, J1, Ex. 1

Arbre binaire de recherche

On rappelle qu'un Arbre Binaire de Recherche (ABR) est :

soit un arbre vide
soit composé d'une racine étiquetée d'une clé, d'un sous arbre à droite et d'un sous arbre à gauche, tous deux ABR également.
Les clés du sous-arbre à gauche sont inférieures ou égales à celle de la racine.
Les clés du sous arbre à droite sont strictement supérieures à celle de la racine.

Partie A : Préambule⚓︎

1. Recopier sur votre copie le ou les numéro(s) correspondant aux arbres binaires de recherche parmi les arbres suivant :


flowchart TD
    subgraph "Arbre 3"
    N31(3) --> N32(2)
    N31 --> N33(4)
    N32 --> N34(1)
    N32 --> N35(1)
    N33 --> N36(4)
    N33 --> N37(5)
    end

    subgraph "Arbre 2"
    N21(4) --> N22(2)
    N21 --> N23(4)
    N22 --> N24(1)
    N22 --> N25(3)
    N23 --> N26(4)
    N23 --> N27(5)
    end

    subgraph "Arbre 1"
    N11(3) --> N12(2)
    N11 --> N13(4)
    N12 --> N14(1)
    N12 --> N15(3)
    N13 --> N16(4)
    N13 --> N17(5)
    end

Réponse

Seul l'arbre 1 est un ABR.
L'arbre 2 contient des clés égales à 4 dans le sous arbre à droite et la racine a pour clé 4.
L'arbre 3 contient une clé égale à 1 à droite de la clé 2.

Partie B : Analyse⚓︎

On considère la structure de données abstraites ABR (Arbre Binaire de Recherche) que l'on munit des opérations suivantes :

Structure de données : ABR

Utilise : Booléen, Element Opérations :

arbre_vide : ∅ → ABR
- arbre_vide() renvoie un arbre vide
est_vide : ABR → Booléen
- est_vide(arbre) renvoie True si l'arbre est vide et False sinon.
racine : ABR → Element
- racine(arbre) renvoie la clé de la racine de l'arbre s'il est non vide.
s_a_gauche : ABR → ABR
- s_a_gauche(arbre) renvoie le sous arbre à gauche de l'arbre s'il est non vide.
s_a_droite : ABR → ABR
- s_a_droite(a) renvoie le sous arbre à droite de l'arbre s'il est non vide.
inserer : ABR, Element → Rien
- inserer(arbre, e) insère la clé e dans l'arbre.

2.a) Dans un ABR non vide, où se trouve le plus petit élément ? Justifier.

Réponse

Le plus petit élément se trouve le plus à gauche dans un ABR non vide.

En effet, dès qu'on emprunte un sous arbre à droite, les valeurs des clés augmentent.

Pour rechercher une valeur dans un ABR non vide, il faut comparer la valeur avec la clé située à la racine. Si cette valeur est à la racine, la fonction renvoie True, sinon il faut procéder récursivement sur un sous arbre à gauche ou à droite.

2.b) En utilisant les fonctions ci-dessus, écrire une fonction récursive recherche_valeur prenant en arguments la valeur recherchée et l'arbre binaire de recherche considéré. Cette fonction renvoie un booléen indiquant si la valeur est présente dans l'arbre ou non.

Réponse

🐍 Script Python

def recherche_valeur(valeur, arbre):
    if est_vide(arbre):
        return False
    elif valeur == racine(arbre):
        return True
    elif valeur < racine(arbre):
        suite = s_a_gauche(arbre)
    else:
        suite = s_a_droite(arbre)
    return recherche_valeur(valeur, suite)

3. On considère l'ABR ci-dessous :

graph TD
    classDef invisible opacity:0;
    subgraph " "
    N1(7) --> N2(2)
    N1 --> N3(10)
    N2 --> N4(1)
    N2 --> N5(5)
    N3 --> N6(8)
    N3 -.-> N7( ):::invisible

    N5 --> N10(3)
    N5 --> N11(6)
    N6 -.-> N12( ):::invisible

    N6 --> N13(9)
    end

3.a) Dire à quel type de parcours correspond le résultat suivant où les clés sont triées dans l'ordre croissant :

1 - 2 - 3 - 5 - 6 - 7 - 8 - 9 - 10

Réponse

Le parcours infixe renvoie la liste croissante des clés d'un ABR.

La clé n'est affichée qu'après le parcours du sous arbre à gauche et avant de parcourir le sous arbre à droite.

3.b) Donner le parcours préfixe de cet arbre.

Réponse

Le parcours préfixe renvoie la clé de chaque nœud visité avant de parcourir le sous arbre à gauche puis le sous arbre à droite.

On obtient donc : 7 - 2 - 1 - 5 - 3 - 6 - 10 - 8 - 9

3.c) Donner le parcours suffixe de cet arbre.

Réponse

Le parcours suffixe parcourt d'abord le sous arbre à gauche, puis le sous arbre à droite et enfin renvoie la clé du nœud visité.

On obtient donc : 1 - 3 - 6 - 5 - 2 - 9 - 8 - 10 - 7

3.d) Donner le parcours en largeur de cet arbre.

Réponse

Le parcours en largeur renvoie la liste des clés d'un ABR en fonction de leur éloignement à la racine.

On obtient d'abord la clé de la racine, puis la clé de la racine du sous-arbre à gauche et celle du sous-arbre à droite, puis celle des sous-arbres des sous-arbres.

On obtient donc : 7 - 2 - 10 - 1 - 5 - 8 - 3 - 6 - 9