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)
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.