Aller au contenu principal
Physique, Chimie et Informatique > Terminales Spé. NSI > Structures hiérarchiques : les arbres

Les arbres binaires

Arbres binaires

Définition

À retenir

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 par récurrence suivante :

Un arbre binaire est :

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

On note T(r,g,d)T(r,g,d) l’arbre non vide dont la racine rr (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 TT est le seul nœud de TT sans parent.

Propriétés

Position des sous-arbres
  • La position des sous-arbres gauche et droite est fondamentale : T(r,g,d)≠T(r,d,g)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 TT, noté n(T)n(T), se calcule récursivement :
    • n(E)=0n(E)=0
    • n(T)=1+n(g)+n(d)n(T)=1+n(g)+n(d)
Profondeur d’un nœud
  • La profondeur d’un nœud nn, notée h(n)h(n), est sa distance à la racine.
  • La profondeur d’un nœud nn, notée h(n)h(n), est définie récursivement par :
    • h(racine)=0h(\text{racine})=0
    • h(n)=1+h(parent de n)h(n)=1+h(\text{parent de }n)
  • 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.
Avertissement

La définition de la profondeur d’un nœud peut varier ! Il est impératif de vérifier celle choisie avant tout travail.

Hauteur d’un arbre
  • La hauteur d’un arbre est la profondeur du nœud le plus éloigné de la racine.
    La hauteur d’un arbre est aussi sa profondeur.
  • La hauteur d’un arbre binaire TT, notée h(T)h(T) est définie récursivement par :
    • h(E)=−1h(E)=-1 si l’arbre est vide ;
    • h(T)=1+max(h(g),h(d))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.

Avertissement

La définition de la hauteur d’un arbre peut varier ! Il est impératif de vérifier celle choisie avant tout travail.

Relation entre le nombre de nœuds nn et la hauteur d’un arbre
  • Soit TT un arbre binaire, nn son nombre de nœuds et hh sa hauteur. Ces grandeurs sont liées par les relations suivantes :

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

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

  1. Dans quel cas a-t-on N=h+1N = h+1 ?

    Réponse

    On a N=h+1N = 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).

  2. Dans quel cas a-t-on N=2h+1−1N = 2^{h+1} - 1 ?

    Réponse

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

Spécification d’un arbre binaire

À retenir
  • 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)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.
Avertissement

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 à l’aide d’une classe

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

Avertissement

Le paradigme de programmation utilisé ci-dessous est le paradigme impératif : on crée dans un premier temps une structure élémentaire qui ne sert qu’à stocker les différentes valeurs et on définit ensuite des fonctions qui manipulent cette structure.

La structure utilisée peut être :

  • Une classe qui définit trois attributs valeur, gauche et droit et aucune méthode ;
  • Une liste Python de trois éléments ;
  • Un dictionnaire comportant trois clés : valeur, gauche et droit.

On peut même imaginer utiliser un tableau ou une liste chaînée !

On ne créera pas de structure « arbre binaire » (accompagnée de méthodes) dans ce document.

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


class Noeud:
    """
    Structure de stockage pour créer des arbres binaires.
    """

    def __init__(self: Noeud, val: str, g: Noeud = None, d: Noeud = None) -> None:
        """Initialisation de l'objet."""
        self.valeur = val
        self.gauche = g
        self.droit = d
  1. É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
arbre_1 = Noeud("A", Noeud("B", None, Noeud("C")), Noeud("D"))

ou

abr1 = Noeud("A")
abr1.gauche = Noeud("B")
abr1.droit = Noeud("D")
abr1.gauche.droit = Noeud("C")
  1. Quel arbre correspond à ce code ?
abr = 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

Écrire le code différemment en créant les nœuds les uns après les autres.

Réponse
abr = Noeud("r")
abr.gauche = Noeud("a")
abr.droit = Noeud("b")
abr.gauche.gauche = Noeud("c")
abr.gauche.droit = Noeud("d")
abr.gauche.gauche.droit = Noeud("h")
abr.gauche.droit.gauche = Noeud("i")
abr.gauche.droit.droit = Noeud("j")
abr.gauche.droit.droit.gauche = Noeud("m")
abr.droit.gauche = Noeud("e")
abr.droit.gauche.gauche = Noeud("k")
abr.droit.droit = Noeud("f")
  1. Écrire le code de la fonction est_vide dont la spécification est :
