Parcours d’un arbre binaire

Do you have difficulties understanding French courses? visit our English version Click here

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) 
            

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 M. ESSADDOUKI

Many people realize their hearts desires late in life. Continue learning, never stop striving and keep your curiosity sharp, and you will never become too old to appreciate life.

0 Commentaire(s)

Pour laisser un commentaire vous devez avoir un compte Inscription, ou Se connecter