16 - 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 : -

MODE COURS (cacher les questions)

1 - Implémentation d'un Arbre Binaire

⇩ ⇧ ⤊

Il existe plusieurs façons d'implémenter le type abstrait ARBRE BINAIRE.

La version objet présentée ici présente des avantages et des inconvénients :

Avantage : plutôt simple.
Désavantage : pas de différence réelle entre un Arbre NON VIDE et un Noeud.

(Rappel) 1.1 L'idée générale (1er partie de la définition de l'arbre binaire)

Voir

A - Description

Un arbre binaire est composé

soit d'un arbre binaire VIDE
soit d'un arbre binaire NON VIDE composé d'un noeud menant à deux sous-arbres

le sous-arbre binaire gauche peut être un arbre binaire VIDE ou un arbre binaire NON VIDE
le sous-arbre binaire droite peut être un arbre binaire VIDE ou un arbre binaire NON VIDE

Il existe deux différences majeures entre les arbres enracinés et les arbres binaires :

L'arbre binaire peut être VIDE, alors qu'un arbre enraciné possède au moins un noeud-racine.
un arbre binaire n'est pas juste un arbre où chaque noeud peut avoir deux fils au maximum. Le positionnement à gauche ou à droite doit suivre une logique interne de positionnement, ce n'est pas un choix aléatoire. Dans le cas d'un arbre généalogique, on pourrait ainsi placer le père à gauche et la mère à droite dans tout l'arbre binaire. Ou faire le choix inverse, mais dans tout l'arbre.

On symbolise parfois l'arbre vide par un symbole particulier sur les arbres binaires. Ci-dessous, c'est un petit carré jaune.

B - Exemple

Ci-dessous, vous trouverez deux arbres binaires différents :

Ces arbres binaires ne sont pas identiques car le fils-gauche de C est B sur le premier mais le fils gauche de C est G sur le deuxième.

S'il s'agissait de deux arbres enracinés, il s'agirait par contre du même arbre. Il serait simplement représenté de deux façons différentes.

(Rappel) 1.2 Implémentation simple d'une Liste Chaînée en Python sous forme d'objets

Voir

Dans cette implémentation, on ne distingue pas le type LISTE NON VIDE et le type CELLULE.

Une Liste est soit une Liste VIDE, soit une Liste NON VIDE.
Une Liste VIDE est un pointeur vers None.
Une Liste NON VIDE est un pointeur vers la CELLULE de tête.
Une CELLULE est l'association d'une valeur et d'une Liste.

Si on résume par quelques équations sur les types :

Liste = Liste VIDE | Liste NON VIDE
Liste VIDE = None
Liste NON VIDE = (Element, Liste)
Cellule = (Element, Liste)

Une Liste NON VIDE est donc un pointeur vers une Cellule.

Exemple :

On pourait donc écrire ceci :

>>> a = (5, None)
>>> b = (15, a)
>>> c = (25, b)
>>> lst1 = c

1.3 Réflexion pour obtenir une implémentation SIMPLE d'un Arbre Binaire

Voir

Dans cette implémentation, on ne distingue pas le type AB NON VIDE et le type NOEUD.

Un AB est soit un AB VIDE, soit un AB NON VIDE.
Un AB VIDE est un pointeur vers None ou encore mieux, le triplet (None, None, None).
Un AB NON VIDE est un pointeur vers le NOEUD racine.
Un NOEUD est l'association d'un contenu et de deux AB.

Si on résume par quelques équations sur les types :

AB = AB VIDE | AB NON VIDE
AB VIDE = (None, None, None)
AB NON VIDE = (Element, AB, AB)
Noeud = (Element, AB, AB)

Un AB NON VIDE est donc ici un pointeur vers un Noeud.

1.4 Arbre Binaire en Python en utilisant un objet

Voir

Etape 1 : création basique

Nous voudrions implémenter l'Arbre sous forme d'un objet de classe AB contenant trois attributs nommés :

v pour valeur(contenu) attribuée à la racine;
g pour sous-arbre gauche:
d pour sous-arbre droite.

class AB:
    """Implémentation d'un Arbre Binaire sous forme objet simple"""
 
    def __init__(self, valeur=None, gauche=None, droite=None):
        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

Un Arbre Binaire VIDE sera alors créé avec AB(None, None, None).
Puisqu'on a utilisé des valeurs par défaut, nous pourrions aussi utiliser AB()
On notera que le constructeur ne doit accepter None en valeur que si les deux autres valeurs sont None également.

Un Arbre Binaire NON VIDE sera donc créé par une construction de type AB(valeur, arbre1, arbre2).

Etape 2 : transformation de None en vrai sous-arbre VIDE

