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

The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.