Tous les articles par icnisnboissy

Corrigé exercice 3 les arbres

14 octobre 2022 icnisnboissy

Q1a
Nombre de nœuds = 7 (taille max pour une hauteur h : 2h – 1 = 1).
Q1b
profondeur maximale du nœud racine = 4
NB : par convention, ici un arbre réduit à un seul nœud est de hauteur 1
Q2
Taille : 7
Hauteur : 3 (par convention h(Δ) = 1)

Q3
Taille : 7
Hauteur : 4

def hauteur(self):
    return self.racine.hauteur()

def taille(self) -> int:
   if self.gauche == None and self.droite == None:
      return 1
   elif self.gauche == None:
      return 1 + self.droite.taille()
   elif self.droite == None:
      return 1 + self.gauche.taille()
   else:
      return 1 + self.gauche.taille() + self.droite.taille()
def taille(self):
   return self.racine.taille()

Q6a
2(h-1) – 1 < taille ≤ 2h – 1
doù t_min = 2(h-1) – 1

Q6b

def bien_construit(self) -> bool:
   return 2**(self.racine.hauteur() - 1) - 1 < self.racine.taille() <= 2**self.racine.hauteur() - 1

Non classé

Corrigé exercice 2 les arbres

14 octobre 2022 icnisnboissy

1.a. Il y a 4 feuilles, d’étiquette 12, val, 21 et 32.
1.b. Le sous-arbre gauche du nœud 23 est 19-21.
1.c. La hauteur de l’arbre est 4. Sa taille est 9.
1.d. Les valeurs possibles de val sont 16 et 17.

2.a. Parcours infixe : 12-13-15-16-18-19-21-23-32
2.b. Parcours suffixe : 12-13-16-15-21-19-32-23-18

3.a.

3.b.

racine = Noeud(18)
racine.insere([15, 13, 12, 16, 23, 32, 19, 21])

(d’autres solutions sont possibles)

3.c. bloc 3 – bloc 2
ne rentre pas dans bloc 1

class Noeud():
    def __init__(self, v):
        self.ag = None
        self.ad = None
        self.v = v

    def insere(self, v):
        n = self
        est_insere = False
        while not est_insere:
            if v == n.v:
                est_insere = True
            elif v < n.v:
                if n.ag != None:
                    n = n.ag
                else:
                    n.ag = Noeud(v)
                    est_insere = True
            else:
                if n.ad != None:
                    n = n.ad
                else:
                    n.ad = Noeud(v)
                    est_insere = True

    def insere_tout(self, vals):
        for v in vals:
            self.insere(v)

    def recherche(self, v):
        arbre = self
        while not arbre is None:
            if arbre.v == v:
                return True
            if v < arbre.v:
                arbre = arbre.ag
            else:
                arbre = arbre.ad
        return False


    # version récursive (non demandée)

    def recherche_rec(self, v):
        if self is None:
            return False
        if self.v == v:
            return True
        if v < self.v:
            if self.ag is not None:
                return self.ag.recherche_rec(v)
            else:
                return False
        else:
            if self.ad is not None:
                return self.ad.recherche_rec(v)
            else:
                return False


racine = Noeud(18)
racine.insere_tout([12, 13, 15, 14, 19, 21, 32, 23])
print(racine.recherche(149))
print(racine.recherche(12))

Non classé

Exercices -Arbres

14 octobre 2022 icnisnboissy

Exercice 1

2021, sujet 0

Question 1

Déterminer la taille et la hauteur de l’arbre binaire suivant :

Question 2

On décide de numéroter en binaire les nœuds d’un arbre binaire de la façon suivante :

la racine correspond à 1 ;
la numérotation pour un fils gauche s’obtient en ajoutant le chiffre 0 à droite au numéro de son père ;
la numérotation pour un fils droit s’obtient en ajoutant le chiffre 1 à droite au numéro de son père ;