A cause de valeurs par défaut, on pourrait ne pas envoyer d'arguments pour les paramètres gauche et droite. Or None ne représente pas l'Arbre VIDE. Il faudra donc impérativement rajouter des tests dans la méthode constructeur pour transformer les valeurs None en vrais sous-arbres vides lorsque l'arbre lui-même possède bien une valeur et n'est donc pas vide.

class AB:
    """Implémentation d'un Arbre Binaire sous forme objet simple"""
     
    def __init__(self, valeur=None, gauche=None, droite=None):
     
        assert valeur or (valeur == None and gauche == None and droite == None)
     
        self.v = valeur
        self.g = gauche
        self.d = droite
     
        if valeur and gauche is None:
            self.g = AB()
        if valeur and droite is None:
            self.d = AB()

Etape 3 : gestion des liaisons possibles entre l'arbre et ses sous-arbres

On crée quatre méthodes-mutateurs permettant de

définir un sous-arbre gauche pour un arbre NON VIDE;
définir un sous-arbre droite pour un arbre NON VIDE;
définir le contenu de la racine d'un arbre;
vider un arbre et en faire un AB VIDE;

# 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):
     
        assert valeur or (valeur == None and gauche == None and droite == None)
     
        self.v = valeur
        self.g = gauche
        self.d = droite
     
        if valeur and gauche is None:
            self.g = AB()
        if valeur and droite is None:
            self.d = AB()
 
    def relier_a_gauche(self:'AB NON VIDE', sous_arbre:'AB'):
        """Méthode qui définit sous_arbre comme le sous-arbre gauche de l'arbre actif"""
        self.g = sous_arbre
 
    def relier_a_droite(self:'AB NON VIDE', sous_arbre:'AB'):
        """Méthode qui définit sous_arbre comme le sous-arbre droite de l'arbre actif"""
        self.d = sous_arbre
 
    def definir_donnees_racine(self:'AB', element:'Element NON VIDE'):
        """Méthode qui place l'élément NON VIDE en tant que racine de l'arbre"""
        self.v = element
 
    def vider(self:'AB'):
        """Méthode qui transforme l'arbre en AB VIDE"""
        self.v = None
        self.g = None
        self.d = None

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

L'assertion teste bien soit que la valeur contient quelque chose, soit qu'on envoie bien trois None.

Question 3

Pour créer un Arbre ne contenant qu'un noeud-racine, il faut donc utiliser l'une de ces possibilités, offertes par l'utilisation des valeurs par défaut :

AB(10, AB(None, None, None), AB(None, None, None))

AB(10, AB(), AB())

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 10 : comment se nomme le v de self.v ?

Correction ?

...CORRECTION...

03° Quel appel faire si on veut que le sous-arbre gauche d'un arbre stocké dans une variable arbre soit un arbre vide ?

Correction ?

...CORRECTION...

Il faut taper ceci

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

arbre.relier_a_gauche(AB())

04° Pourquoi avoir créer vider() alors qu'un utilisateur aurait pu taper lui-même ceci dans le programme pour transformer arbre en arbre vide ?

arbre.v = None

arbre.g = None

arbre.d = None

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.

(Rappel) 2.1 Les primitives (2e partie de la définition de l'arbre binaire)

Voir

Je le décris ici sous forme d'un type immuable, mais on pourait faire la même chose en muable.

nvABV() -> Arbre Binaire VIDE

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

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

Crée un nouvel ARBRE BINAIRE dont la racine porte la valeur v et mène aux sous-arbres transmis à la fonction, g et d.

estABV(arbre:Arbre Binaire) -> bool

Prédicat qui renvoie True si l'arbre est un arbre binaire vide.

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

Renvoie le noeud jouant le rôle de la racine pour cet arbre binaire NON VIDE.

contenu(noeud:Noeud) -> Element

Renvoie l'élément rattaché au noeud transmis.

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

Renvoie le sous-arbre gauche de arbre. On obtient bien un Arbre. Si vous voulez le noeud gauche, il faudra appliquer en plus la fonction racine().

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

Renvoie le sous-arbre droite de arbre.

Notez bien que j'ai rajouté les underscores sur les noms des fonctions implémentées ci-dessous alors que les versions abstraites n'en possèdent pas.

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) sous forme d'objets
"""
 
# 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):
     
        assert valeur or (valeur == None and gauche == None and droite == None)
     
        self.v = valeur
        self.g = gauche
        self.d = droite
     
        if valeur and gauche is None:
            self.g = AB()
        if valeur and droite is None:
            self.d = AB()
 
    def relier_a_gauche(self:'AB NON VIDE', sous_arbre:'AB'):
        """Méthode qui définit sous_arbre comme le sous-arbre gauche de l'arbre actif"""
        self.g = sous_arbre
 
    def relier_a_droite(self:'AB NON VIDE', sous_arbre:'AB'):
        """Méthode qui définit sous_arbre comme le sous-arbre droite de l'arbre actif"""
        self.d = sous_arbre
 
    def definir_donnees_racine(self:'AB', element:'Element NON VIDE'):
        """Méthode qui place l'élément NON VIDE en tant que racine de l'arbre"""
        self.v = element
 
    def vider(self:'AB'):
        """Méthode qui transforme l'arbre en AB VIDE"""
        self.v = None
        self.g = None
        self.d = None
 
