Un arbre binaire est soit vide, représenté en Python par la valeur None
, soit un nœud, contenant une étiquette et deux sous-arbres gauche et droit et représenté par une instance de la classe Noeud
donnée ci-dessous.
class Noeud:
"""Classe représentant un noeud d'un arbre binaire"""
def __init__(self, etiquette, gauche, droit):
"""Crée un noeud de valeur etiquette avec
gauche et droit comme fils."""
self.etiquette = etiquette
self.gauche = gauche
self.droit = droit
def parcours(arbre, liste):
"""parcours récursivement l'arbre en ajoutant les étiquettes
de ses noeuds à la liste passée en argument en ordre infixe."""
if arbre != None:
parcours(arbre.gauche, liste)
liste.append(arbre.etiquette)
parcours(arbre.droit, liste)
return liste
La fonction récursive parcours
renvoie la liste des étiquettes des nœuds de l’arbre implémenté par l’instance arbre
dans l’ordre du parcours en profondeur infixe à partir d’une liste vide passée en argument.
Compléter le code de la fonction insere
, présenté page suivante, qui prend en argument un arbre binaire de recherche arbre
représenté ainsi et une étiquette cle
, non présente dans l’arbre, et qui :
cle
s’il est vide ;cle
sinon ;Tester ensuite ce code en utilisant la fonction parcours
et en insérant successivement des nœuds d’étiquette 1, 4, 6 et 8 dans l’arbre binaire de recherche représenté ci- dessous :
def insere(arbre, cle):
"""insere la cle dans l'arbre binaire de recherche
représenté par arbre.
Retourne l'arbre modifié."""
if arbre == None:
return Noeud(cle, None, None) # creation d'une feuille
else:
if ...:
arbre.gauche = insere(arbre.gauche, cle)
else:
arbre.droit = ...
return arbre
Test 1
|
|
Test 2
|