Parcours en largeur d'un arbre binaire
Le parcours en largeur (BFS) est un algorithme permettant de parcourir ou de rechercher dans des structures de données arborescentes. Il commence à la racine de l’arborescence (racine ou un noeud quelconque), et explore tous les nœuds voisins à la profondeur actuelle avant de passer aux nœuds à la prochaine niveau de profondeur.
le parcours en largeur de l'exemple ci-dessus est 30 16 40 9 20
Méthode 1
Il y a essentiellement deux fonctions dans cette méthode. L'une consiste à afficher tous les nœuds à un niveau donné (AfficheNiveau), l'autre effectuer le parcours en largeur de l'arbre (ParcoursLargeur). ParcoursLargeur utilise AfficheNiveau pour afficher un à un les nœuds à tous les niveaux, à partir de la racine.
ParcoursLargeur(Noeud)
Pour n = 1 à Hauteur(Noeud)
AfficheNiveau(Noeud, n);
AfficheNiveau(Noeud, niveau)
SI Noeud = NUL ALORS retourne;
SI niveau = 1 ALORS
ECRIRE(Noeud.val);
SINON SI niveau > 1, ALORS
AfficheNiveau(Noeud->gauche, niveau-1);
AfficheNiveau(Noeud->droit, niveau-1);
def ParcoursLargeur(Noeud):
h = Hauteur(Noeud)
for i in range(1, h+1):
AfficheNiveau(Noeud, i)
def AfficheNiveau(Noeud, niveau):
if Noeud is None:
return
if niveau == 1:
print(Noeud.val)
elif niveau > 1:
AfficheNiveau(Noeud.gauche, niveau-1)
AfficheNiveau(Noeud.droit, niveau-1)
def Hauteur(Noeud):
if Noeud is None:
return 0
else:
lheight = Hauteur(Noeud.gauche)
rheight = Hauteur(Noeud.droit)
return 1+max(lheight, rheight)
# tester la fonction
racine = Noeud(30)
racine.gauche = Noeud(16)
racine.droit = Noeud(40)
racine.gauche.gauche = Noeud(9)
racine.gauche.droit = Noeud(20)
ParcoursLargeur(racine)
Méthode 2
ParcoursLargeur(Noeud)
1) Créer une file d'attente vide "file"
2) temp_node = Noeud / * commencer à partir de la racine * /
3) Boucle lorsque temp_node n'est pas NUL
a) afficher temp_node.val.
b) Mettre en file d'attente "file" les enfants de temp_node (enfants gauche, puis enfant droit)
c) Retirer un noeud de la file et l’attribuer à temp_node
def ParcoursLargeur(Noeud):
if Noeud is None:
return
file = []
file.append(Noeud)
while(len(file) > 0):
# afficher et retirer le premier élément
print(file[0].val)
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)
# tester la fonction
racine = Noeud(30)
racine.gauche = Noeud(16)
racine.droit = Noeud(40)
racine.gauche.gauche = Noeud(9)
racine.gauche.droit = Noeud(20)
ParcoursLargeur(racine)
Partager ce cours avec tes amis :
Rédigé par
ESSADDOUKI
Mostafa
