adplus-dvertising

Parcours d’un arbre binaire

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 infixe

                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) 
                                                
def parcours_infixe(a):
    if len(a) == 0:
        return([])
    else:
        return parcours_infixe(a[1]) + [a[0]] + parcours_infixe(a[2])
                                                

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)
                                                
def parcours_prefixe(a):
    if len(a) == 0:
        return([])
    else:
        return [a[0]] + parcours_prefixe(a[1]) + parcours_prefixe(a[2])
                                                

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)
                                                
def parcours_postfixe(a):
    if len(a) == 0:
        return([])
    else:
        return parcours_postfixe(a[1]) + parcours_postfixe(a[2]) + [a[0]]
                                                

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 ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.