Par exemple, dans l’arbre ci-dessous, on a utilisé ce procédé pour numéroter les nœuds A, B, C, E et F .

Dans l’exemple précédent, quel est le numéro en binaire associé au nœud G ?
Quel est le nœud dont le numéro en binaire vaut 13 en décimal ?
En notant h la hauteur de l’arbre, sur combien de bits seront numérotés les nœuds les plus en bas ?
Justifier que pour tout arbre de hauteur h et de taille n ≥ 2, on a : h ≤ n ≤ 2h − 1.

Question 3
Un arbre binaire est dit complet si tous les niveaux de l’arbre sont remplis.

On décide de représenter un arbre binaire complet par un tableau de taille n + 1, où n est la taille de l’arbre, de la façon suivante :

La racine a pour indice 1 ;
Le fils gauche du nœud d’indice i a pour indice 2 × i ;
Le fils droit du nœud d’indice i a pour indice 2 × i + 1 ;
On place la taille n de l’arbre dans la case d’indice 0

Répondre aux questions suivantes :

Déterminer le tableau qui représente l’arbre binaire complet de l’exemple précédent.
On considère le père du nœud d’indice i avec i ≥ 2. Quel est son indice dans le tableau ?

Question 4

On se place dans le cas particulier d’un arbre binaire de recherche complet où les nœuds contiennent des entiers et pour lequel la valeur de chaque noeud est supérieure à celles des noeuds de son fils gauche, et inférieure à celles des noeuds de son fils droit.

Écrire une fonction recherche ayant pour paramètres un arbre arbre et un élément element. Cette fonction renvoie True si element est dans l’arbre et False sinon. L’arbre sera représenté par un tableau comme dans la question précédente. corrigé

Corrigé

merci à G.Lassus

Exercice 2

2021, Métropole sujet 1, exercice 1

Dans cet exercice, les arbres binaires de recherche ne peuvent pas comporter plusieurs fois la même clé. De plus, un arbre binaire de recherche limité à un nœud a une hauteur de 1. On considère l’arbre binaire de recherche représenté ci-dessous (figure 1), où val représente un entier :

1.a Donner le nombre de feuilles de cet arbre et préciser leur valeur (étiquette).

1.b Donner le sous arbre-gauche du nœud 23.

1.c Donner la hauteur et la taille de l’arbre.

1.d Donner les valeurs entières possibles de val pour cet arbre binaire de recherche.

On suppose, pour la suite de cet exercice, que val est égal à 16.

2. On rappelle qu’un parcours infixe depuis un nœud consiste, dans l’ordre, à faire un parcours infixe sur le sous arbre-gauche, afficher le nœud puis faire un parcours infixe sur le sous-arbre droit.
Dans le cas d’un parcours suffixe, on fait un parcours suffixe sur le sous-arbre gauche puis un parcours suffixe sur le sous-arbre droit, avant d’afficher le nœud.

a. Donner les valeurs d’affichage des nœuds dans le cas du parcours infixe de l’arbre.
b. Donner les valeurs d’affichage des nœuds dans le cas du parcours suffixe de l’arbre.

3. On considère la classe Noeud définie de la façon suivante en Python :

a. Représenter l’arbre construit suite à l’exécution de l’instruction suivante :

racine = Noeud(18)
racine.insere_tout([12, 13, 15, 16, 19, 21, 32, 23])

b. Écrire les deux instructions permettant de construire l’arbre de la figure 1. On rappelle que le nombre val est égal à 16.

c. On considère l’arbre tel qu’il est présenté sur la figure 1. Déterminer l’ordre d’exécution des blocs (repérés de 1 à 3) suite à l’application de la méthode insere(19) au nœud racine de cet arbre.

4. Écrire une méthode recherche(self, v) qui prend en argument un entier v et renvoie la valeur True si cet entier est une étiquette de l’arbre, False sinon.

corrigé

Exercice 3

2021, Métropole Candidats Libres 2, exercice 3

