14 - Algorithmes des arbres binaires

⏪

⏬

⏩

1 - Implémentation

2 - Interface

3 - module

4 - Algos

5 - FAQ

L'Arbre est une structure récursive.

Nous allons nous limiter à l'Arbre Binaire de façon à réaliser un nombre de fonctions récursives permettant de l'explorer.

Logiciel nécessaire pour l'activité : -

Prérequis :

Données : Arbre et Arbre Binaire
Algos : Parcours d'Arbres

Evaluation ✎ :

Documents de cours : -

1 - Implémentation d'un Arbre Binaire

⇩ ⇧ ⤊

L'activité d'aujourd'hui ne traite pas de la façon dont on réalise l'implémentation de notre type abstrait Arbre Binaire.

1er partie de la définition de l'arbre binaire

Un Arbre Binaire est :

soit un arbre binaire vide

soit l'ensemble d'un noeud et de deux sous-arbres binaires

Le noeud mène vers un sous-arbre binaire gauche (potentiellement vide donc)
Le noeud mène vers un sous-arbre binaire droite (potentiellement vide donc)

La distinction entre gauche et droite est fondamentale : placer un noeud à gauche plutôt qu'à droite doit être dû à une raison précise puisqu'il s'agit d'une arbre binaire et pas d'un arbre enraciné d'arité 2.

Réflexion pour obtenir une implémentation SIMPLE sous forme d'objets d'un Arbre Binaire en Python

Vision simple de l'Arbre Binaire

On peut se rendre compte que dans le cadre d'une implémentation la plus basique qui soit :

Un Arbre Binaire VIDE est un cas particulier.
Un Arbre Binaire NON VIDE est juste un pointeur vers un noeud.
Un Noeud est l'association de sa valeur stockée, et des deux sous-arbres binaires auquels il peut mener : vide ou un autre noeud.

Vision simple de la liste chaînée

On retrouve donc la situation déjà rencontrée avec la liste chaînée sous forme de tuple :

Une liste VIDE est un cas particulier.
Une liste NON VIDE est juste un pointeur vers la cellule de tête
Une Cellule est l'association d'une valeur stockée et de son successeur : None ou une autre cellule.

Pour une liste chaînée NON VIDE, nous avions ceci :

On pourait donc écrire ceci :

>>> lst1 = c

Vision simple de l'arbre binaire

Nous allons faire la même chose avec les Arbres Binaires en réalisant une implémentation qui ne distingue pas en réalité l'Arbre Binaire NON VIDE et le Noeud-racine.

Un Arbre Binaire sera une instance de la classe AB contenant trois attributs nommés v pour valeur liée à la racine, g pour sous-arbre gauche et d pour sous-arbre droite.

Un Arbre Binaire VIDE aura alors des attributs None, None, None.

Un Arbre Binaire NON VIDE aura des attributs correspondant à la valeur stockée par sa racine, à son sous-arbre binaire gauche et à son sous-arbre binaire droite.

On choisit donc de ne pas implémenter directement les Noeuds, même si vous allez voir que l'utilisateur ne peut pas le savoir.

# Déclaration de la classe AB
 
class AB:
    '''Implémentation d'un Arbre Binaire sous forme objet simple'''
 
    def __init__(self, valeur=None, gauche=None, droite=None):
        '''
        :: param valeur(Noeud|None) :: la valeur portée par la racine de l'Arbre, None uniquement si Arbre Binaire Vide
        :: param gauche(AB|None)    :: le sous-arbre binaire gauche (None indiquant un arbre vide)
        :: param droite(AB|None)    ::  le sous-arbre binaire droite (None indiquant un arbre vide)
        :: return(None)             :: -
        :: effet de bord            .. modifie self par effet de bord
        :: PRECONDITION : valeur à None valide uniquement sur l'appel AB(None, None, None)
 
        '''
        # Initialisation des attributs utilisés
        self.v = valeur  # valeur portée par la racine
        self.g = gauche  # Référence du sous-arbre gauche ou None si on atteint un Arbre Binaire Vide
        self.d = droite  # Référence du sous-arbre droite ou None si on atteint un Arbre Binaire Vide
 
    def relier_a_gauche(self, sous_arbre):
        '''Méthode qui définit sous_arbre comme le sous-arbre gauche de l'arbre actif
 
        :: param self(AB)        :: l'arbre NON VIDE à modifier
        :: param sous_arbre(AB)  :: le sous-arbre binaire à ajouter à gauche
        :: return(None)          :: -
        :: effet de bord         .. modifie self par effet de bord
 
        '''
        self.g = sous_arbre
 
    def relier_a_droite(self, sous_arbre):
        '''Méthode qui définit sous_arbre comme le sous-arbre droite de l'arbre actif
 
        :: param self(AB)        :: l'arbre NON VIDE à modifier
        :: param sous_arbre(AB)  :: le sous-arbre binaire à ajouter à droite
        :: return(None)          :: -
        :: effet de bord         .. modifie self par effet de bord
 
        '''
        self.d = sous_arbre

