Aller au contenu

Arbres binaires

On pourra utiliser sans justification supplémentaire les fonctions vues en tp suivantes : est_vide, est_feuille, etiquette, gauche, droit. Afin d'illustrer les résultats attendus pour chaque exercice, on donne ci-dessous quatre arbres \(\mathcal{A}_1\), \(\mathcal{A}_2\), \(\mathcal{A}_3\), \(\mathcal{A}_{4}\).

img

Arbre parfait

Un arbre binaire est dit parfait lorsque toutes les feuilles sont à la même profondeur de la racine. Il s'agit d'un arbre dont tous les niveaux sont remplis : tous les noeuds internes ont deux enfants.

On considère dans cet exercice que l'arbre vide est un arbre parfait. Par exemple, l'arbre \(\mathcal{A}_1\) est parfait, les autres arbres ne le sont pas.

Compléter le code de la fonction python est_parfait afin que celle-ci renvoie True si et seulement si l'arbre binaire a (éventuellement vide) est parfait. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def est_parfait(a):
    if est_vide(a):
        return True
    # elif est_vide(gauche(a)) and not est_vide(droit(a)):
    #     return False
    # elif est_vide(droit(a)) and not est_vide(gauche(a)):
    #     return False
    else:
        est_parfait_sag = est_parfait(gauche(a))
        est_parfait_sad = est_parfait(droit(a))
        # ^ est l'opérateur xor (ou exclusif) :
        # True  ^ True  -> False
        # False ^ True  -> True
        # True  ^ False -> True
        # False ^ False -> False
        # si l'un des deux enfants (mais pas les deux)
        # est vide alors l'arbre n'est pas parfait.
        if est_vide(gauche(a)) ^ est_vide(droit(a)):
            return False
        else:
            return est_parfait_sag and est_parfait_sad

Peigne

On dit d'un arbre binaire qu'il est un peigne lorsqu'il ne possède qu'une unique feuille. Il s'agit d'un arbre possédant un seul nœud par niveau : tous les nœuds internes ne possèdent qu'un enfant.

On considère dans cet exercice que l'arbre vide est un peigne. Par exemple, l'arbre \(\mathcal{A}_3\) est un peigne, les autres arbres ne le sont pas.

Compléter le code de la fonction python est_peigne afin que celle-ci renvoie True si et seulement si l'arbre binaire a (éventuellement vide) est un peigne. 

1
2
3
4
5
6
7
def est_peigne(a):
    """ Arbre -> bool
    Détermine si l'arbre binaire a est peigne """
    if est_vide(a):
        return True
    else:
        return (est_peigne(gauche(a)) and est_vide(droit(a))) or (est_peigne(droit(a)) and est_vide(gauche(a)))

Nombre de feuilles d'un arbre

Écrire une fonction python nb_feuilles qui étant donné un arbre a (supposé non vide) compte le nombre de feuilles de l'arbre a.

Par exemple, \(\mathcal{A}_1\) possède quatre feuilles, \(\mathcal{A}_2\) possède trois feuilles, \(\mathcal{A}_3\) possède une feuille et \(\mathcal{A}_4\) possède deux feuilles. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def nb_feuilles(a):
    """ Arbre -> int
    Renvoie le nombre de feuilles de l'arbre a
    a est supposé non vide. """
    if est_feuille(a):
        return 1
    elif est_vide(gauche(a)):
        return nb_feuilles(droit(a))
    elif est_vide(droit(a)):
        return nb_feuilles(gauche(a))
    else:
        return nb_feuilles(gauche(a)) + nb_feuilles(droit(a))

Parcours d'arbre

  1. Donner la liste des étiquettes de \(\mathcal{A}_1\) lorsque celui-ci est parcouru en profondeur d'abord, dans l'ordre préfixe.

    0 -5 -3 1 4 -3 5

  2. Donner la liste des étiquettes de \(\mathcal{A}_2\) lorsque celui-ci est parcouru en profondeur d'abord, dans l'ordre infixe.

    4 -2 -3 5 -1 -1 6 -5

  3. Donner la liste des étiquettes de \(\mathcal{A}_4\) lorsque celui-ci est parcouru en profondeur d'abord, dans l'ordre postfixe.

    -5 -3 -2 6 8 -4 5