On rappelle qu’un arbre binaire est composé de nœuds, chacun des nœuds possédant éventuellement un sous-arbre gauche et éventuellement un sous-arbre droit. Un nœud sans sous-arbre est appelé feuille. La taille d’un arbre est le nombre de nœuds qu’il contient ; sa hauteur est le nombre de nœuds du plus long chemin qui joint le nœud racine à l’une des feuilles. Ainsi la hauteur d’un arbre réduit à un nœud, c’est-à-dire la racine, est 1.

Dans un arbre binaire de recherche, chaque nœud contient une clé, ici un nombre entier, qui est :

strictement supérieure à toutes les clés des nœuds du sous-arbre gauche ;
strictement inférieure à toutes les clés des nœuds du sous-arbre droit.

Un arbre binaire de recherche est dit « bien construit » s’il n’existe pas d’arbre de hauteur inférieure qui pourrait contenir tous ses nœuds.

On considère l’arbre binaire de recherche ci-dessous.

1.a. Quelle est la taille de l’arbre ci-dessus ?

1.b. Quelle est la hauteur de l’arbre ci-dessus ?

2. Cet arbre binaire de recherche n’est pas « bien construit ». Proposer un arbre binaire de recherche contenant les mêmes clés et dont la hauteur est plus petite que celle de l’arbre initial.

3. Les classes Noeud et Arbre ci-dessous permettent de mettre en œuvre en Python la structure d’arbre binaire de recherche. La méthode insere permet d’insérer récursivement une nouvelle clé.

class Noeud :

    def __init__(self, cle):
        self.cle = cle
        self.gauche = None
        self.droit = None

    def insere(self, cle):
        if cle < self.cle :
            if self.gauche == None :
                self.gauche = Noeud(cle)
            else :
                self.gauche.insere(cle)
        elif cle > self.cle :
            if self.droit == None :
                self.droit = Noeud(cle)
            else :
                self.droit.insere(cle)

class Arbre :

    def __init__(self, cle):
        self.racine = Noeud(cle)

    def insere(self, cle):
        self.racine.insere(cle)

Donner la représentation de l’arbre codé par les instructions ci-dessous.

a = Arbre(10)
a.insere(20)
a.insere(15)
a.insere(12)
a.insere(8)
a.insere(4)
a.insere(5)

4. Pour calculer la hauteur d’un arbre non vide, on a écrit la méthode ci-dessous dans la classe Noeud.

def hauteur(self):
    if self.gauche == None and self.droit == None:
        return 1
    if self.gauche == None:
        return 1 + self.droit.hauteur()
    elif self.droit == None:
        return 1 + self.gauche.hauteur()
    else:
        hg = self.gauche.hauteur()
        hd = self.droit.hauteur()
        if hg > hd:
            return hg + 1
        else:
            return hd + 1

Écrire la méthode hauteur de la classe Arbre qui renvoie la hauteur de l’arbre.

5. Écrire les méthodes taille des classes Noeud et Arbre permettant de calculer la taille d’un arbre. corrigé Méthode de la classe :

6. On souhaite écrire une méthode bien_construit de la classe Arbre qui renvoie la valeur True si l’arbre est « bien construit » et False sinon.

On rappelle que la taille maximale d’un arbre binaire de recherche de hauteur est 2^h-1.

6.a Quelle est la taille minimale, notée min d’un arbre binaire de recherche « bien construit » de hauteur h?

6.b Écrire la méthode bien_construit demandée.

corrigé

Non classé

Corrigé exercice 1 les arbres

14 octobre 2022 icnisnboissy

Q1 La taille est 9, la hauteur est 4.
Q2 1. G est associé à 1010.
Q2 2. 13 s’écrit 1101 en binaire, c’est donc le nœud I.
Q2 3. Les nœuds les plus en bas sont notés sur bits.
Q2 4. L’arbre de hauteur de taille minimale est l’arbre filiforme, qui est de taille .
L’arbre de hauteur de taille maximale est l’arbre complet, qui est de taille . Si est la taille d’un arbre quelconque de taille

