Parcours des arbres

Il peut être nécessaire de parcourir l'ensemble des nœuds d'un arbre (pour les répertorier, pour réaliser une recherche, pour obtenir une liste triée avec un ABR, ou tout simplement pour transmettre un arbre d'un système à un autre dans un fichier texte...), mais au vu de la structure hiérarchique, il n'y a pas de parcours classique à priori (contrairement à la liste, ou le parcours est "naturel").
Voici quelques exercices de parcours d'arbre et leur correction.

Parcours en profondeur (d'abord)..ou DFS (Deep First Search)

Beaucoup d’algorithmes se résument à traiter individuellement chaque nœud de l’arbre (pour en faire la liste, pour effectuer un calcul...). On se donne donc une opération Traiter à appliquer à chaque nœud.
Dans le parcours en profondeur, on va profiter de la structure récursive de l'arbre binaire. Parcourir un arbre c'est :

parcourir le sous arbre gauche
parcourir le sous arbre droit

Reste a savoir quand traiter le nœud commun à ces deux sous arbres...

Avant de parcourir les deux sous arbres → parcours préfixe
Entre le parcours des deux sous arbres → parcours infixe
Après le parcours des deux sous arbres → parcours suffixe

Parcours préfixe

Dans ce parcours, nous traitons donc la racine avant de parcourir ses deux sous arbres. Par exemple pour l'arbre ci-dessous:

Parcours

( cochez pour l'exemple ci-dessous )

L'algorithme du parcours préfixe d'un arbre est donc le suivant :

		
parcoursPrefixe(Arbre):

Traiter la racine de l'arbre 

Si il y a un sous arbre gauche
	parcourir le sous arbre gauche

Si il y a un sous arbre droit
	parcourir le sous arbre droit

A vous de coder une fonction ( ou une méthode de la classe Arbre ) pour le parcours préfixe d'un arbre, et de la tester sur quelques exemples. Le traitement utilisé sera uniquement l'affichage de la valeur du nœud.

from classe_arbre import * def parcours_prefixe(arbre): pass arbre = Arbre('A', Arbre('B', Arbre('D', Arbre('H'), Arbre('I')), Arbre('E')), Arbre('C', Arbre('F'), Arbre('G', Arbre('J'))))

SOLUTION

Parcours infixe

Une fois que vous avez compris le parcours préfixe, les deux suivants sont très simples, il suffit de déplacer la place du traitement dans l'algorithme de parcours. Ainsi il devient :

		
parcoursInfixe(Arbre):

Si il y a un sous arbre gauche
	parcourir le sous-arbre gauche

Traiter la racine de l'arbre	

Si il y a un sous arbre gauche
	parcourir le sous-arbre droit

Parcours

( cochez pour l'exemple ci-dessous )

A vous de coder une fonction, ou une méthode, pour le parcours infixe d'un arbre et de la tester sur quelques exemples. Le traitement utilisé sera uniquement l'affichage de la valeur du nœud.

from classe_arbre import * def parcours_infixe(arbre): pass arbre = Arbre('A', Arbre('B', Arbre('D', Arbre('H'), Arbre('I')), Arbre('E')), Arbre('C', Arbre('F'), Arbre('G', Arbre('J'))))

SOLUTION

Parcours suffixe

Une fois que vous avez compris les deux autres parcours, le suffixe est évident. L'algorithme devient :

		
parcoursSufixe(Arbre):

Si il y a un sous arbre gauche
	parcourir le sous arbre gauche

Si il y a un sous arbre droit
	parcourir le sous arbre droit
	
Traiter la racine de l'arbre

Parcours

( cochez pour l'exemple ci-dessous )

A vous de coder une fonction, ou une méthode, pour le parcours suffixe d'un arbre et de la tester sur quelques exemples. Le traitement utilisé sera uniquement l'affichage de la valeur du nœud.

from classe_arbre import * def parcours_suffixe(arbre): pass arbre = Arbre('A', Arbre('B', Arbre('D', Arbre('H'), Arbre('I')), Arbre('E')), Arbre('C', Arbre('F'), Arbre('G', Arbre('J'))))

SOLUTION

Parcours en largeur (d'abord) d'un arbre

Le parcours en largeur est assez explicite, car les nœuds sont parcourus dans la largeur de l'arbre, par "niveaux" successifs :

Cependant on remarque que la structure récursive de l'arbre ne pourra pas être exploitée ici.
Pour réaliser ce parcours nous auront besoin d'un TAD linéaire que vous avez déjà utilisé : la file.

L'idée est la suivante :

Enfiler la racine
La défiler puis la traiter
Enfiler ses deux nœuds fils
Défiler le premier nœud fils, le traiter
Enfiler ses deux nœuds fils
etc...

File

Parcours

( cochez pour l'exemple ci-dessus )

Si l'on écrit l'algorithme correspondant on aura :

		
parcoursLargeur(arbre):
    arbre est un arbre
    
    file est une File
    Enfiler l'arbre dans la file
    
    Tant que la file n'est pas vide
        s = défiler la file
        Traiter s
    
        Si le fils gauche de s n'est pas vide
            Enfiler le fils gauche de s dans la file
        
        Si le fils droit de s n'est pas vide
            Enfiler le fils droit de s dans la file

A vous de coder ce parcours en largeur d'un arbre et de le tester. Le traitement d'un nœud sera là-aussi l'affichage de son étiquette.
Pensez à importer au préalable un module dans lequel se trouve le code pour manipuler une structure de file; vous pouvez également utiliser la classe deque du module collections, plus efficace.

from classe_arbre import * from file import * #from collections import deque def parcours_largeur(arbre): pass arbre = Arbre('A', Arbre('B', Arbre('D', Arbre('H'), Arbre('I')), Arbre('E')), Arbre('C', Arbre('F'), Arbre('G', Arbre('J'))))

SOLUTION

Application

Tri avec un ABR

Les arbres binaires de recherche sont des structures ordonnées complexes. Nous avons constaté que pour la recherche d'un élément qu'un ABR était équivalent à une liste triée.
L'intérêt de l'ABR étant la facilité d'insertion d'un élément.
Cette structure ordonnée peut nous permettre de trier un tableau.

Attention, lisez bien l'intégralité de ce paragraphe avant de vous lancer dans le codage !

Vous devez créer une fonction tri_ABR() prenant en paramètre un tableau non trié et renvoyant un tableau trié.
Vous devrez utiliser les classes Arbre ( du module classe_arbre ), ABR avec sa méthode inserer( classe que vous aurez sans doute intérêt à mettre aussi dans son propre module à importer par souci de clarté du code ) et une fonction de parcours d'arbre.
La fonction devra donc :

Créer un ABR à partir de la liste passée en argument
Parcourir cet arbre de façon judicieuse pour créer une liste triée.

Mais, avant de vous lancer tête la première dans le code, vous devez :

Lire ce paragraphe sur les tests unitaires
Proposer trois tests unitaires dans la docstring de votre fonction

Et seulement ENSUITE, vous commencerez à coder votre fonction.
Lors de la phase de test vous utiliserez bien sur le module doctest.

from classe_arbre import * import doctest class ABR(Arbre): def inserer (self, v): if self.valeur is None: return ABR(v, None, None) elif (v < self.valeur): if self.filsgauche is None: return ABR(self.valeur, ABR(v, None, None), self.filsdroit) else: return ABR(self.valeur, self.filsgauche.inserer(v), self.filsdroit) elif (v > self.valeur): if self.filsdroit is None: return ABR(self.valeur, self.filsgauche, ABR(v, None, None)) else: return ABR(self.valeur, self.filsgauche,self.filsdroit.inserer(v)) def tri_ABR(tab: list)->list: """ Utilise un ABR pour trier un tableau. TESTS : >>> .... >>> .... """ pass

Pour finir... un peu de complexité :

Rappeler la complexité minimum d'un tri
Quelle est la complexité de la construction de votre ABR ?
Quelle est la complexité de la construction de votre liste triée ?
En déduire la complexité de votre fonction. Cette méthode de tri est-elle efficace ?

SOLUTION

Arbres arithmétiques

Nous avons vu précédemment comment calculer une expression stockée dans un arbre arithmétique.
Mais comment obtenir cet arbre arithmétique ?

Vous devez coder une fonction encode_arbreArith(), qui prend en paramètre une chaîne de caractères contenant une expression arithmétique correcte, et qui la stocke dans un arbre arithmétique.
Nous avons déjà vu comment décoder un arbre arithmétique, mais les parcours d'arbre que nous venons de voir ne seraient-ils pas aussi une solution à ce problème ? A vous de trouver le parcours qui pourra résoudre le problème, et écrire une fonction decode_arbreArith qui utilise un parcours d'arbre arithmétique pour évaluer une expression préalablement codée.

from classe_arbre import * def encode_arbreArith(expr: str)->Arbre: pass def decode_arbreArith(arbre: Arbre)->int: pass

SOLUTION