Parcours d'un arbre binaire en largeur d'abord
Principe
L'arbre est parcouru en commençant à la racine puis tous les noeuds voisins à la profondeur actuelle avant de passer aux noeuds au prochain niveau de profondeur.
Algorithme
Text Only
VARIABLES
T : arbre
Tg : arbre
Td : arbre
x : noeud
f : file (initialement vide)
DEBUT
PARCOURS-LARGEUR(T) :
enfiler(T.racine, f) //on place la racine dans la file
tant que f non vide :
x ← defiler(f)
affiche x.clé
si x.gauche ≠ vide :
Tg ← x.gauche
enfiler(Tg.racine, f)
fin si
si x.droit ≠ vide :
Td ← x.droite
enfiler(Td.racine, f)
fin si
fin tant que
FIN
Implémentation en Python
🐍 Script Python
def ParcoursLargeur(T: tree):
f = []
f.append(T[0])
while len(f) > 0:
x = f.pop()
print(x.value)
if x.left != None:
Tg = x.left
f.insert(0, Tg[0])
if x.right != None:
Td = x.right
f.insert(0, Td[0])