def est_vide(n: Noeud) -> bool:
    """
    Teste si un arbre est vide.
    """
Réponse
def est_vide(n: Noeud) -> bool:
    """
    Teste si un arbre est vide.
    """
    return n == None
  1. Écrire le code de la fonction ajoute_filsG dont la spécification est :
def ajoute_filsG(n: Noeud, valeur: str) -> None:
    """
    Ajoute un noeud d'étiquette valeur comme fils gauche.
    """
Réponse
def ajoute_filsG(n: Noeud, valeur: str) -> None:
    """
    Ajoute un noeud d'étiquette valeur comme fils gauche.
    """
    if est_vide(n.gauche):
        n.gauche = Noeud(valeur)
    else:
        raise Exception("Le nœud possède déjà un fils gauche !")
  1. Écrire le code de la fonction ajoute_filsD dont la spécification est :
def ajoute_filsD(n: Noeud, valeur: str) -> None:
    """
    Ajoute un noeud d'étiquette valeur comme fils droit.
    """
Réponse
def ajoute_filsD(n: Noeud, valeur: str) -> None:
    """
    Ajoute un noeud d'étiquette valeur comme fils droit.
    """
    if est_vide(n.droit):
        n.droit = Noeud(valeur)
    else:
        raise Exception("Le nœud possède déjà un fils droit !")
  1. Écrire le code de la fonction est_feuille dont la spécification est :
def est_feuille(n: Noeud) -> bool:
    """
    Teste si un noeud est une feuille.
    """
Réponse
def est_feuille(n: Noeud) -> bool:
    """
    Teste si un noeud est une feuille.
    """
    return est_vide(n.gauche) and est_vide(n.droit)
  1. Écrire le code de la fonction degre_noeud dont la spécification est :
def degre_noeud(n: Noeud) -> int:
    """
    Détermine le degré du noeud passé en argument.
    """

Quelques algorithmes de manipulation des arbres binaires

Tous les algorithmes qui suivent sont récursifs.

  1. Écrire le code de la fonction taille dont la spécification est :
def taille(n: Noeud) -> int:
    """
    Retourne le nombre de noeud dans l'arbre.
    """
Réponse
def taille(n: Noeud) -> int:
    """
    Retourne le nombre de noeud dans l'arbre.
    """
    if est_vide(n):
        # Cas de base : un arbre vide ne contient aucun noeud.
        return 0
    else:
        # Recherche récursive dans les sous-arbres gauche et droit.
        taille_gauche = taille(n.gauche)
        taille_droit = taille(n.droit)

        # Calcul de la taille
        return 1 + taille_gauche + taille_droit
  1. Écrire le code de la fonction profondeur dont la spécification est :
def profondeur(n: Noeud) -> int:
    """
    Retourne la profondeur de l'arbre.
    """
Réponse
def profondeur(n: Noeud) -> int:
    """
    Retourne la profondeur de l'arbre.
    """
    if est_vide(n):
        # Cas de base : si le nœud est vide, il n'est pas dans l'arbre.
        return -1
    else:
        # Recherche récursive dans les sous-arbres gauche et droit.
        arbre_gauche = profondeur(n.gauche)
        arbre_droit = profondeur(n.droit)

        # Détermine la profondeur
        return 1 + max(arbre_gauche, arbre_droit)
  1. Écrire le code de la fonction nbre_feuilles dont la spécification est :
def nbre_feuilles(n: Noeud) -> int:
    """
    Détermine le nombre de feuilles dans l'arbre.
    """
Réponse
def nbre_feuilles(n: Noeud) -> int:
    """
    Détermine le nombre de feuilles dans l'arbre.
    """
    if est_vide(n):
        # Cas de base : un arbre vide ne contient aucune feuille
        return 0
    elif est_feuille(n):
        # Cas de base : on ajoute 1 au total dès qu'on rencontre une feuille
        return 1
    else:
        # Recherche récursive dans les sous-arbres gauche et droit.
        nbre_feuilles_gauche = nbre_feuilles(n.gauche)
        nbre_feuilles_droit = nbre_feuilles(n.droit)

        # Calcul du nombre de feuilles
        return nbre_feuilles_gauche + nbre_feuilles_droit
  1. Écrire le code de la fonction profondeur_noeud dont la spécification est :
