Enonce
La classe ABR ci-dessous permet d'implémenter une structure d'arbre binaire de recherche.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 | class Noeud:
def __init__(self, valeur):
'''MĂ©thode constructeur pour la classe Noeud.
Paramètre d'entrée : valeur (str)'''
self.valeur = valeur
self.gauche = None
self.droit = None
def getValeur(self):
'''MĂ©thode accesseur pour obtenir la valeur du noeud
Aucun paramètre en entrée'''
return self.valeur
def droitExiste(self):
'''MĂ©thode renvoyant True si l'enfant droit existe
Aucun paramètre en entrée'''
return (self.droit is not None)
def gaucheExiste(self):
'''MĂ©thode renvoyant True si l'enfant gauche existe
Aucun paramètre en entrée'''
return (self.gauche is not None)
def inserer(self, cle):
'''Méthode d'insertion de clé dans un arbre binaire de recherche
Paramètre d'entrée : cle (int)'''
if cle < ...:
# on insère à gauche
if self.gaucheExiste():
# on descend à gauche et on retente l'insertion de la clé
...
else:
# on crée un fils gauche
self.gauche = ...
elif cle > ... :
# on insère à droite
if ... :
# on descend à droite et on retente l'insertion de la clé
...
else:
# on crée un fils droit
... = Noeud(cle)
|
Compléter la fonction récursive inserer afin qu'elle permette d’insérer un nœud
dans l’arbre binaire de recherche proposé, à l’aide de sa clé.
Voici un exemple d'utilisation :
>>> arbre = Noeud(7)
>>> for cle in (3, 9, 1, 6):
arbre.inserer(cle)
>>> arbre.gauche.getValeur()
3
>>> arbre.droit.getValeur()
9
>>> arbre.gauche.gauche.getValeur()
1
>>> arbre.gauche.droit.getValeur()
6