Les arbres binaires

Le corrigé de l’activité se trouve ici

Arbres binaires

Définition

Un arbre binaire est une structure de données abstraite formée d’un ensemble de nœuds organisés hiérarchiquement selon la définition inductive suivante :

Un arbre binaire est :

  • soit un arbre vide, noté $E$, ne contenant aucun nœud ;
  • soit un nœud, appelé racine, relié à exactement deux arbres binaires $g$ et $d$, respectivement appelés sous-arbres gauche et sous-arbre droit.

On note $T(r,g,d)$ l’arbre non vide dont la racine $r$ (on peut aussi indiquer l’étiquette de cette racine).

Vocabulaire et remarques

  • Un nœud dont les deux sous-arbres sont vides est appelé une feuille.
  • Un nœud qui n’est pas une feuille est un nœud interne.
  • Un arbre binaire est dit parfait si toutes les feuilles sont à la même profondeur .
  • La racine d’un arbre $T$ est le seul nœud de $T$ sans parent.

Propriétés

Position des sous-arbres

  • La position des sous-arbres gauche et droite est fondamentale : $$T(r,g,d) \neq T(r,d,g)$$

Taille d’un arbre

  • La taille d’un arbre est égale au nombre de nœuds qu’il comporte.
  • Le nombre de nœuds d’un arbre binaire $T$, noté $n(T)$, se calcule récursivement :
    • $n(E)=0$
    • $n(T)=1+n(g)+n(d)$

Profondeur d’un nœud

  • La profondeur d’un nœud $x$, notée $h(x)$, est sa distance à la racine.
  • La profondeur d’un nœud $x$, notée $h(x)$, est définie récursivement par :
    • $h(\text{racine})=0$
    • $h(x)=1+h(\text{parent de }x)$
  • La profondeur d’un nœud dans un arbre est donc le nombre d’arrêtes qu’il faut parcourir, depuis la racine, pour parvenir au nœud.
La définition de la profondeur d’un nœud peut varier !

Hauteur d’un arbre

  • La hauteur d’un arbre est la profondeur la plus grande atteinte par ses nœuds.
  • La hauteur d’un arbre binaire $T$, notée $h(T)$ est définie récursivement par :
    • $h(E)=-1$
    • $h(T)=1+\mathrm{max}(h(g), h(d))$

Remarque

On peut aussi définir la hauteur d’un nœud : la hauteur d’un nœud est la distance entre ce nœud et la feuille la plus profonde ayant une relation de descendance avec ce nœud.

La définition de la hauteur d’un arbre peut varier !

Relation entre le nombre de nœuds $n$ et la hauteur d’un arbre

  • Soit $T$ un arbre binaire, $n$ son nombre de nœuds et $h$ sa hauteur. Ces grandeurs sont liées par les relations suivantes :

  • $h + 1 \leq n \leq 2^{h+1} - 1$

  • le nombre de sous-arbres vides de $T$ est $n+1$.

  1. Dans quel cas a-t-on $N = h+1$ ?
Réponse

On a $N = h+1$ lorsque chaque nœud ne possède qu’un seul nœud fils. Il s’agit donc d’une structure linéaire (liste).

  1. Dans quel cas a-t-on $N = 2^{h+1} - 1$ ?
Réponse

On a $N = 2^{h+1} - 1$ lorsque l’arbre binaire est parfait, c’est à dire lorsque toutes les feuilles ont la même profondeur.

