Théorie des graphes

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 Mostafa Sedoki
Computer science teacher and the founder of the e-learning platform "developpement-informatique.com", my mission is to provide high-quality courses for free to all computer science students and teachers

Cours Similaires :