Insertion et suppression d'un élément de l'arbre binaire
Insertion dans un arbre binaire
L'idée est de faire un parcours en largeur itératif de l'arbre donné en utilisant une file d'attente
inserer(val)
1) nouveau=Noeud(val) /* créer un noeud */
1) Créer une file d'attente vide file
2) temp_node = Noeud / * commencer à partir de la racine * /
3) Tanque temp_node n'est pas NUL
a) SI temp_node.gauche est NUL ALORS
temp_node.gauche=nouveau
retourne
b) SINON SI temp_node.gauche est NUL ALORS
temp_node.droit=nouveau
retourne
FINSI
c) Mettre en file d'attente file les enfants de temp_node (enfants gauche, puis enfant droit)
d) Retirer un noeud de file et l’attribuer à temp_node
class Noeud:
def __init__(self, key):
self.gauche = None
self.droit = None
self.val = key
def Inserer(Noeud, val):
nouveau=Noeud(val)
file = []
file.append(Noeud)
while(len(file) > 0):
# retirer l'élément en tête de la file
node = file.pop(0)
# si l'enfant gauche est vide
if node.gauche is None:
node.gauche=nouveau
break
# si l'enfant droit est vide
elif node.droit is None:
node.gauche=nouveau
break
else:
file.append(node.gauche)
file.append(node.droit)
# tester la fonction
racine = Noeud(30)
racine.gauche = Noeud(16)
racine.droit = Noeud(40)
racine.gauche.gauche = Noeud(9)
racine.gauche.droit = Noeud(20)
racine.insert(5)
Suppression d'un noeud dans un arbre binaire
Dans un arbre binaire, supprimer un noeud d'un arbre binaire consiste à remplacer le noeud a supprimer par le noeud le plus profond à l'extrême droite
L'idée est de faire un parcours en largeur de l'arbre donné en utilisant une file d'attente pour retrouver le noeud à l'extrême droite et le noeud à supprime
1) En partant de la racine, recherchez le nœud le plus profond à l'extrême droite d'arbre binaire et le nœud à supprimé.
2) Remplacez les données du nœud de l'extrême droite par le nœud a supprimer.
3) Supprimez ensuite le nœud le plus profond à l'extrême droite.
class Noeud:
def __init__(self, key):
self.gauche = None
self.droit = None
self.val = key
# retourner le noeud à l'extereme droit avec son parent
def noeudExtreme(noeud):
file = []
file.append(noeud.droit)
node = None
parent = noeud
while (len(file) > 0):
node = file.pop(0)
# ajouter l'enfant gauche de l'élément retiré
if node.gauche is not None:
file.append(node.gauche)
# ajouter l'enfant droit de l'élément retiré
if node.droit is not None:
file.append(node.droit)
parent = noeud
return (node, parent)
# trouver le noeud a supprimer
def TrouverNoeud(noeud, cle):
file = []
file.append(noeud)
node = None
while (len(file) > 0):
node = file.pop(0)
if node.val == cle:
return node
# ajouter l'enfant gauche de l'élément retiré
if node.gauche is not None:
file.append(node.gauche)
# ajouter l'enfant droit de l'élément retiré
if node.droit is not None:
file.append(node.droit)
# afficher les noeuds
def afficher(noeud):
file = []
file.append(noeud)
node = None
while (len(file) > 0):
node = file.pop(0)
print(node.val)
# ajouter l'enfant gauche de l'élément retiré
if node.gauche is not None:
file.append(node.gauche)
# ajouter l'enfant droit de l'élément retiré
if node.droit is not None:
file.append(node.droit)
def suppression(noeud, cle):
assert noeud != None
extreme, parent = noeudExtreme(noeud)
elm = TrouverNoeud(noeud, cle)
if elm is not None:
elm.val = extreme.val
# supprimer le nœud le plus profond à l'extrême droite
if parent.gauche == extreme.val:
parent.gauche = None
else:
parent.droit = None
racine = Noeud(30)
racine.gauche = Noeud(16)
racine.droit = Noeud(40)
racine.gauche.gauche = Noeud(9)
racine.gauche.droit = Noeud(20)
suppression(racine, 9)
Partager ce cours avec tes amis :
Rédigé par
ESSADDOUKI
Mostafa