def profondeur_noeud(n: Noeud, val: str, prof: int = 0) -> int:
    """
    Détermine la profondeur du noeud de valeur val.
    """
Réponse
def profondeur_noeud(n: Noeud, val: str, prof: int = 0) -> int:
    """
    Détermine la profondeur du noeud de valeur val.
    Retourne -1 si le noeud n'est pas dans l'arbre.

    prof est la profondeur.
    """
    if est_vide(n):
        # Cas de base : si le nœud est vide, il n'est pas dans l'arbre.
        return -1
    elif n.valeur == val:
        # On a trouvé le noeud
        return prof
    else:
        # Recherche récursive dans les sous-arbres gauche et droit.
        # Incrémente la profondeur
        prof_gauche = profondeur_noeud(n.gauche, val, prof + 1)
        prof_droite = profondeur_noeud(n.droit, val, prof + 1)

        # Valeur retournée
        return max(prof_gauche, prof_droite)

Exemple : recherche de la profondeur du nœud de valeur 3

Les nœuds passés en argument sont repérés par la notation 1n, 2n, …

p(1n, 3, 0)
    p(2n, 3, 1)           -> -1
        p(4n, 3, 2)       -> -1
            p(None, 3, 3) -> -1
            p(None, 3, 3) -> -1
        p(5n, 3, 2)       -> -1
            p(None, 3, 3) -> -1
            p(None, 3, 3) -> -1
    p(3n, 3, 1)           -> 1 
  1. Écrire le code de la fonction remplace dont la spécification est :
def remplace(n: Noeud, val_ini: str, val_fin: str) -> None:
    """
    Cherche tous les noeuds de valeur val_ini et remplace ces
    dernières par val_fin.
    """
Réponse
def remplace(n: Noeud, val_ini: str, val_fin: str) -> None:
    """
    Cherche tous les noeuds de valeur val_ini et remplace ces
    dernières par val_fin.
    """
    if est_vide(n):
        return None
    elif n.valeur == val_ini:
        n.valeur = val_fin
    else:
        remplace(n.gauche, val_ini, val_fin)
        remplace(n.droit, val_ini, val_fin)
  1. Écrire le code de la fonction ajoute dont la spécification est :
def ajoute(n: Noeud, parent: str, enfant: str, gauche: bool) -> None:
    """
    Ajoute un noeud de valeur enfant comme enfant du noeud de valeur
    parent.
    Le noeud enfant est placé par défaut à gauche.

    HYPOTHÈSE : Le noeud de valeur parent existe.
    """
Réponse
def ajoute(n: Noeud, parent: str, enfant: str, gauche: bool) -> None:
    """
    Ajoute un noeud de valeur enfant comme enfant du noeud de valeur
    parent.
    Le noeud enfant est placé par défaut à gauche.

    HYPOTHÈSE : Le noeud de valeur parent existe.
    """
    if est_vide(n):
        return None
    elif n.valeur == parent:
        if gauche and not est_vide(n.gauche):
            raise Exception("Le noeud enfant gauche existe déjà !")
        if not gauche and not est_vide(n.droit):
            raise Exception("Le noeud enfant droit existe déjà !")
        if gauche:
            n.gauche = Noeud(enfant)
        else:
            n.droit = Noeud(enfant)
    else:
        ajoute(n.gauche, parent, enfant, gauche)
        ajoute(n.droit, parent, enfant, gauche)
  1. Écrire le code de la fonction supprime dont la spécification est :
def supprime(n: Noeud, val: str) -> None:
    """
    Supprime le noeud de valeur val ainsi que tous ses descendants.
    """
Réponse
def supprime(n: Noeud, val: str) -> None:
    """
    Supprime le noeud de valeur val ainsi que tous ses descendants.
    """
    if est_vide(n):
        return None
    elif est_feuille(n):
        return None
    elif n.gauche.valeur == val:
        n.gauche = None
    elif n.droit.valeur == val:
        n.droit = None
    else:
        supprime(n.gauche, val)
        supprime(n.droit, val)
  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.