, on a donc bien $$ h \leqslant n \leqslant 2^h-1 $$.

Q3 1. Tableau : [15, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O] .
Q3 2. Le père du nœud d’indice i a pour indice i//2.

Q4 :

def recherche(arbre, element):
    i = 1
    while i < len(arbre):
        if arbre[i] == element:
            return True
        if element < arbre[i]:
            i = 2*i # on se place sur le fils gauche
        else:
            i = 2*i +  1 # on se place sur le fils droit
    return False

Non classé

Outils en ligne

28 septembre 2021 icnisnboissy

Environnement de développement Python en ligne pour travailler la programmation sur n’importe quel appareil sans installation

Replit.com

Environnement Linux (Debian) en ligne :

Cocalc (l’enregistrement est facultatif mais vous permettra de retrouver votre travail).
Webminal est une alternative très intéressante mais l’enregistrement est obligatoire et nécessite une adresse mail.

Non classé

Le principe du “diviser pour régner” en Python EXERCICES

14 décembre 2020 icnisnboissy

Exercice 1: Recherche valeur dans une liste

Algorithme:

fonction chercher : (tableau, clé) —-> booléen
1. Pour un tableau de taille 1, il contient la clé si valeur est la clé
2. On sépare le tableau en deux parties sensiblement de même taille (gauche et droite)
3. Le tableau contient la clé si
chercher(gauche, clé) ou chercher(droite, clé)
est vrai.

Exemple
tableau = [4, 10, 20, 5]
clé = 10
A-t-on clé dans tableau ?
Exemple
clé = 10
[4, 10, 20, 5]

diviser [4, 10] [20, 5]

diviser [4] [10] [20] [5]

combiner Faux ou Vrai Faux ou Faux

combiner Vrai ou Faux

combiner Vrai

Implémenter cette fonction sous python.

Exercice 2: Calcul y puissance x

On souhaite calculer N=7⁵². La méthode basique consiste à multiplier le nombre 7 par lui-même 52 fois… Ce qui n’est pas très rapide !