Spécification des arbres binaires

  • Créer un nœud (type) :
    • fonction : creer_nœud() $\longrightarrow$ retourne un nœud  ;
    • fils_gauche et fils_droit sont automatiquement initialisés à None ;;
    • complexité : $O(0)$ (pas tout à fait vrai mais suffisant pour comprendre la suite).
  • Lire dans le champ valeur :
    • fonction : lire_valeur(n: Noeud[T]) $\longrightarrow$ T ;
    • complexité : 1 opération élémentaire.
  • Écrire dans le champ valeur :
    • fonction : modifier_valeur(n: Noeud[T], valeur: T) $\longrightarrow$ None ;
    • complexité : 1 opération élémentaire.
  • Lire dans le champ fils_gauche :
    • fonction : lire_filsG(n: Noeud[T]) $\longrightarrow$ Noeud[T] ;
    • complexité : 1 opération élémentaire.
  • Écrire dans le champ fils_gauche :
    • fonction : modifier_filsG(n: Noeud[T], m: Noeud[T]) $\longrightarrow$ None ;
    • complexité : 1 opération élémentaire.
  • Lire dans le champ fils_droit :
    • fonction : lire_filsD(n: Noeud[T]) $\longrightarrow$ Noeud[T] ;
    • complexité : 1 opération élémentaire.
  • Écrire dans le champ fils_droit :
    • fonction : modifier_filsD(n: Noeud[T], m: Noeud[T]) $\longrightarrow$ None ;
    • complexité : 1 opération élémentaire.
Tout comme on a désigné les listes chaînées par leur première cellule, on va désigner les arbres par leur nœud racine.

Implémentation de la spécification en Python

Il existe de nombreuses façons de d’implémenter la structure d’arbre en Python. Dans cette partie on va utiliser une classe.

Le paradigme de programmation utilisé ci-dessous est le paradigme impératif : on crée dans un premier temps une structure élémentaire à l’aide d’une classe et on définit ensuite des fonctions qui manipulent cette structure.
On ne crée pas de structure arbre binaire (accompagnée de méthodes).

  1. Écrire le code de la classe Noeud respectant la spécification. Les trois attributs seront nommés valeur, gauche, droit.

  2. Écrire le code permettant de construire l’arbre : 

    graph TD
  A("A") --- B("B")
  B --- G(None)
  B --- C("C")
  C --- H(None)
  C --- I(None)
  A --- D("D")
  D --- E(None)
  D --- F(None)

Réponse 
1
2
3
4
5
6

arbre_1 = Noeud('A',
                Noeud('B',
                        None,
                        Noeud('C')),
                Noeud('D')
                )
  1. Quel arbre correspond à ce code ?
1
2
3

Noeud('r', Noeud('a', Noeud('c', None, Noeud('h')), Noeud('d', Noeud('i'),
 Noeud('j', Noeud('m'), None))), Noeud('b', Noeud('e', Noeud('k', None, None),
  None), Noeud('f')))
Réponse
  1. Écrire la spécification et le code de la fonction est_vide dont la spécification est :
1
2
3
4

def est_vide(n: Noeud) -> bool:
    """
    Teste si un arbre est vide.
    """
  1. Écrire la spécification et le code de la fonction ajoute_filsG dont la spécification est :
1
2
3
4

def ajoute_filsG(n: Noeud, valeur: str) -> None:
    """
    Ajoute un noeud d'étiquette valeur comme fils gauche. 
    """
  1. Écrire la spécification et le code de la fonction ajoute_filsD dont la spécification est :
1
2
3
4

def ajoute_filsD(n: Noeud, valeur: str) -> None:
    """
    Ajoute un noeud d'étiquette valeur comme fils droit. 
    """
  1. Écrire la spécification et le code de la fonction est_feuille dont la spécification est :
1
2
3
4

def est_feuille(n: Noeud) -> bool:
    """
    Teste si un noeud est une feuille.
    """
  1. Écrire la spécification et le code de la fonction degre_noeud dont la spécification est :
1
2
3
4

def degre_noeud(n: Noeud) -> int:
    """
    Détermine le degré du noeud passé en argument.
    """
Réponses aux questions précédentes 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

from __future__ import annotations


class Noeud():
    """
    Implémentation d'un noeud.
    """

    def __init__(self: Noeud,
                 valeur: str,
                 gauche: Noeud = None,
                 droit: Noeud = None) -> None:
        self.valeur = valeur
        self.gauche = gauche
        self.droit = droit


def est_vide(n: Noeud) -> bool:
    """
    Teste si un arbre est vide.
    """
    return n is None