01° Lire les classes.

Quel est le seul cas où on a le droit d'envoyer None comme première valeur au constructeur AB() ?
S'agit-il d'une précondition imposée via une assertion ou juste d'une précondition à suivre mais sans vérification ?
Que faire pour créer un arbre ne contenant qu'un noeud dont la valeur est 10 ?

Correction ?

...CORRECTION...

Question 1

On ne peut envoyer None qui si on désire créer un Arbre Vide.

Il faut alors utiliser par exemple AB(None, None, None).

D'ailleurs, puisqu'il s'agit des valeurs par défaut, on peut même juste envoyer ceci :

Il faut alors utiliser par exemple AB().

Question 2

Rien n'est vérifié par une assertion ou un test. Il s'agit donc d'une simple indication à suivre scrupuleusement.

Question 3

Pour créer un Arbre ne contenant qu'un noeud-racine, il faut donc utiliser ceci :

Il faut alors utiliser par exemple AB(10, AB(None, None, None), AB(None, None, None))

Ou encore mieux (à cause des valeurs par défaut) AB(10, AB(), AB())

Ou encore mieux (à cause des valeurs par défaut) AB(10)

02° Répondre aux deux questions ci-dessous :

Ligne 6 : comment se nomment les variables qu'on trouve sur cette ligne : des paramètres ou des attributs ?
Ligne 17 : comment se nomme le v de self.v ?

Correction ?

...CORRECTION...

03° Répondre aux deux questions ci-dessous :

Ligne 21 : quel mot de vocabulaire utilisé pour décrire relier_a_gauche() ?
Ligne 25 : d'après la documentation de relier_a_gauche(), quel doit-être le type du paramètre sous_arbre ?
Comment pourrait-on imposer cette précondition sur le type du paramètre sous_arbre si on le voulait ?
Ligne 30 : que fait cette ligne qui est finalement la seule vraie ligne hors documentation de cette méthode ?
Quel appel faire si on veut que le sous-arbre gauche d'un arbre arbre soit un arbre vide ?

Correction ?

...CORRECTION...

Méthode
sous_arbre devrait être une instance de la classe AB.
On pourrait rajouter l'une de ces lignes en tant que première ligne de la méthode :

assert isinstance(sous_arbre, AB)

assert type(sous_arbre) == AB

Cette ligne modifie l'attribut gauche en y plaçant la référence de l'arbre qui servira de sous-arbre gauche.
Il faut taper ceci

arbre.relier_a_gauche(AB(None, None, None)).

arbre.relier_a_gauche(AB()).

04° A quoi sert la méthode relier_a_droite() ?

Correction ?

...CORRECTION...

2 - Fonctions d'interface

⇩ ⇧ ⤊

Maintenant que nous savons comment nous avons implémenté notre Arbre Binaire, nous allons pouvoir étudier et réaliser les fonctions d'interface permettant d'implémenter les primitives nécessaires à la manipulation des Arbres Binaires.

2e partie de la définition du type abstrait de données ARBRE BINAIRE : ses primitives

Description des primitives que nous allons utiliser

nvABV() -> Arbre Binaire VIDE

Crée un nouvel ARBRE BINAIRE vide.
On le note ainsi pour dire nouvelArbreBinaireVide() car c'est trop long.

nvAB(e:Element, g:Arbre Binaire, d:Arbre Binaire) -> Arbre Binaire NON VIDE

