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