def ajoute_filsG(n: Noeud, valeur: str) -> None:
    """
    Ajoute un noeud d'étiquette valeur comme fils gauche. 
    """
    if est_vide(n.gauche):
        new_n = Noeud(valeur)
        n.gauche = new_n
    else:
        raise Exception("Noeud possède déjà un fils à gauche.")


def ajoute_filsD(n: Noeud, valeur: str) -> None:
    """
    Ajoute un noeud d'étiquette valeur comme fils droit. 
    """
    if est_vide(n.droit):
        new_n = Noeud(valeur)
        n.droit = new_n
    else:
        raise Exception("Noeud possède déjà un fils à droite.")


def est_feuille(n: Noeud) -> bool:
    """
    Teste si un noeud est une feuille.
    """
    return est_vide(n.gauche) and est_vide(n.droit)


def degre_noeud(n: Noeud) -> int:
    """
    Détermine le degré du noeud passé en argument.
    """
    nbre = 0
    if not est_vide(nbre.gauche):
        nbre += 1
    if not est_vide(nbre.droit):
        nbre += 1
    return nbre


if __name__ == "__main__":
    n1 = Noeud('A')
    ajoute_filsG(n1, 'B')
    ajoute_filsD(n1.gauche, 'C')
    ajoute_filsD(n1, 'D')

    print("Pour n1, D est-il une feuille : {}".format(est_feuille(n1.droit)))
    print("Pour n1, B est-il une feuille : {}".format(est_feuille(n1.gauche)))
    print("Pour n1, C est-il une feuille : {}".format(est_feuille(n1.gauche.droit)))

    print("Degré de la racine : {}".format(degre_noeud(n1)))
    print("Degré de B : {}".format(degre_noeud(n1.gauche)))
    print("Degré de D : {}".format(degre_noeud(n1.droit)))
    print("Degré de C : {}".format(degre_noeud(n1.gauche.droit)))

Quelques algorithmes de manipulation des arbres binaires

Algorithmes récursifs

  1. Écrire la spécification et le code de la fonction taille dont la spécification est :
1
2
3
4

def taille(n: Noeud) -> int:
    """
    Retourne le nombre de noeud dans l'arbre.
    """
Réponse 
1
2
3
4
5
6
7
8

def taille(n: Noeud) -> int:
    """
    Retourne le nombre de noeud dans l'arbre depuis le noeud n
    """
    if est_vide(n):
        return 0
    else:
        return 1 + taille(n.gauche) + taille(n.droit)
  1. Écrire la spécification et le code de la fonction profondeur dont la spécification est :
1
2
3
4

def profondeur(n: Noeud) -> int:
    """
    Retourne la profondeur de l'arbre. 
    """
Réponse 
1
2
3
4
5
6
7
8

def profondeur(n: Noeud) -> int:
    """
    Retourne la profondeur de l'arbre 
    """
    if est_vide(n):
        return 0
    else:
        return 1 + max(profondeur(n.gauche), profondeur(n.droit))
  1. Écrire la spécification et le code de la fonction nbre_feuilles dont la spécification est :
1
2
3
4

def nbre_feuilles(n: Noeud) -> int:
    """
    Détermine le nombre de feuilles dans l'arbre. 
    """
Réponse 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def nbre_feuilles(n: Noeud) -> int:
    """
    Détermine le nombre de feuilles dans l'arbre. 
    """
    if est_vide(n):  # Cas des nœuds de degré 1 (ou de l'arbre vide)
        return 0
    elif est_feuille(n):
        return 1
    else:
        return 0 + nbre_feuilles(n.gauche) + nbre_feuilles(n.droit)
  1. Quelles sont les complexités des algorithmes implémentés dans cette section ?
Réponse

Les algorithmes parcourent une fois chaque nœud de l’arbre. La complexité est donc proportionnelle au nombre de nœuds.

Parcours en profondeur d’un arbre

Les fonction écrites jusqu’à présent parcourent en profondeur tous les nœuds des arbres sans que l’ordre dans lequel ce parcourt est effectué ait la moindre importance.