Crée un nouvel ARBRE BINAIRE dont le noeud-racine porte l'étiquette e et mène vers les sous-arbres binaires g et d transmis.

estABV(arbre:Arbre Binaire) -> bool

Prédicat qui répond True si l'arbre binaire est un arbre binaire vide.
On le note ainsi pour dire estArbreBinaireVide() car c'est trop long.

racine(arbre:Arbre Binaire NON VIDE) -> Noeud

Renvoie le noeud jouant le rôle de la racine pour l'arbre binaire NON VIDE reçu.

gauche(arbre:Arbre Binaire NON VIDE) -> Arbre

Renvoie le sous-arbre binaire gauche de arbre NON VIDE.

droite(arbre:Arbre Binaire NON VIDE) -> Arbre

Renvoie le sous-arbre binaire droite de arbre NON VIDE.

contenu(noeud:Noeud) -> Element

Renvoie la valeur du Noeud.

05° Créer un fichier nommé arbre_binaire_ifa.py dans un répertoire qu'on nommera algoAB.

📁 algoAB

📄 arbre_binaire_ifa.py

'''Module implémentant un Arbre Binaire (AB)
'''
 
# Déclaration de la classe AB
 
class AB:
    '''Implémentation d'un Arbre Binaire sous forme objet simple'''
 
    def __init__(self, valeur=None, gauche=None, droite=None):
        '''
        :: param valeur(Noeud|None) :: la valeur portée par la racine de l'Arbre, None uniquement si Arbre Binaire Vide
        :: param gauche(AB|None)    :: le sous-arbre binaire gauche (None indiquant un arbre vide)
        :: param droite(AB|None)    ::  le sous-arbre binaire droite (None indiquant un arbre vide)
        :: return(None)             :: -
        :: effet de bord            .. modifie self par effet de bord
        :: PRECONDITION : valeur à None valide uniquement sur l'appel AB(None, None, None)
 
        '''
        # Initialisation des attributs utilisés
        self.v = valeur  # valeur portée par la racine
        self.g = gauche  # Référence du sous-arbre gauche ou None si on atteint un Arbre Binaire Vide
        self.d = droite  # Référence du sous-arbre droite ou None si on atteint un Arbre Binaire Vide
 
    def relier_a_gauche(self, sous_arbre):
        '''Méthode qui définit sous_arbre comme le sous-arbre gauche de l'arbre actif
 
        :: param self(AB)        :: l'arbre NON VIDE à modifier
        :: param sous_arbre(AB)  :: le sous-arbre binaire à ajouter à gauche
        :: return(None)          :: -
        :: effet de bord         .. modifie self par effet de bord
 
        '''
        self.g = sous_arbre
 
    def relier_a_droite(self, sous_arbre):
        '''Méthode qui définit sous_arbre comme le sous-arbre droite de l'arbre actif
 
        :: param self(AB)        :: l'arbre NON VIDE à modifier
        :: param sous_arbre(AB)  :: le sous-arbre binaire à ajouter à droite
        :: return(None)          :: -
        :: effet de bord         .. modifie self par effet de bord
 
        '''
        self.d = sous_arbre
 
# Fonctions d'interface (accessibles de l'extérieur)
 
def valeur(noeud:'Noeud') -> 'Element':
    '''Renvoie la valeur du noeud fourni'''
    return noeud.v
 
def nv_ABV() -> 'Arbre Binaire VIDE':
    '''Renvoie un nouvel Arbre Binaire Vide'''
    return AB()
 
def nv_AB(valeur:'Element', g:'Arbre|None'=None, d:'Arbre|None'=None) -> 'Arbre Binaire NON VIDE':
    '''Renvoie un nouvel Arbre Binaire dont la racine porte valeur et qui mène aux sous-arbres g et d'''
    return AB(valeur, g, d)
 
def est_ABV(arbre:'Arbre Binaire') -> bool:
    '''Prédicat qui renvoie True si l'arbre est vide'''
    return arbre.v is None and arbre.g is None and arbre.d is None
 
def racine(arbre:'Arbre Binaire NON VIDE') -> 'Noeud':
    '''Renvoie le noeud-racine de l'Arbre Binaire NON VIDE'''
    return arbre  # car un arbre non vide est un pointeur vers sa racine
 
