# Arbres : Exercice de parcours en largeur
**Exercice :** Effectuer en python le parcours en largeur d'un arbre.
**Rappel :** Lorsque l'on parcourt l'arbre en *"largeur"* on commence par explorer les frères/soeurs avant d'explorer les fils.
**Rappel :** Par convention, on préfère explorer de gauche a droite.
## Ressources
### Classes Arbre et Noeud
```python=
class Noeud:
def __init__(self, cle):
self.cle = cle
class Arbre:
def __init__(self, cle):
self.racine = Noeud(cle)
self.sag = None # Le sous-arbre gauche, qui est lui-même un arbre
self.sad = None # Le sous-droit gauche, qui est lui-même un arbre
```
### Classe File
```python!
class File:
def __init__(self):
self.liste = []
def enfiler(self, e):
self.liste.append(e)
def defiler(self):
if len(self.liste) != 0:
e = self.liste[0]
self.liste = self.liste[1:]
return e
else:
return None
def estVide(self):
if len(self.liste) == 0:
return True
else:
return False
```
## Jeux de tests : exemples d'arbres pour faire des tests
Le premier arbre que vous pouvez utiliser pour faire vos tests est celui présent à la page 276 de votre manuel :
**Rappels :**
- La racine de cet arbre est A
- Les feuilles de cet arbre sont : D, E, G, I
- Il s'agit d'un arbre binaire (au maximum deux fils par noeud). Il n'est ni localement complet, ni complet (le noeud *B* a un seul fils, de même pour *H*).
- Cet arbre est de taille 9 (on peut compter 9 noeuds)
- La hauteur de cet arbre est de 3 (le noeud le plus distant de la racine a une hauteur de 3, en effet, H(I) = 3). Attention, on compte les arêtes depuis la racine et pas les noeuds. Il s'agit d'une distance.
Construction de cet arbre a partir de notre classe *Arbre* :
```python=
arbre1 = Arbre('A')
arbre1.sag = Arbre('B')
arbre1.sag.sag = Arbre('C')
arbre1.sag.sag = Arbre('C')
arbre1.sag.sag.sag = Arbre('D')
arbre1.sag.sag.sad = Arbre('E')
arbre1.sad = Arbre('F')
arbre1.sad.sag = Arbre('G')
arbre1.sad.sad = Arbre('H')
```
Le deuxième arbre que vous pouvez utiliser pour faire vos tests est celui dessiné par Guillaume au tableau :
**Rappels :**
- La racine de cet arbre est A
- Les feuilles de cet arbre sont : J, I, H, L, K
- Il s'agit d'un arbre binaire qui n'est ni complet, ni localement complet.
- Cet arbre est de taille 12.
- Cet arbre est de hauteur 4
- On peut utiliser les mots : *hauteur*, *profondeur* et *niveau* de manière équivalente.
Construction de cet arbre a partir de notre classe *Arbre* :
```python=
arbre2 = Arbre('A')
arbre2.sag = Arbre('C')
arbre2.sad = Arbre('B')
arbre2.sag.sag = Arbre('F')
arbre2.sag.sag.sag = Arbre('J')
arbre2.sag.sag.sad = Arbre('I')
arbre2.sad.sag = Arbre('E')
arbre2.sad.sad = Arbre('D')
arbre2.sad.sag.sag = Arbre('H')
arbre2.sad.sad = Arbre('D')
arbre2.sad.sad.sag = Arbre('G')
arbre2.sad.sad.sag.sag = Arbre('L')
arbre2.sad.sad.sag.sad = Arbre('K')
```
# Resolution de l'exercice
## Determiner les interfaces
On commence par determiner le prototype de la fonction a implementer :
```python=
parcoursLargeur(a : Arbre) -> list
```
On écrit une fonction qui prend un unique paramètre : l'arbre que l'on veut parcourir. Elle retourne une liste qui contient les clés des noeuds qui ont été parcourus, dans l'ordre dans lequel ils ont été parcourus.
## Solution
### 1) La solution "officielle"
L'essentiel ici est d'avoir l'idee d'utiliser une structure de file qui va servir a stocker le "travail" qui reste a realiser ainsi que l'ordre dans lequel il faut le realiser.
```python=
def parcoursLargeur(a : Arbre) -> list:
result = [] # On cree une liste vide pour stocker les cles des noeuds que l'on a parcourus
f = File() # On cree une file vide, elle sert a stocker le "travail" qui reste a realiser et l'ordre dans lequel il faut le faire. Il s'agit des prochains elements a parcourir au fur et a mesure qu'on les decouvre.
f.enfiler(a) # Avant toute chose, on enfile la racine, c'est le prochain element a traiter
# On verifie les entrees pour eviter de faire des calculs sur n'importe quoi. On sors de la fonction et on avertit l'utilisateur en cas de pb.
if a == None:
print("Erreur vous avez demande le parcours d'un arbre vide")
return None
# On continue le parcours tant qu'il reste du travail a faire dans la file ...
while not f.estVide():
courant = f.defiler() # On recupere dans la file le travail a realiser. Il s'agit du sous-arbre courant a traiter
result.append(courant.racine.cle) # On indique que l'on vient de le parcourir (ajout a la liste)
# On teste la presence de sous-arbres gauche et droit.
# Si ils sont existants, on les ajoute a la file des prochains elements a parcourir ...
if courant.sag != None:
f.enfiler(courant.sag)
if courant.sad != None:
f.enfiler(courant.sad)
return result
```
**Remarque :** L'ordinateur n'a pas une vision globale de l'arbre en entier comme nous (humains) on peut l'avoir du premier coups d'oeil. C'est du a notre maniere de decrire l'arbre dans la classe *Arbre*. En effet, lorsque l'on considere un arbre *A*, les seules informations dont dispose l'ordinateur sont :
- la racine
- un "lien" vers la racine du SAG
- un "lien" vers la racine du SAD
Il va etre oblige de se balader progressivement de lien en lien jusque les avoir tous parcourus. C'est la que la notion d'exploration et de parcours prends son sens.
**Remarque :** Dans cet algorithme, si on remplace la structure de file par une pile, alors on obtient un parcours en profondeur.
**Remarque :** Cet algorithme n'est pas recursif.
### 2) La solution d'Augustin
```python=
# Fonction sans File qui permet de parcourir un arbre en largeur
def parcoursLargeur(arbre : Arbre) -> list:
element = [arbre.Racine.clef]
liste_de_sous_arbre = [arbre]
while len(liste_de_sous_arbre) > 0:
nouveau_sous_arbre = []
for i in range(len(liste_de_sous_arbre)):
if liste_de_sous_arbre[i].Sag is not None:
nouveau_sous_arbre.append(liste_de_sous_arbre[i].Sag)
element.append(liste_de_sous_arbre[i].Sag.Racine.clef)
if liste_de_sous_arbre[i].Sad is not None:
nouveau_sous_arbre.append(liste_de_sous_arbre[i].Sad)
element.append(liste_de_sous_arbre[i].Sad.Racine.clef)
liste_de_sous_arbre = nouveau_sous_arbre
return element
```
**Remarque :** La solution d'Augustin est equivalente a la precedente. Il n'utilise pas la classe *File*, mais son utilisation astucieuse des listes est equivalente au passage par une file.
## Les resultats attendus :
Pour *arbre1* le parcours en largeur donne :
```python
['A', 'B', 'F', 'C', 'G', 'H', 'D', 'E', 'I']
```
Pour *arbre2* le parcours en largeur donne :
```python
['A', 'C', 'B', 'F', 'E', 'D', 'J', 'I', 'H', 'G', 'L', 'K']
```
# Deuxieme etape : Recherche d'un maximum dans l'arbre
On profite de la capacite a explorer un arbre pour effectuer un traitement sur les donnees qu'il peut contenir. On considere un arbre modifie qui embarque/encapsule de l'information a l'interieur de ses noeuds. Dans ce cas precis on va stocker un nombre dans chaque noeud, on veut ecrire une fonction qui retourne la cle du noeud qui contient la plus grande valeur ainsi que la valeur de ce maximum.
## Modification des classes Noeud et Arbre
On ajoute un attribut *'data'* a la classe *Noeud*, il contient l'information contenue a l'interieur de celui-ci. Ici, on considerera qu'il s'agit toujours d'un nombre.
On modifie le constructeur de la classe en consequence :
```python=
class Noeud:
def __init__(self, cle, data):
self.cle = cle
self.data = data
class Arbre:
def __init__(self, cle, data):
self.racine = Noeud(cle, data)
self.sag = None
self.sad = None
```
## Construction du jeu de tests
On cree un arbre de test, on pourra alors executer notre algorithme dessus pour essayer de se convaincre que notre code fonctionne tel que prevu.
```python=
a = Arbre('A', 10)
a.sag = Arbre('B', 42)
a.sag.sag = Arbre('C', 55)
a.sag.sag.sag = Arbre('D', 17)
a.sag.sag.sad = Arbre('E', 21)
a.sad = Arbre('F', 32)
a.sad.sag = Arbre('G', 26)
a.sad.sad = Arbre('H', 101)
a.sad.sad.sad = Arbre('I', 1)
```
## Determiner les interfaces
Comme toujours, avant de commencer a ecrire du code, on s'interroge sur les entrees/sorties de notre fontion et sur leur nature. Ici, on veut ecrire une fonction qui prend en parametre un objet de type *Arbre* et qui renvoie un couple constitue de :
- la cle du noeud qui contient le maximum (chaine de caracteres)
- la valeur de ce maximum (entier)
```python
rechercheMax(a : Arbre) -> (str, int)
```
## Le programme de recherche de maximum
```python
def rechercheMax(a):
f = File()
f.enfiler(a)
val_max = a.racine.data # Variable temporaire qui contient la valeur max rencontree jusque-la (a ce stade de l'exploration de l'arbre)
cle_max = a.racine.cle # Variable temporaire qui contient cle du noeud ayant la valeur max
if a == None:
print("Erreur vous avez demande le parcours d'un arbre vide")
return None
while not f.estVide():
courant = f.defiler()
if courant.racine.data > val_max:
val_max = courant.racine.data
cle_max = courant.racine.cle
if courant.sag != None:
f.enfiler(courant.sag)
if courant.sad != None:
f.enfiler(courant.sad)
return (cle_max, val_max)
```
## Test et resultat attendu
On execute la fonction sur l'arbre *a* construit auparavent :
```python
print(rechercheMax(a))
```
Le resultat est le suivant :
```python
('H', 101)
```
Sign in with Wallet
Connect another wallet