Parcourir un arbre de différentes façons
Parcourir un arbre binaire
Cela consiste à consulter tous les nœuds de l’arbre, les uns après les autres, notamment dans le but de récupérer les valeurs des clés dans un ordre donné.
Il existe plusieurs façons de parcourir un arbre binaire : soit en « profondeur d’abord », en anglais Depth-First Search (DFS), soit en « largeur d’abord », en anglais Breadth-First Search (BFS).
Quelque soit la façon de parcourir un arbre binaire, les algorithmes mis en œuvre privilégient une méthode récursive.
Parcourir un arbre binaire, en profondeur d’abord
Il s’agit d’un parcours dit en « profondeur d’abord », en anglais Depth-First Search (DSF).
Le principe : on explore chaque branche complètement avant d’explorer la branche voisine.
Cela consiste à parcourir un arbre binaire depuis la racine en allant vers les feuilles, en explorant à chaque niveau, d’abord le sous-arbre gauche, puis le sous-arbre droit.
Chaque nœud est ainsi « visité » trois fois : une fois par la « gauche », une fois par le « dessous » et une fois par la « droite ».
Parcours d’un arbre binaire, en profondeur d’abord, ordre préfixe
L’ordre de parcours est qualifié de préfixe si la racine la valeur de la racine est prise en compte en premier, avant celles des deux sous-arbres.
Algorithme (approche récursive)
Si l’arbre est non vide, on note la valeur de la racine puis on parcourt son sous-arbre gauche puis son sous-arbre droit,
sinon c’est terminé
Le parcours en profondeur d’abord de type préfixe donne le résultat suivant :
A – B – D – E – G – H – C – F – I
Implémenter en Python une méthode qui permet de réaliser le parcours en profondeur d’abord d’ordre préfixe d’un arbre binaire, à partir de l’algorithme qui suit.
ordre infixe
ordre suffixe
ordre en largeur d’abord
Il s’agit d’un parcours dit en « largeur d’abord », en anglais Breadth-First Search (DSF).
Le principe : on explore l’arbre niveau par niveau, en considérant tous les nœuds d’un niveau.
L’ordre de parcours est qualifié de postfixe si la valeur de la racine est prise après celles des deux
sous-arbres.
Algorithme (approche récursive)
Si l’arbre est non vide,
on place l’arbre dans une file
tant que la file n’est pas vide, on défile un élément qui est un arbre
on affiche la valeur de la racine et on enfile chacun des deux sous arbres s’ils ne sont pas vides
<< Cliquez pour plus d’informations <<