def gauche(arbre:'Arbre Binaire NON VIDE') -> 'Arbre Binaire':
    '''Renvoie le sous-arbre gauche de l'Arbre Binaire NON VIDE'''
    return arbre.g
 
def droite(arbre:'Arbre Binaire NON VIDE') -> 'Arbre Binaire':
    '''Renvoie le sous-arbre droit de l'Arbre Binaire NON VIDE'''
    return arbre.d
 
# Programme de test du module
 
if __name__ == "__main__":
 
    ad = nv_AB("D")
    af = nv_AB("F", g=ad)
    ae = nv_AB("E", d=af)
    ah = nv_AB("H")
    ag = nv_AB("G", d=ah)
    ab = nv_AB("B")
    ac = nv_AB("C", g=ag, d=ab)
    aa = nv_AB("A", g=ac, d=ae)

06° Lire chaque fonction d'interface et expliquer briévement ce qu'elles réalisent en analysant leur code.

Correction ?

...CORRECTION...

07° Dessiner l'Arbre Binaire créé par le programme de test (les lignes 80 à 87).

Correction ?

...CORRECTION...

08° Modifier le programme pour qu'il réalise plutôt la réalisation de cet arbre ci :

Correction ?

...CORRECTION...

3 - Utilisation du module

⇩ ⇧ ⤊

Nous allons maintenant réaliser différentes fonctions nous permettant de déterminer les caractéristiques de l'arbre, en utilisant uniquement les fonctions d'interface et sans nous soucier de l'implémentation.

Le mieux est donc de placer notre implémentation et les fonctions d'interface dans un module et de créer nos propres fonctions en utilisant uniquement les fonctions d'interface.

09° Créer un fichier nommé mes_algos.py dans le répertoire algoAB et contenant le programme Python suivant :

# Importation
 
from arbre_binaire_ifa import valeur
from arbre_binaire_ifa import nv_ABV
from arbre_binaire_ifa import nv_AB
from arbre_binaire_ifa import est_ABV
from arbre_binaire_ifa import racine
from arbre_binaire_ifa import gauche
from arbre_binaire_ifa import droite
 
# Déclarations des fonctions
 
def parcours_prefixe(arbre:'Arbre Binaire') -> None:
    '''Exploration (et affichage) en profondeur en préfixe RGD'''
    pass
 
def hauteur(arbre:'Arbre Binaire', profondeur_vide=0) -> int:
    '''Renvoie la hauteur de l'Arbre Binaire'''
    pass
 
def nb_feuilles(arbre:'Arbre Binaire') -> int:
    '''Renvoie le nombre de feuilles de l'Arbre Binaire'''
    pass
 
def taille(arbre:'Arbre Binaire') -> int:
    '''Renvoie la taille de l'Arbre Binaire'''
    pass
 
def est_present(arbre:'Arbre Binaire', c:'Element') -> bool:
    '''Prédicat : True si la clé c est la valeur d'un des noeuds'''
    pass
 
# Instructions du programme principal
 
if __name__ == "__main__":
 
    ad = nv_AB("D")
    af = nv_AB("F", g=ad)
    ae = nv_AB("E", d=af)
    ah = nv_AB("H")
    ag = nv_AB("G", d=ah)
    ab = nv_AB("B")
    ac = nv_AB("C", g=ag, d=ab)
    aa = nv_AB("A", g=ac, d=ae)

Vous devriez donc avoir deux fichiers situés dans le même répertoire.

📁 algoAB

📄 arbre_binaire_ifa.py

📄 mes_algos.py

Et c'est pour cela qu'avec from arbre_binaire_ifa import ... on parvient facilement à retrouver les fonctions situées dans le fichier arbre_binaire_ifa.py.

10° Expliquer pourquoi on peut directement utiliser la fonction nv_AB() alors que la fonction n'est pas dans ce fichier Python ? Que trouve-t-on directement derrière le import ?

Correction ?

...CORRECTION...

On trouve directement le nom de la fonction nv_AB() derrière le import. On a donc directement importer le nom de cette fonction et on peut l'utiliser juste en tapant son nom.

11° Notre programme importe donc la fonction de cette façon :

from arbre_binaire_ifa import nv_AB

Comment lancer l'appel à nv_AB() si les premières lignes proposaient simplement une importation de ce type :