À retenir

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 racine puis enfin parcourir le sous-arbre droit. On parle d’un parcours infixe.
  • Afficher la valeur du nœud racine avant de parcourir le sous-arbre gauche puis le sous-arbre droit. On parle d’un parcours préfixe.
  • Parcourir le sous-arbre gauche, le sous-arbre droit 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)
        1 --- 4(4)
        4 --- 5(5)
        4 --- 6(6)
        6 --- 7(7)
        8 --- 9(9)
        8 --- 13(13)
        9 --- 10(10)
        10 --- 11(11)
        10 --- 12(12)
        13 --- 14(14)
        13 --- 15(15)
    
    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, 11, 10, 12, 9, 8, 14, 13, 15
    • Suffixe : 3, 2, 5, 7, 6, 4, 1, 11, 12, 10, 9, 14, 15, 13, 8, 0

  2. Écrire le code des fonctions parcours_infixe, parcours_prefixe et parcours_suffixe dont les spécifications sont :

def parcours_infixe(n: Noeud) -> str:
    """
    Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
    Retourne le parcours sous forme d'une chaîne de caractères.
    """
Réponse
def parcours_infixe(n: Noeud) -> str:
    """
    Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
    Retourne le parcours sous forme d'une chaîne de caractères.
    """
    if est_vide(n):
        return ""
    else:
        chaine = parcours_infixe(n.gauche)
        chaine += str(n.valeur)
        chaine += parcours_infixe(n.droit)
        return chaine
def parcours_prefixe(n: Noeud) -> None:
    """
    Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
    Retourne le parcours sous forme d'une chaîne de caractères.
    """
Réponse
def parcours_prefixe(n: Noeud) -> None:
    """
    Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
    Retourne le parcours sous forme d'une chaîne de caractères.
    """
    if est_vide(n):
        return ""
    else:
        chaine = str(n.valeur)
        chaine += parcours_prefixe(n.gauche)
        chaine += parcours_prefixe(n.droit)
        return chaine
def parcours_suffixe(n: Noeud) -> None:
    """
    Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
    Retourne le parcours sous forme d'une chaîne de caractères.
    """
Réponse
def parcours_suffixe(n: Noeud) -> None:
    """
    Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
    Retourne le parcours sous forme d'une chaîne de caractères.
    """
    if est_vide(n):
        return ""
    else:
        chaine = parcours_suffixe(n.gauche)
        chaine += parcours_suffixe(n.droit)
        chaine += str(n.valeur)
        return chaine

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.
Fonction parcours_largeur(racine: Noeud):
    File f = File()
    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 cet algorithme.
Réponse
def parcours_largeur(n: Noeud) -> str:
    """Réalise le parcours en largeur d'un arbre binaire."""
    message = ""

    f = File()
    f.enfiler(n)
    while not f.est_vide():
        n = f.defiler()
        message += str(n.valeur)
        if not est_vide(n.gauche):
            f.enfiler(n.gauche)
        if not est_vide(n.droit):
            f.enfiler(n.droit)

    return message

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 ?
Fonction parcours_profondeur(racine: Noeud):
    Pile p = Pile()
    p.empiler(racine)
    TantQue non p.est_vide():
        n = p.depiler()
        print(n)
        Si non est_vide(n.filsG):
            p.empiler(n.filsG)
        FinSi
        Si non est_vide(n.filsD):
            p.empiler(n.filsD)
        FinSi
    FinTantQue
FinFonction
Réponse

L’algorithme semble realiser un parcours préfixe mais en explorant d’abord le sous-arbre droit au lieu d’explorer le sous-arbre gauche.

Modifier l’algorithme de telle sorte qu’il réalise le parcours préfixe.

Réponse
Fonction parcours_profondeur(racine: Noeud):
    Pile p = Pile()
    p.empiler(racine)
    TantQue non p.est_vide():
        n = p.depiler()
        print(n)
        Si non est_vide(n.filsD):
            p.empiler(n.filsD)
        FinSi
        Si non est_vide(n.filsG):
            p.empiler(n.filsG)
        FinSi
    FinTantQue
FinFonction
  1. Implémenter en Python cet algorithme.
Réponse
def parcours_prefixe_iter(n: Noeud) -> str:
    """
    Réalise un parcours préfixe à l'aide d'une pile.
    """
    message = ""

    p = Pile()
    p.empiler(n)
    while not p.est_vide():
        n = p.depiler()
        message += str(n.valeur)
        if not est_vide(n.gauche):
            p.empiler(n.gauche)
        if not est_vide(n.droit):
            p.empiler(n.droit)
    return message