L’idée consiste donc à diviser le problème en 2 : on va calculer 7²⁶× 7²⁶, c’est-à-dire( 7²⁶)². Là, il n’y a plus que 26 + 1 opérations (26 multiplications pour calculer 7²⁶, et une dernière pour faire le carré du résultat.

On recommence ensuite avec 7²⁶ : on le calcule en faisant (7¹³)².

N se calcule alors en 13+1+1 opérations au lieu de 52 initialement.

On ne s’arrête pas là, bien entendu : on continue tant que l’on peut utiliser ce principe :

N=7⁵²

=(7²⁶)²

=((7¹³)²)²

=[[(7⁶)²×7]²]²

=[[((7³)²)²×7]²]²

=[[((7²×7)²)²×7]²]²

Le principe est, vous l’avez peut-être remarqué, récursif.

Implémentation en Python du “diviser pour régner”

Nous allons écrire une fonction “puissance(x,n)” basée sur ce paradigme, où x et n sont deux entiers (positif pour n). Pour cela, nous allons prendre en compte que:

Implémenter cette fonction avec python

Exercice 3: Faire pivoter une image

quartdetour Télécharger

Algorithmique, NSI

Méthode diviser pour régner

14 décembre 2020 icnisnboissy

Diviser pour régner

Le diviser pour régner est une méthode algorithmique basée sur le principe suivant :

On prend un problème (généralement complexe à résoudre), on divise ce problème en une multitude de petits problèmes, l’idée étant que les « petits problèmes » seront plus simples à résoudre que le problème original. Une fois les petits problèmes résolus, on recombine les « petits problèmes résolus » afin d’obtenir la solution du problème de départ.

Le paradigme « diviser pour régner » repose donc sur 3 étapes :

DIVISER : le problème d’origine est divisé en un certain nombre de sous-problèmes
RÉGNER : on résout les sous-problèmes (les sous-problèmes sont plus faciles à résoudre que le problème d’origine)
COMBINER : les solutions des sous-problèmes sont combinées afin d’obtenir la solution du problème d’origine.

Les algorithmes basés sur le paradigme « diviser pour régner » sont très souvent des algorithmes récursifs.

Nous allons maintenant étudier un de ces algorithmes basés sur le principe diviser pour régner : le tri-fusion

Tri-fusion

Nous avons déjà étudié des algorithmes de tri : le tri par insertion et le tri par sélection. Nous allons maintenant étudier une nouvelle méthode de tri, le tri-fusion. Comme pour les algorithmes déjà étudiés, cet algorithme de tri fusion prend en entrée un tableau non trié et donne en sortie, le même tableau, mais trié.

À faire vous-même 1

Étudiez cet algorithme :

TRI FUSION (tableau):
• Si tableau est de taille <= 1 on ne fait rien.
• Sinon, On sépare tableau en 2 parties gauche et droite,
• On appelle Tri fusion sur gauche et sur droite
• On fusionne gauche et droite dans tableau

FUSIONNER (`tableau`, `gauche`, `droite`):
* On parcourt les deux tableaux `gauche` et `droite` en même temps,
Pour chaque paire d'éléments, on place le plus petit dans tableau.
* S'il reste des éléments dans `gauche` ou dans `droite` on les place à la fin
de tableau

Pour trier un tableau A, on fait l’appel initial TRI-FUSION(A, 1, A.longueur)

Rappel : Attention, en algorithmique, les indices des tableaux commencent à 1

Cet algorithme est un peu difficile à appréhender, on notera qu’il est composé de deux fonctions FUSIONNER et TRI-FUSION (fonction récursive). La fonction TRI-FUSION assure la phase « DIVISER » et la fonction FUSION assure les phases « RÉGNER » et « COMBINER ».

Voici un exemple d’application de cet algorithme sur le tableau A = [23, 12, 4, 56, 35, 32, 42, 57, 3] :

À faire vous-même 2

Étudiez attentivement le schéma ci-dessous afin de mieux comprendre le principe du tri-fusion (identifiez bien les phases « DIVISER » et « COMBINER »).

On remarque que dans le cas du tri-fusion, la phase « RÉGNER » se réduit à sa plus simple expression, en effet, à la fin de la phase « DIVISER », nous avons à trier des tableaux qui comportent un seul élément, ce qui est évidemment trivial.

À faire vous-même 3

Reprenez tout le raisonnement qui vient d’être fait sur le tableau T = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]. Vous n’hésiterez pas à faire un schéma et à expliquer la fusion de 2 tableaux triés.

Nous avons vu que le tri par insertion et tri par sélection ont tous les deux une complexité O(n2)

. Qu’en est-il pour le tri-fusion ?

Le calcul rigoureux de la complexité de cet algorithme sort du cadre de ce cours. Mais, en remarquant que la première phase (DIVISER) consiste à « couper » les tableaux en deux plusieurs fois de suite, intuitivement, on peut dire qu’un logarithme base 2 doit intervenir. La deuxième phase consiste à faire des comparaisons entre les premiers éléments de chaque tableau à fusionner, on peut donc supposer que pour un tableau de n éléments, on aura n comparaisons. En combinant ces 2 constations on peut donc dire que la complexité du tri-fusion est en O(n.log(n))

(encore une fois la « démonstration » proposée ici n’a rien de rigoureux).

La comparaison des courbes de la fonction n2 (en rouge) et n.log(n)

(en bleu) :

nous montre que l’algorithme de tri-fusion est plus « efficace » que l’algorithme de tri par insertion ou que l’algorithme de tri par sélection.

Présentation vidéo détaillée du tri fusion