# Fonctions d'interface (accessibles de l'extérieur)
 
def contenu(noeud:'Noeud') -> 'Element':
    """Renvoie le contenu associé au noeud fourni"""
    return noeud.v
 
def nv_ABV() -> 'AB VIDE':
    """Renvoie un nouvel Arbre Binaire Vide"""
    return AB()
 
def nv_AB(valeur:'Element', g:'AB|None'=None, d:'AB|None'=None) -> 'AB 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:'AB') -> 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:'AB NON VIDE') -> 'Noeud':
    """Renvoie le noeud-racine de l'Arbre Binaire NON VIDE"""
    return arbre  # dans cette implémentation, un AB non vide est un pointeur vers sa racine
 
def gauche(arbre:'AB NON VIDE') -> 'AB':
    """Renvoie le sous-arbre gauche de l'Arbre Binaire NON VIDE"""
    return arbre.g
 
def droite(arbre:'AB NON VIDE') -> 'AB':
    """Renvoie le sous-arbre droite 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 pour réellement comprendre ce qu'elles réalisent et comment elles le réalisent.

Correction ?

...CORRECTION...

07° Que veut dire la ligne 72 ? Dessiner l'Arbre Binaire créé par le programme de test (les lignes 74+).

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 contenu
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:'AB') -> None:
    """Exploration (et affichage) en profondeur en préfixe RGD"""
    pass
 
def hauteur(arbre:'AB', profondeur_vide=0) -> int:
    """Renvoie la hauteur de l'Arbre Binaire"""
    pass
 
def nb_feuilles(arbre:'AB') -> int:
    """Renvoie le nombre de feuilles de l'Arbre Binaire"""
    pass
 
def taille(arbre:'AB') -> int:
    """Renvoie la taille de l'Arbre Binaire"""
    pass
 
def est_present(arbre:'AB', 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

⇩ ⇧ ⤊

(RAPPEL) Algo Parcours PREFIXE d'Arbre sans précondition

Voir

Il existe deux versions de l'algorithme : dans la première la précondition est que l'arbre soit NON VIDE, dans la deuxième version, il peut être vide ou pas.

Description des ENTREES et SORTIE

ENTREE : Un Arbre Binaire
SORTIE : Rien sur l'exemple, simple fonction d'affichage. Mais on pourrait les stocker dans un tableau et renvoyer le tableau.

Description de l'ALGORITHME (sans précondition)

Description de parcourir(arbre: Arbre Binaire)

SI NON estABV(arbre)

visiter(racine(arbre))

parcourir(gauche(arbre))

parcourir(droite(arbre))

Fin SI

Renvoyer VIDE

Note importante pour éviter une erreur bête

Il s'agit ici de SI (NON condition) et pas d'un SINON SI (condition).

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

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

Vous devriez obtenir la réponse suivante :

A
C
G
H
B
E
F
D

Correction ?

...CORRECTION...

def parcours_prefixe(arbre:'AB') -> None:
    """Exploration (et affichage) en profondeur en préfixe RGD"""
     
    if not est_ABV(arbre):
        print(contenu(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:'AB') -> None:`

Vous devriez obtenir la réponse suivante :

H
G
B
C
D
F
E
A

Correction ?

...CORRECTION...

def parcours_suffixe(arbre:'AB') -> None:
    """Exploration (et affichage) en profondeur en postfixe GDR"""
     
    if not est_ABV(arbre):
        parcours_suffixe(gauche(arbre))
        parcours_suffixe(droite(arbre))
        print(contenu(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:'AB') -> None:`

Vous devriez obtenir la réponse suivante :

G
H
C
B
A
E
D
F

Correction ?

...CORRECTION...

def parcours_infixe(arbre:'AB') -> None:
    """Exploration (et affichage) en profondeur en infixe GRD"""
     
    if not est_ABV(arbre):
        parcours_infixe(gauche(arbre))
        print(contenu(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:'AB', 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:'AB', 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:'AB') -> 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:'AB') -> 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:'AB') -> 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:'AB') -> 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:'AB', 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 contenu(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 (pas le prototype !) et tenter de le recréer en définissant vous même la récursivité.

Pas facile, mais indispensable pour l'évaluation.

5 - FAQ

⇩ ⇧ ⤊

Rien pour le moment

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

⏪

⏫

⏩