Implémentation de la spécification en Python à l’aide d’une liste Python

  1. Reprendre toutes les fonctions de ce document en n’utilisant pas la classe Noeud mais une liste à trois éléments. Le premier est la « valeur » du noeud, le second l’adresse du fils gauche, le troisième l’adresse du fils droit.
Réponse
"""
Implémentation d'un arbre binaire en utilisant le
paradigme impératif et des listes.

Structure d'un noeud : [valeur, gauche, droit]
"""


def est_vide(n: list[str, list, list]) -> bool:
    """
    Teste si un arbre est vide.
    """
    return n is None


def ajoute_filsG(n: list[str, list, list], valeur: str) -> None:
    """
    Ajoute un noeud d'étiquette valeur comme fils gauche.
    """
    if est_vide(n[1]):
        n[1] = [valeur, None, None]
    else:
        raise Exception("Le nœud possède déjà un fils gauche !")


def ajoute_filsD(n: list[str, list, list], valeur: str) -> None:
    """
    Ajoute un noeud d'étiquette valeur comme fils droit.
    """
    if est_vide(n[2]):
        n[2] = [valeur, None, None]
    else:
        raise Exception("Le nœud possède déjà un fils droit !")


def est_feuille(n: list[str, list, list]) -> bool:
    """
    Teste si un noeud est une feuille.
    """
    return est_vide(n[1]) and est_vide(n[2])


def degre_noeud(n: list[str, list, list]) -> int:
    """
    Détermine le degré du noeud passé en argument.
    """
    if est_vide(n):
        raise Exception("Le nœud est vide !")

    nbre = 0
    if not est_vide(n[1]):
        nbre += 1
    if not est_vide(n[2]):
        nbre += 1

    return nbre


def taille(n: list[str, list, list]) -> int:
    """
    Retourne le nombre de noeud dans l'arbre.
    """
    if est_vide(n):
        return 0
    else:
        return 1 + taille(n[1]) + taille(n[2])


def profondeur(n: list[str, list, list]) -> int:
    """
    Retourne la profondeur de l'arbre.
    """
    if est_vide(n):
        return -1
    else:
        return 1 + max(profondeur(n[1]), profondeur(n[2]))


def nbre_feuilles(n: list[str, list, list]) -> int:
    """
    Détermine le nombre de feuilles dans l'arbre.
    """
    if est_vide(n):
        return 0
    elif est_feuille(n):
        return 1
    else:
        return nbre_feuilles(n[1]) + nbre_feuilles(n[2])


def parcours_pref(n: list[str, list, list]) -> str:
    """Parcours en profondeur préfixe d'un arbre binaire."""
    if est_vide(n):
        return ""
    else:
        chaine = str(n[0])
        chaine += parcours_pref(n[1])
        chaine += parcours_pref(n[2])
        return chaine


def parcours_inf(n: list[str, list, list]) -> str:
    """Parcours en profondeur infixe d'un arbre binaire."""
    if est_vide(n):
        return ""
    else:
        chaine = parcours_inf(n[1])
        chaine += str(n[0])
        chaine += parcours_inf(n[2])
        return chaine


def parcours_suf(n: list[str, list, list]) -> str:
    """Parcours en profondeur infixe d'un arbre binaire."""
    if est_vide(n):
        return ""
    else:
        chaine = parcours_suf(n[1])
        chaine += parcours_suf(n[2])
        chaine += str(n[0])
        return chaine


if __name__ == "__main__":
    arb = [
        "A",
        ["B", ["C", None, None], ["D", None, None]],
        ["E", ["F", None, None], ["G", ["H", None, None], None]],
    ]
    print(est_vide(arb))
    print(f"Taille de l'arbre : {taille(arb)}")
    print(f"Profondeur (hauteur) de l'arbre : {profondeur(arb)}")
    print(f"Préfixe : {parcours_pref(arb)}")
    print(f"Infixe : {parcours_inf(arb)}")
    print(f"Suffixe : {parcours_suf(arb)}")

Implémentation de la spécification en Python à l’aide d’un dictionnaire

  1. Reprendre toutes les fonctions de ce document en n’utilisant pas la classe Noeud mais un dictionnaire à trois clés : valeur, gauche et droit pour stocker la « valeur » du noeud, l’adresse du fils gauche et l’adresse du fils droit.
Réponse
"""
Implémentation du type arbre binaire en utilisant
le paradigme impératif et des dictionnaires.
"""


