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.