Utilisation du tri fusion:
Contrairement au tri par sélection ou par insertion, le tri fusion est réellement utilisé en pratique.
Il a de nombreux avantages :
• complexité optimale (cela ne signifie pas qu’il est le plus rapide)
• stable (voir plus bas)
• facile à mettre en œuvre
Cependant, il est possible d’améliorer la méthode :
timsort, le tri natif en Python et Javascript utilise une combinaison du tri fusion et du tri par insertion.

Exercices Diviser pour régner

FICHE REVISION

Auteur : David Roche

NSI, PROJET

Projet : implémentation en Python des algorithmes sur les arbres binaires

8 décembre 2020 icnisnboissy

Le but de ce projet est d’implémenter en Python les algorithmes sur les arbres binaires précédemment étudiés. Il sera donc sans doute nécessaire de reprendre ce qui a été vu sur la structure de données « arbre » et sur « les algorithmes sur les arbres binaires ».

Comme nous l’avons déjà dit, Python ne propose pas de structure de données permettant d’implémenter directement les arbres binaires. Il va donc être nécessaire de créer cette structure. Pour programmer ce type de structure, nous allons utiliser le paradigme objet (à voir si pas encore étudier paradigme objet)

Vous trouverez ci-dessous la classe « ArbreBinaire » qui va nous permettre d’implémenter des arbres binaires.


class ArbreBinaire:
    def __init__(self, valeur):
        self.valeur = valeur
        self.enfant_gauche = None
        self.enfant_droit = None

    def insert_gauche(self, valeur):
        if self.enfant_gauche == None:
            self.enfant_gauche = ArbreBinaire(valeur)
        else:
            new_node = ArbreBinaire(valeur)
            new_node.enfant_gauche = self.enfant_gauche
            self.enfant_gauche = new_node

    def insert_droit(self, valeur):
        if self.enfant_droit == None:
            self.enfant_droit = ArbreBinaire(valeur)
        else:
            new_node = ArbreBinaire(valeur)
            new_node.enfant_droit = self.enfant_droit
            self.enfant_droit = new_node

   def get_valeur(self):
        return self.valeur

   def get_gauche(self):
        return self.enfant_gauche

   def get_droit(self):
        return self.enfant_droit

À faire vous-même 1

Étudiez attentivement la classe « ArbreBinaire » (méthodes et attributs). Vous pouvez, par exemple, vous interroger sur l’utilité de toutes les méthodes de cette classe.

Voici un exemple d’utilisation de cette classe pour construire un arbre binaire :

Soit l’arbre binaire suivant : Arbre 1

Voici le programme qui va permettre de construire cet arbre à l’aide de la classe « ArbreBinaire » :


class ArbreBinaire:
   def __init__(self, valeur):
      self.valeur = valeur
      self.enfant_gauche = None
      self.enfant_droit = None

   def insert_gauche(self, valeur):
      if self.enfant_gauche == None:
         self.enfant_gauche = ArbreBinaire(valeur)
      else:
         new_node = ArbreBinaire(valeur)
         new_node.enfant_gauche = self.enfant_gauche
         self.enfant_gauche = new_node

   def insert_droit(self, valeur):
      if self.enfant_droit == None:
         self.enfant_droit = ArbreBinaire(valeur)
      else:
         new_node = ArbreBinaire(valeur)
         new_node.enfant_droit = self.enfant_droit
         self.enfant_droit = new_node

   def get_valeur(self):
      return self.valeur

   def get_gauche(self):
      return self.enfant_gauche

   def get_droit(self):
      return self.enfant_droit

#######fin de la classe########

######début de la construction de l'arbre binaire###########

racine = ArbreBinaire('A')
racine.insert_gauche('B')
racine.insert_droit('F')

b_node = racine.get_gauche()
b_node.insert_gauche('C')
b_node.insert_droit('D')

f_node = racine.get_droit()
f_node.insert_gauche('G')
f_node.insert_droit('H')