def est_vide(n: dict[str, dict, dict]) -> bool:
    """
    Teste si un arbre est vide.
    """
    return n == None


def ajoute_filsG(n: dict[str, dict, dict], val: str) -> None:
    """
    Ajoute un noeud d'étiquette val comme fils gauche.
    """
    if est_vide(n["gauche"]):
        n["gauche"] = {"valeur": val, "gauche": None, "droit": None}
    else:
        raise Exception("Le nœud possède déjà un fils gauche !")


def ajoute_filsD(n: dict[str, dict, dict], val: str) -> None:
    """
    Ajoute un noeud d'étiquette valeur comme fils droit.
    """
    if est_vide(n["droit"]):
        n["droit"] = {"valeur": val, "gauche": None, "droit": None}
    else:
        raise Exception("Le nœud possède déjà un fils droit !")


def est_feuille(n: dict[str, dict, dict]) -> bool:
    """
    Teste si un noeud est une feuille.
    """
    return est_vide(n["gauche"]) and est_vide(n["droit"])


def degre_noeud(n: dict[str, dict, dict]) -> int:
    """
    Détermine le degré du noeud passé en argument.
    """
    if est_vide(n):
        raise Exception("Le nœud est vide !")

    nbre = 0
    if not est_vide(n["gauche"]):
        nbre += 1
    if not est_vide(n["droit"]):
        nbre += 1

    return nbre


def taille(n: dict[str, dict, dict]) -> int:
    """
    Retourne le nombre de noeud dans l'arbre.
    """
    if est_vide(n):
        return 0
    else:
        return 1 + taille(n["gauche"]) + taille(n["droit"])


def profondeur(n: dict[str, dict, dict]) -> int:
    """
    Retourne la profondeur de l'arbre.
    """
    if est_vide(n):
        return -1
    else:
        return 1 + max(profondeur(n["gauche"]), profondeur(n["droit"]))


def nbre_feuilles(n: dict[str, dict, dict]) -> int:
    """
    Détermine le nombre de feuilles dans l'arbre.
    """
    if est_vide(n):
        return 0
    elif est_feuille(n):
        return 1
    else:
        return nbre_feuilles(n["gauche"]) + nbre_feuilles(n["droit"])


def parcours_pref(n: dict[str, dict, dict]) -> str:
    """Parcours en profondeur préfixe d'un arbre binaire."""
    if est_vide(n):
        return ""
    else:
        return str(n["valeur"]) + parcours_pref(n["gauche"]) + parcours_pref(n["droit"])


def parcours_inf(n: dict[str, dict, dict]) -> str:
    """Parcours en profondeur infixe d'un arbre binaire."""
    if est_vide(n):
        return ""
    else:
        return parcours_inf(n["gauche"]) + str(n["valeur"]) + parcours_inf(n["droit"])


def parcours_suf(n: dict[str, dict, dict]) -> str:
    """Parcours en profondeur infixe d'un arbre binaire."""
    if est_vide(n):
        return ""
    else:
        return parcours_suf(n["gauche"]) + parcours_suf(n["droit"]) + str(n["valeur"])


if __name__ == "__main__":
    arb = {
        "valeur": "A",
        "gauche": None,
        "droit": {
            "valeur": "B",
            "gauche": {"valeur": "C", "gauche": None, "droit": None},
            "droit": {"valeur": "D", "gauche": None, "droit": None},
        },
    }
    print(est_vide(arb))
    print(parcours_inf(arb))

    arb2 = {"valeur": "A", "droit": None, "gauche": None}
    ajoute_filsG(arb2, "B")
    ajoute_filsD(arb2, "C")
    noeud_C = arb2["droit"]
    ajoute_filsD(noeud_C, "D")
    ajoute_filsG(noeud_C, "E")
    print(f"Taille de l'arbre : {taille(arb2)}")
    print(f"Profondeur (hauteur) de l'arbre : {profondeur(arb2)}")
    print(parcours_pref(arb2))
    print(parcours_inf(arb2))
    print(parcours_suf(arb2))

À retenir

À retenir

Un arbre binaire est un ensemble fini de nœuds, qui est soit vide (la valeur None est utilisée pour représenter l’arbre 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. Il peut aussi être implémenté en utilisant une liste à trois éléments ou un dictionnaire à trois éléments.