import arbre_binaire_ifa

Correction ?

...CORRECTION...

Cette fois, on importe que le nom du module arbre_binaire_ifa.

Pour utiliser la fonction, il faut donc taper ceci :

arbre_binaire_ifa.nv_AB()

4 - Parcours et autres algorithmes

⇩ ⇧ ⤊

Parcours Préfixe (sous forme d'une simple exploration qui ne renvoie rien)

La fonction visiter() sera un simple affichage dans la console : on affichera la clé du noeud.

Préfixe car on commence par visiter le noeud actuel avant de faire autre chose.

On affiche donc le noeud racine lui-même avant ses descendants.

Description des ENTREES / SORTIE

ENTREE : Un Arbre Binaire (possiblement Vide)

SORTIE : Rien (sur l'exemple, il s'agit d'une fonction d'affichage sur l'interface utilisateur)

Description de l'algorithme récursif parcours_prefixe(arbre:Arbre)

SI NON estArbreBinaireVide(arbre)

visiter(racine(arbre))

parcours_prefixe(gauche(arbre))

parcours_prefixe(droite(arbre))

Fin SI

Renvoyer VIDE

Attention, on donne ici l'algorithme, pas l'implémentation Python.

12° Réaliser la fonction correspondante. Lancer les appels sur l'Arbre Binaire du programme.

`1`	`def parcours_prefixe(arbre:'Arbre Binaire') -> None:`

Vous devriez obtenir la réponse suivante :

A
C
G
H
B
E
F
D

Correction ?

...CORRECTION...

def parcours_prefixe(arbre:'Arbre Binaire') -> None:
    '''Exploration (et affichage) en profondeur en préfixe RGD'''
    if not est_ABV(arbre):
        print(valeur(racine(arbre)))
        parcours_prefixe(gauche(arbre))
        parcours_prefixe(droite(arbre))

13° Réaliser la fonction parcours_suffixe(). Ne regardez votre ancienne fonction, tentez de retrouver seul la solution : le jour de l'examen, vous partirez de rien.

`1`	`def parcours_suffixe(arbre:'Arbre Binaire') -> None:`

Vous devriez obtenir la réponse suivante :

H
G
B
C
D
F
E
A

Correction ?

...CORRECTION...

def parcours_suffixe(arbre:'Arbre Binaire') -> None:
    '''Exploration (et affichage) en profondeur en postfixe GDR'''
    if not est_ABV(arbre):
        parcours_suffixe(gauche(arbre))
        parcours_suffixe(droite(arbre))
        print(valeur(racine(arbre)))

14° Réaliser la fonction parcours_infixe(). Ne regardez votre ancienne fonction, tentez de retrouver seul la solution : le jour de l'examen, vous partirez de rien.

`1`	`def parcours_infixe(arbre:'Arbre Binaire') -> None:`

Vous devriez obtenir la réponse suivante :

G
H
C
B
A
E
D
F

Correction ?

...CORRECTION...

def parcours_infixe(arbre:'Arbre Binaire') -> None:
    '''Exploration (et affichage) en profondeur en infixe GRD'''
    if not est_ABV(arbre):
        parcours_infixe(gauche(arbre))
        print(valeur(racine(arbre)))
        parcours_infixe(droite(arbre))

15° Réaliser la fonction hauteur(). Elle doit renvoyer la hauteur de l'arbre.

Comme vous le voyez, cette fonction possède un paramètre qui permet de choisir la profondeur d'un arbre binaire vide. Ici, elle est réglée par défaut à 0. La racine aura donc une profondeur de 1.

`1`	`def hauteur(arbre:'Arbre Binaire', profondeur_vide=0) -> int:`

Condition d'arrêt : l'arbre est vide.
Cas de base : on renvoie la hauteur définie pour l'arbre vide
Cas récursif :
On renvoie la somme de 1 et du maximum entre hauteur du sous-arbre gauche et hauteur du sous-arbre droite.

On rappellera que pour trouver le maximum entre deux valeurs, on peut comparer mais on peut également utiliser la fonction native max qui renvoie le plus grand des arguments qu'on lui fournit : si a est plus grand que b, max(a, b) renvoie alors a.

Le jour de l'épreuve pratique, vous pouvez utiliser max() uniquement si vous êtes capable de la recréer.

Correction ?

...CORRECTION...

def hauteur(arbre:'Arbre Binaire', profondeur_vide=0) -> int:
    '''Renvoie la hauteur de l'Arbre Binaire'''
    if est_ABV(arbre):
        return profondeur_vide
    else:
        return 1 + max(hauteur(gauche(arbre)), hauteur(droite(arbre)))

16° Réaliser la fonction nb_feuilles(). Elle doit renvoyer le nombre de feuilles de l'arbre.

`1`	`def nb_feuilles(arbre:'Arbre Binaire') -> int:`

Condition d'arrêt 1 : l'arbre est vide.
Cas de base : on renvoie 0
Condition d'arrêt 2 : les deux sous-arbres de l'arbre sont vides (c'est une feuille !).
Cas de base : on renvoie 1
Cas récursif :
On renvoie la somme de l'appel récursif sur le sous-arbre-gauche et de l'appel récursif sur le sous-arbre droite.

Correction ?

...CORRECTION...

def nb_feuilles(arbre:'Arbre Binaire') -> int:
    '''Renvoie le nombre de feuilles de l'Arbre Binaire'''
    if est_ABV(arbre):
        return 0
    elif est_ ABV(gauche(arbre)) and est_ ABV(droite(arbre)):
        return 1
    else:
        return nb_feuilles(gauche(arbre)) + nb_feuilles(droite(arbre))

17° Variante : votre fonction doit en plus afficher la clé de la feuille lorsqu'il en trouve une.

Sur l'Arbre Binaire de l'exemple, cela donne :


  H
  B
  D
3

18° Réaliser la fonction taille(). Elle doit renvoyer le nombre de noeuds de l'Arbre Binaire.

`1`	`def taille(arbre:'Arbre Binaire') -> int:`

Condition d'arrêt 1 : l'arbre est vide.
Cas de base : on renvoie 0
Condition d'arrêt 2 : les deux sous-arbres de l'arbre sont vides (c'est une feuille !).
Cas de base : on renvoie 1
Cas récursif :
On renvoie la somme de 1 et de l'appel récursif sur le sous-arbre-gauche et de l'appel récursif sur le sous-arbre droite.

Correction ?

...CORRECTION...

def taille(arbre:'Arbre Binaire') -> int:
    '''Renvoie la taille de l'Arbre Binaire'''
    if est_ABV(arbre):
        return 0
    elif est_ ABV(gauche(arbre)) and est_ ABV(droite(arbre)):
        return 1
    else:
        return 1 + taille(gauche(arbre)) + taille(droite(arbre))

19° Réaliser le prédicat est_present(). Cette fonction doit renvoyer True si la clé fournie apparaît bien comme valeur d'un des noeuds de l'Arbre Binaire.

`1`	`def est_present(arbre:'Arbre Binaire', c:'Element') -> bool:`

Condition d'arrêt 1 : l'arbre est vide.
Cas de base : on renvoie False
Condition d'arrêt 2 : la clé de la racine a la bonne valeur.
Cas de base : on renvoie True
Cas récursif :
On renvoie le résultat de la recherche sur l'arbre gauche OU de la recherche dans l'arbre droite.

Question subsidiaire : que renvoie un OU s'il l'un des termes est VRAI ?

Correction ?

...CORRECTION...

def est_present(arbre:'Arbre Binaire', c:'Element') -> bool:
    '''Prédicat : True si c est la clé d'un des noeuds'''
    if est_ABV(arbre):
        return False
    elif valeur(racine(arbre)) == c:
        return True
    else:
        return est_present(gauche(arbre), c) or est_present(droite(arbre), c)

Vous devriez être bien content maintenant et vous rendre compte du parcours personnel réalisé depuis le début de première.

Il est temps de plonger dans le grand bain :

20° Effacer les instructions des fonctions que vous venez de réaliser aujourd'hui et tenter de le recréer en définissant vous même la récursivité.

Pas facile, mais indispensable pour l'évaluation. C'est l'objectif de la prochaine activité.

5 - FAQ

⇩ ⇧ ⤊

Rien pour le moment

Activité publiée le 10 12 2020
Dernière modification : 10 12 2020
Auteur : ows. h.

⏪

⏫

⏩