c_node = b_node.get_gauche()
c_node.insert_droit('E')

g_node = f_node.get_gauche()
g_node.insert_gauche('I')

h_node = f_node.get_droit()
h_node.insert_droit('J')

######fin de la construction de l'arbre binaire###########

À faire vous-même 2

Étudiez attentivement le programme ci-dessus afin de comprendre le principe de « construction d’un arbre binaire »

Il est possible d’afficher un arbre binaire dans la console Python, pour cela, nous allons écrire une fonction « affiche ». Cette fonction renvoie une série de tuples de la forme (valeur,arbre_gauche, arbre_droite), comme « arbre_gauche » et « arbre_droite » seront eux-mêmes affichés sous forme de tuples, on aura donc un affichage qui ressemblera à : (valeur,(valeur_gauche,arbre_gauche_gauche,arbre_gauche_droite),(valeur_droite,arbre_droite_gauche,arbre_droite_droite)), mais comme « arbre_gauche_gauche » sera lui-même représenté par un tuple… Nous allons donc avoir des tuples qui contiendront des tuples qui eux-mêmes contiendront des tuples…

Pour l’arbre binaire défini ci-dessus, on aura :


('A', ('B', ('C', None, ('E', None, None)), ('D', None, None)), ('F', ('G', ('I', None, None), None), ('H', None, ('J', None, None))))

Voici le programme augmenté de la fonction « affiche » :


class ArbreBinaire:
   def __init__(self, valeur):
      self.valeur = valeur
      self.enfant_gauche = None
      self.enfant_droit = None

   def insert_gauche(self, valeur):
      if self.enfant_gauche == None:
         self.enfant_gauche = ArbreBinaire(valeur)
      else:
         new_node = ArbreBinaire(valeur)
         new_node.enfant_gauche = self.enfant_gauche
         self.enfant_gauche = new_node

   def insert_droit(self, valeur):
      if self.enfant_droit == None:
         self.enfant_droit = ArbreBinaire(valeur)
      else:
         new_node = ArbreBinaire(valeur)
         new_node.enfant_droit = self.enfant_droit
         self.enfant_droit = new_node

   def get_valeur(self):
      return self.valeur

   def get_gauche(self):
      return self.enfant_gauche

   def get_droit(self):
      return self.enfant_droit

#######fin de la classe########

######début de la construction de l'arbre binaire###########

racine = ArbreBinaire('A')
racine.insert_gauche('B')
racine.insert_droit('F')

b_node = racine.get_gauche()
b_node.insert_gauche('C')
b_node.insert_droit('D')

f_node = racine.get_droit()
f_node.insert_gauche('G')
f_node.insert_droit('H')

c_node = b_node.get_gauche()
c_node.insert_droit('E')

g_node = f_node.get_gauche()
g_node.insert_gauche('I')

h_node = f_node.get_droit()
h_node.insert_droit('J')

######fin de la construction de l'arbre binaire###########

def affiche(T):
   if T != None:
      return (T.get_valeur(),affiche(T.get_gauche()),affiche(T.get_droit()))

À faire vous-même 3

Vérifiez que « affiche(racine) » renvoie bien :


('A', ('B', ('C', None, ('E', None, None)), ('D', None, None)), ('F', ('G', ('I', None, None), None), ('H', None, ('J', None, None))))

N.B : la fonction « affiche » n’a pas une importance fondamentale, elle sert uniquement à vérifier que les arbres programmés sont bien corrects.

À faire vous-même 4

Programmez à l’aide de la classe « ArbreBinaire », l’arbre binaire suivant :

Arbre 2

Vérifiez votre programme à l’aide de la fonction « affiche »

Vous allez maintenant pouvoir commencer à travailler sur l’implémentation des algorithmes sur les arbres binaires :

À faire vous-même 5

Programmez la fonction « hauteur » qui prend un arbre binaire T en paramètre et renvoie la hauteur de T (algorithme correspondant, voir ici)