Théorie des graphes

Parcours d’un arbre binaire

Il existe 3 méthodes de parcours d’un arbre binaire

  • Parcours infixe : fils gauche, racine, fils droit
  • Parcours préfixe : racine, fils gauche, fils droit
  • Parcours postfixe : fils gauche, fils droit, racine

On ne peut réaliser ces différents parcours qu’en utilisant une pile, puisqu’on est obligé de commencer le parcours par la racine et d’empiler les nœuds dont on n’a pas encore rencontré. La pile peut être utilisée d’une manière explicite ou bien au moyen d’une procédure récursive.

Parcours préfixe

                Algorithme infixe (Noeud)
                    1. Parcourez le sous-arbre gauche, c’est-à-dire, appelez infixe(sous-arbre gauche)
                    2. Visitez la racine.
                    3. Parcourez le sous-arbre droit, c’est-à-dire appelez infixe(sous-arbre droit)
            
                def infixe(Noeud):
                    if Noeud==None:
                        return
                    if Noeud.gauche!=None:
                        infixe(Noeud.gauche) 
                    print(Noeud.val)
                    if Noeud.droit!=None:
                        infixe(Noeud.droit) 
            

Exemple: Dans l'example ci-dessus est 9 16 20 30 40.
Dans le cas des arbres binaires de recherche, le parcours préfixe donne des nœuds dans un ordre croissant

Parcours préfixe

                Algorithme prefixe(Noeud)
                    1. Visitez la racine.
                    2. Parcourez le sous-arbre gauche, c’est-à-dire, appelez prefixe(sous-arbre gauche)
                    3. Parcourez le sous-arbre droit, c’est-à-dire appelez prefixe(sous-arbre droit)
            
                def prefixe(Noeud):
                    if Noeud==None:
                        return
                    
                    print(Noeud.val)
                    if Noeud.gauche!=None:
                        prefixe(Noeud.gauche) 
                    
                    if Noeud.droit!=None:
                        prefixe(Noeud.droit)
            

Exemple: Dans l'example ci-dessus est 30 16 9 20 40.
Le parcours préfixe est utilisé pour créer une copie de l’arbre. Le parcours préfixe est également utilisé pour obtenir l’expression préfixe d’un arbre d’expression.

Parcours postfixe

                Algorithme postfixe(Noeud)
                    1. Parcourez le sous-arbre gauche, c’est-à-dire, appelez postfixe(sous-arbre gauche)
                    2. Parcourez le sous-arbre droit, c’est-à-dire appelez postfixe(sous-arbre droit)
                    3. Visitez la racine.
            
                def postfixe(Noeud):
                    if Noeud==None:
                        return
        
                    if Noeud.gauche!=None:
                        postfixe(Noeud.gauche) 

                    if Noeud.droit!=None:
                        postfixe(Noeud.droit)

                    print(Noeud.val)
                

Exemple: Dans l'example ci-dessus est 9 20 16 40 30.
Parcours postfixe est utilisé pour supprimer l’arbre. Parcours postfixe est également utilisé pour obtenir l'expression postfixe d'un arbre d'expression.


Partager ce cours avec tes amis :
Rédigé par Mostafa Sedoki
Professeur d'Informatique dans les CPGE

Cours Similaires :