Si on souhaite donner un affichage de l’arbre, la façon dont on le parcourt prend alors une grande importance. On peut :

  • Parcourir le sous-arbre gauche, afficher la valeur du nœud puis enfin parcourir le sous-arbre droit. On parle d’un parcours infixe.
  • Afficher la valeur de chaque nœud avant de parcourir les sous-arbres. On parle d’un parcours préfixe.
  • Parcourir les sous-arbres puis afficher les valeurs. On parle d’un parcours suffixe.
  1. Pour l’arbre ci-dessous, donner les parcours préfixe, infixe et suffixe.
graph TD
    0(0) --- 1(1)
    0 --- 8(8)
    1 --- 2(2)
    2 --- 3(3)
    2 --- A(None)
    1 --- 4(4)
    4 --- 5(5)
    4 --- 6(6)
    6 --- B(None)
    6 --- 7(7)
    8 --- 9(9)
    8 --- 13(13)
    9 --- C(None)
    9 --- 10(10)
    10 --- 11(11)
    10 --- 12(12)
    13 --- 14(14)
    13 --- 15(15)
    3 --- D(None)
    3 --- E(None)
    5 --- F(None)
    5 --- G(None)
    7 --- H(None)
    7 --- I(None)
    11 --- J(None)
    11 --- K(None)
    12 --- L(None)
    12 --- M(None)
    14 --- O(None)
    14 --- P(None)
    15 --- Q(None)
    15 --- R(None)
Réponses
  • Préfixe : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
  • Infixe : 3, 2, 1, 5, 4, 6, 7, 0, 9, 11, 10, 12, 8, 14, 13, 15
  • Suffixe : 3, 2, 5, 7, 6, 4, 1, 11, 12, 10, 9, 14, 15, 13, 8, 0
  1. Écrire les spécifications et le code des fonctions affiche_infixe, affiche_prefixe et affiche_suffixe dont les spécifications sont :
1
2
3
4

def affiche_infixe(n: Noeud) -> None:
    """
    Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
    """

1
2
3
4

def affiche_prefixe(n: Noeud) -> None:
    """
    Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
    """

1
2
3
4

def affiche_suffixe(n: Noeud) -> None:
    """
    Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
    """

Algorithmes itératifs

  1. Reprendre les questions précédentes en utilisant des algorithmes itératifs.

Parcours d’un arbre à l’aide d’une file ou d’une pile

Parcours en largeur d’un arbre

  1. Décrire le fonctionnement de l’algorithme suivant et montrer qu’il réalise un parcours en largeur d’un arbre.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

Fonction parcours_largeur(racine: Noeud):
    File f = newFile()
    f.enfiler(racine)
    TantQue non f.est_vide():
        n = f.defiler()
        print(n.valeur)
        Si non est_vide(n.filsG):
            f.enfiler(n.filsG)
        FinSi
        Si non est_vide(n.filsD):
            f.enfiler(n.filsD)
        FinSi
    FinTantQue
FinFonction
  1. Implémenter en Python l’algorithme précédent.

Parcours en profondeur d’un arbre

  1. Décrire le fonctionnement de l’algorithme suivant et montrer qu’il réalise un parcours en profondeur d’un arbre. De quel type de parcours en profondeur s’agit-il ?
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

Fonction parcours_profondeur(racine: Noeud):
    Pile p = newPile()
    p.empiler(racine)
    TantQue non est_vide(p):
        n = p.depiler()
        print(n)
        Si non est_vide(n.filsG):
            empiler(n.filsG)
        FinSi
        Si non est_vide(n.filsD):
            empiler(n.filsD)
        FinSi
    FinTantQue
FinFonction
  1. Implémenter en Python l’algorithme précédent.

À retenir

Un arbre binaire est un ensemble fini de nœuds, qui est soit vide, soit structuré à partir d’un nœud particulier, appelé racine de l’arbre, et de deux sous-ensembles de nœuds formant récursivement un sous-arbre gauche et un sous-arbre droit. Un arbre peut-être implémenté en Python avec un objet par nœud, d’une classe qui possède trois attributs : la valeur (ou étiquette) du nœud, le sous-arbre gauche et le sous-arbre droit. La valeur None est utilisée pour représenter l’arbre vide.
Arbres  Arbres binaires 

Voir également