Arbres - Parcours

I. Retour sur les structures de données abstraites.⚓︎

Quelles techniques avons-nous pour accéder aux éléments ?

1. Pour le type abstrait liste :

Solution

Renvoyer la tête de la liste

2. Pour le type abstrait file :

Solution

Défiler

3. Pour le type abstrait pile :

Solution

Dépiler

4. Pour le type abstrait dictionnaire :

Solution

Accès par clé

. Pour le type list de python :

Solution

Accès par index, ou par élément

II. Rappel : Les Arbre binaires⚓︎

Arbres binaires

Un arbre binaire est une structure permettant de stocker une collection de données de même type.
Ce n'est pas une structure linéaire.
Le principal avantage des arbres par rapport aux listes est qu’ils permettent de ranger les données de telle sorte que les recherches soient plus efficaces.
Pour accéder à un élément quelconque d’un arbre , il faut "descendre" dans l’arbre jusqu’à cet élément.

Arbre généalogique de Louis XIV

Comme nous l'avons déjà vu, certaines données ont naturellement une structure d'arbre binaire. C'est le cas d'un arbre généalogique ascendant (recherche du père et de la mère) .

Exemple pour Louis XIV :

graph TD
D(Henri IV)
E(Maria de Medicis)
F(Felipe III d'Espagne)
G(Margareta d'Autriche)
B(Louis XIII)
C(Anna d'Autriche)
A(Louis XIV)
D --- B
E --- B
F --- C
G --- C
B --- A
C --- A

😊 De façon plus conforme à la théorie des arbres, nous aurions pu représenter cet arbre de la façon suivante, en plaçant la racine en haut :

graph TD
A(Louis XIV)
B(Louis XIII)
C(Anna d'Autriche)
D(Henri IV)
E(Maria de Medicis)
F(Felipe III d'Espagne)
G(Margareta d'Autriche)
A --- B
A --- C
B --- D
B --- E
C --- F
C --- G

Les parcours

Un parcours en largeur nous permettra de parcourir successivement toutes les personnes d'une même génération.
Un parcours en profondeur nous permettra de parcourir l'arbre "par branche".

III. 🏃‍ Parcours en largeur des arbres⚓︎

BFS

Ce parcours est parfois noté BFS pour Breadth-First Search
Le parcours en largeur correspond à un parcours par niveau de noeuds de l'arbre. Un niveau est un ensemble de nœuds ou de feuilles situés à la même profondeur.

👉 C'est un parcours étage par étage (de haut en bas) et de gauche à droite.

largeur

Dans cet exemple, on obtient successivement : 3, 1, 4, 5, 2, 0.

👉 Pour étudier cet algorithme de parcours en largeur, nous allons utiliser une file.

Les files

Quel est le principe d'une file ?

Solution

En informatique, une file (queue en anglais ) est une structure de données basée sur le principe «Premier entré, premier sorti», en anglais FIFO (First In, First Out), ce qui veut dire que les premiers éléments ajoutés à la file seront les premiers à être récupérés.

Le module queue de Python

Nous avons déjà vu plusieurs implémentations possibles des files, nous allons ici utiliser celle de Python : le module Queue

Extrait de la documentation en français de python sur le module Queue qui est une implémentation des files. (Documentation officielle)

Les objets Queue (Queue, LifoQueue ou PriorityQueue) fournissent les méthodes publiques décrites ci-dessous.

f = Queue() Créé une file vide nommée f.
f.qsize() renvoie la taille de la file f.
f.empty() renvoie True si la file f est vide, False sinon
f.put(item) ajoute item dans la file f
f.get() défile (retire) et renvoie l'élément défilé de la file f.

D'après le cours de Gilles Lassus

Méthode

On place l'arbre dans la file.
Tant que la file n'est pas vide, on procède comme suit :
- On défile, donc on récupère l'arbre situé en haut de la file.
- Si cet arbre n'est pas vide :
  - On garde son étiquette.
  - On enfile son sous-arbre gauche, puis son sous-arbre droit.

arbres BFS

À vous

Ecrire les états suivants de la file. Nous admettons ici qu'un arbre vide est None.

Solution

files arbre test

Classe Arbre simplifiée, sans encapsulation

Exécuter le script suivant :

Créer l'arbre tests

Compléter le script suivant pour créer l'arbre de la figure ci-dessus

Solution

Python

# arbre-test
a = Arbre(8)
a.left = Arbre(4)
a.right = Arbre(5)
a.left.left = Arbre(2)
a.left.right = Arbre(1)
a.right.right = Arbre(3)

À vous

Compléter le script suivant : la fonction parcours_BFS doit renvoyer la liste des noeuds obtenue par le parcours en largeur de l'arbre.

Solution

Python

def parcours_BFS(arbre):
    file = Queue()
    file.put(arbre)
    solution = []
    while not file.empty():
        a = file.get()
        if a is not None :
            solution.append(a.data)
            file.put(a.left)
            file.put(a.right)
    return solution

Tester

Tester ci-dessous la fonction parcours_BFS pour l'arbre test créé au-dessus.

Solution

Python

print(parcours_BFS(a))

✍ A noter ... et à mémoriser ... 🐘

f = File() # Création d'une file vide
f.enfiler(arbre)

tant que f non vide :
    arbre_au_sommet = f.defiler()
    si arbre_au_sommet n'est pas vide
        On garde son étiquette
        f.enfiler(son sous-arbre gauche)
        f.enfiler(son sous-arbre droit)
    fin si
fin tant que

IV. Les parcours en profondeur - Généralités⚓︎

Le principe

Dans le cas d'un parcours en profondeur, l'un des deux sous-arbres est complètement exploré avant que l'exploration du second ne commence.
On distingue trois types de parcours selon l'ordre dans lequel le sous-arbre de gauche, le sous-arbre droit et la racine sont explorés.

balade et contours

Pour parcourir un arbre en profondeur, on se "balade" autour de l'arbre de la façon suivante (en commençant toujours par la gauche) :

Les flèches numérotées en pointillé, qui sont représentées à côté des branches de l'arbre indiquent comment on se "balade" autour de l'arbre.

Ainsi on a les parcours successifs suivants:

la flèche 1 indique que l'on va de r à a
la flèche 2 indique que l'on va de a à c
la flèche 3 indique que l'on va de c à h
la flèche 4 indique que l'on va de h à c

etc.

👉 Nous avons donc la "balade" r, a, c, h, c, a, d, i, d, j, l, j, d, a, r, b, e, k, e, b, f, b, r , que l'on appelera le "contours";

balade 1

Source : https://math.univ-lyon1.fr/irem/IMG/pdf/parcours_arbre_avec_solutions-2.pdf

Première définition des trois parcours

On définit trois parcours des sommets de l’arbre :

L’ordre préfixe : on liste chaque sommet la première fois qu’on le rencontre dans la balade.
Chaque nœud est visité avant que ses deux fils le soient.
On part de la racine, on visite le fils gauche (et éventuellement le fils gauche de celui-ci, etc.) avant de remonter et de redescendre vers le fils droit.

Cela donne ici : r, a, c, h, d, i, j, l, b, e, k, f

l’ordre suffixe (aussi appelé postfixe en anglais) : on liste chaque sommet la dernière fois qu’on le rencontre.
Chaque nœud est visité après que ses deux fils le soient.
On visite le fils gauche, puis le fils droit, puis la racine

Cela donne ici : h, c, i, l, j, d, a, k, e, f , b, r

l’ordre infixe (plus compliqué!): chaque nœud est visité (listé) après son fils gauche mais avant son fils droit.
Si c'est une feuille il est donc listé (son fils gauche et son fils droit sont vides)
On visite le fils gauche, puis la racine, puis le fils droit

Cela donne ici : c, h, a, i ,d, l, j, r, k, e, b, f

😀 Ces trois parcours sont naturellement récursifs.

Deuxième définition des trois parcours

💡 On ajoute les fils fantômes manquants 😀

balade 2

On peut ainsi considérer qu’on passe une fois à gauche de chaque nœud (en descendant), une fois en dessous de chaque nœud, une fois à droite de chaque nœud (en remontant).

ordres préfixe, suffixe, infixe

Ordre préfixe : lorsque l'on passe à gauche des nœuds.

👉 Regarder cette vidéo : ordre préfixe

Ordre suffixe : lorsque l'on passe à droite des nœuds.

👉 Regarder cette vidéo : ordre suffixe

Ordre infixe : lorsque l'on passe sous les noeuds

👉 Regarder cette vidéo : ordre infixe

Exercice 1

ÉnoncéCorr. largeurCorr. préfixeCorr. infixeCorr. postfixe

Donner le rendu de chaque parcours :

Parcours en largeur
Parcours préfixe
Parcours infixe
Parcours postfixe

largeur : 1 2 3 4 5 6 7 8 9

préfixe : 1 2 4 5 7 8 3 6 9

infixe : 4 2 7 5 8 1 3 9 6

postfixe : 4 7 8 5 2 9 6 3 1

Exercice 2

ÉnoncéCorr. largeurCorr. préfixeCorr. infixeCorr. postfixe

Donner le rendu de chaque parcours :

Parcours en largeur
Parcours préfixe
Parcours infixe
Parcours postfixe

largeur : 9 8 7 6 2 5 1 4 3

préfixe : 9 8 6 2 1 7 5 4 3

infixe : 6 8 1 2 9 7 4 5 3

postfixe : 6 1 2 8 4 3 5 7 9

Exercice débranché : Expérimentons ces trois parcours dans le cas concret d'un labyrinthe

Voici un labyrinthe :

im lab

Les cercles vides sont des nœuds sans intersection, les cercles pleins sont des culs de sac, les carrés sont des intersections, l'entrée et la sortie sont marquées par un cercle plein dans un cercle vide.

Ce labyrinthe est parfait : chaque cellule est reliée à toutes les autres et, ce, de manière unique

Contrairement au labyrinthe étudié dans le cours sur les graphe, celui-ci peut donc être représenté par un arbre (il n'y a pas de cycle)

a. Faire la représentation de ce labyrinthe avec un arbre (sur feuille).

Pour nommer un nœud, il a été choisi de donner en premier le numéro de la colonne, et en deuxième le numéro de la ligne. Le nœud d'entrée est donc le (0,4) et celui de sortie le (5,4).
On part du nœud (0,4) qui sera la racine de cet arbre. Lorsqu'il n'y a qu'un fils, on convient de le placer obligatoirement à gauche, et lorsqu'il y a une intersection, placez bien entendu à gauche le nœud quand on va vers la gauche et à droite quand on va à droite.
👉 Pour simplifier, on notera 04 à la place (0, 4), 14 à la place de (1, 4) etc...

Dessin à faire sur votre feuille

b. Quelle est la hauteur de l'arbre ?

Solution

Réponse : 12

c. Quelle est la profondeur du nœud (5,4) ? Qu'est-ce que cette profondeur représente dans notre problème ?

Solution

Réponse : 9

C'est la longueur du plus court chemin vers la sortie.

d. Différents parcours en profondeur de cet arbre

💁🏻

📌Appelez votre professeur pour qu'il vous donne une version papier à compléter. Vous devez réaliser les trois parcours en profondeur vus (préfixe, suffixe et infixe) sur cet arbre.

Pour une question de mise en page quand il n'y a qu'un seul fils la flèche est dessinée verticale (et non vers la gauche)

Vous pouvez aussi télécharger ce document ici : 🌐 Arbres à compléter

Correction du parcours préfixe

préfixe

Correction du parcours suffixe

suffixe

Correction du parcours infixe

infixe

📌Quel est le parcours qui donne le chemin le plus court pour trouver la sortie?

Solution

Réponse : parcours suffixe

📌Aurions-nous pu trouver un chemin plus rapide?

Solution

Réponse : il suffit de faire (0,4), (1,4), (2,4), (3,4), (4,4), (4,3), (4,2), (5,2), (5,3), (5,4)

Remarque

🌵 La structure d'arbre n'est pas adaptée à la recherche de chemins, ou du plus court chemin. Nous verrons plus tard comment résoudre ce problème avec des parcours de graphe.

V. Implémentation des parcours en profondeur⚓︎

Une classe Arbre

Il faut absolument exécuter ce code pour pouvoir travailler ensuite.

1. Le parcours préfixe⚓︎

On donne le pseudo-code suivant :

fonction parcours_prefixe(arbre) :
    si arbre is not None :
        affiche arbre.valeur
        parcours_prefixe(arbre.gauche)
        parcours_prefixe(arbre.droit)

A vous de jouer 1

Compléter le code suivant, et le tester pour arbre1 (arbre ci-dessous)
Vérifier à la main que le résultat est bien correct.

flowchart TD
    a(A)
    b(B)
    c(C)
    d(D)
    e(E)
    f(F)
    g( )
    h( )
    i(G)
    a --- b
    a --- c
    b --- d
    b --- e
    c --- f
    c --- g
    d --- h
    d --- i
    linkStyle 5 stroke-width:0px;
    linkStyle 6 stroke-width:0px;
    style g opacity:0;
    style h opacity:0;

Solution

Python

# version simple avec print (renvoie None)
def parcours_prefixe(arbre) :
    if arbre is not None :
        print(arbre.valeur)
        parcours_prefixe(arbre.gauche)
        parcours_prefixe(arbre.droit)

# création de l'arbre :
arbre1 = Arbre("A")
arbre1.ajout_gauche("B")
arbre1.ajout_droit("C")
arbre1.gauche.ajout_gauche("D")
arbre1.gauche.ajout_droit("E")
arbre1.gauche.gauche.ajout_droit("G")
arbre1.droit.ajout_gauche("F")

# parcours
parcours_prefixe(arbre1)

A vous de jouer 2

Au lieu de simplement afficher les nœuds visités, nous allons en constituer la liste.

Compléter :

Évaluations restantes : 5/5

.128013kg[: r)S/N(.lo4yb=ac1x+ud3t2_Pwevp-fhmn]is050z0G0B0t0P0n0Q0f0u0n0t0Q0Q0s010B0P0I010406050Q0y0M0M0t0g0q040i0o0n0y0+0o0N050j0=0@0_0{0:0I04051b141e0j1b0:0z0P0H0Z0#0%0)0#0N0c0y0t0c0G0J0I0q0B0L120f0L0P0c0L0n1G0L0B0.050U0r0n0G1n0$0(011F1H1J1H0B1P1R1N0B0g1c1B0Z0~0Q0I0t0N0)0C011T1p010K0W0G0N0t0M0G1N1/1;1_1V1|1R1 210.0a0f0E0g0o0I0o0Q0P110N0f0S1-0g0g0G0u2m14240N1c0j1B2z1)1+1*1O0z261q0P0N1~2j1N1k1m0!1U2J2L0N0o2P1N0I2s1c2x2z2$0;1:2n2R1`2V0g0^0n1N0t1E2s0K0)030D0D0u2W0G1J2U0o0J0p0J0v0.0v140t2%2*0/2)252,1V2.2:2=2@0G2_012{2}2 312M340J1@040C3a3c1;3e2x2I013j0t2;1c2?0L2^2`2|2~0S3t2V3v0A0.0A3A2w3d0:3E3h0)3H3J053L3N3p3P3s2K3u350p0.0p3Y153d1f2!142P2C0z1+2H3%013Q221c401d3~2(3{3C05472#2*0f0P0z0)2|2x3v373K4k4m013/3R3;3T35370f2a0G4n3r4x324q1N0j3b3f2+1o1V0b0.0S0K3Z3C0f4N3F0N0K0.1:0g2~0y0g0Q0D2Z3n0P0w0G0D1J0Q0B0G4V2y4Y450-040l4{4i3g4P3(0.0_0r2s524}55014 0h0e520:4e4|3E4l4F4p353x3+4t4F473S335q1^4D5u3:4I5y2z3b0f5H4X3$5d4R040P4U5k045J4j450N570g594`5Q5S542S010o0F0.0P0Q525#4O5%0b0u0.0k125Z2$5/3F4 5h5!5j2(5m4u4o2*3U3l5n4v4G304y5x0J3V4C204E6a5v6d675F5R5I6q5c5;0.2s0B4*135!6s1`4 0d0O5i5b635o663?68646b5w3v3@6h215B4H3=344K5G5I6A4Q6u0T6x5.6!0)6C6G5T5d5V04585a5Q6*5(0.0m6-5$2-0.0H3I0G4*6|5:6B0.6E6z5K5%0o0.0x6)7a6~044%4)4+4-2^4:4=4@4_745}0.516@7g3i5W5Y7s457c046{7w6.5%6:0c0t0y0u0L5`3|7x6+0.0h7f7H1`7D7e797W7y7i0_7k4,4.1|4;4?5,7r7G6}1V4 7v627#566;5X6?7_7=0)7D7F7 757$0z2g2l7B5d5f6F6@0j4h3}0G2z4a2A42142D8n0t1Q8i3 1l3e0j0S0U0W0Q04.

Retenir

préfixe : RGD (racine, sous-arbre gauche, sous-arbre droit)

Racine en 1er

Parcours préfixe

fonction parcours_prefixe(arbre):
    si arbre is not None :
        affiche arbre.valeur
        parcours_prefixe(arbre.gauche)
        parcours_prefixe(arbre.droit)

👉 ou si on doit renvoyer une liste :

fonction parcours_prefixe(arbre):
    si arbre is None :
        renvoyer une liste vide
    sinon :
        renvoyer [arbre.valeur] + parcours_prefixe(arbre.gauche) + parcours_prefixe(arbre.droit)

2. Le parcours suffixe⚓︎

On donne le pseudo-code suivant :

fonction parcours_suffixe(arbre) :
    si arbre is not None :
        parcours_suffixe(arbre.gauche)
        parcours_suffixe(arbre.droit)
        affiche arbre.valeur

A vous de jouer 3

Compléter le code suivant, et le tester pour arbre1 (arbre ci-dessous)
Vérifier à la main que le résultat est bien correct.

flowchart TD
    a(A)
    b(B)
    c(C)
    d(D)
    e(E)
    f(F)
    g( )
    h( )
    i(G)
    a --- b
    a --- c
    b --- d
    b --- e
    c --- f
    c --- g
    d --- h
    d --- i
    linkStyle 5 stroke-width:0px;
    linkStyle 6 stroke-width:0px;
    style g opacity:0;
    style h opacity:0;

Solution

Python

def parcours_suffixe(arbre):
    if arbre is not None:
        parcours_suffixe(arbre.gauche)
        parcours_suffixe(arbre.droit)
        print(arbre.valeur)

A vous de jouer 4

Au lieu de simplement afficher les nœuds visités, nous allons en constituer la liste.

Compléter :

Évaluations restantes : 5/5

.128013kg[: r)S/N(.lo4y6b=ac1x+ud3t2_Pevp-fhmn]is050A0G0C0u0P0n0Q0f0v0n0u0Q0Q0t010C0P0I010406050Q0z0M0M0u0g0q040i0o0n0z0+0o0N050j0=0@0_0{0:0I04051b141e0j1b0:0A0P0H0Z0#0%0)0#0N0c0z0u0c0G0J0I0q0C0L120f0L0P0c0L0n1G0L0C0.050U0s0n0G1n0$0(011F1H1J1H0C1P1R1N0C0g1c1B0Z0~0Q0I0u0N0)0D011T1p010K0W0G0N0u0M0G1N1/1;1_1V1|1R1 210.0a0f0F0g0o0I0o0Q0P110N0f0S1-0g0g0G0v2m14240N1c0j1B2z1)1+1*1O0A261q0P0N1~2j1N1k1m0!1U2J2L0N0o2P1N0I2s1c2x2z2$0;1:2n2R1`2V0g0^0n1N0u1E2s0K0)030E0E0v2W0G1J2U0o0J0r0J0w0.0w140u2%2*0/2)252,1V2.2:2=2@0G2_012{2}2 312M340J1@040D3a3c1;3e2x2I013j0u2;1c2?0L2^2`2|2~0S3t2V3v0B0.0B3A2w3d0:3E3h0)3H3J053L3N3p3P3s2K3u350p0.0p3Y153d1f2!142P2C0A1+2H3%013Q221c401d3~2(3{3C05472#2*0f0P0A0)2|2x3v373K4k4m013/3R3;3T35370f2a0G4n3r4x324q1N0j3b3f2+1o1V0b0.0S0K3Z3C0f4N3F0N0K0.1:0g2~0z0g0Q0E0=0K1|0x0G0E1J0Q0C0G4V2y4Y450-040l4{4i3g4P3(0.0_0s2s524}55014 0h0e520:4e4|3E4l4F4p353x3+4t4F473S335q1^4D5u3:4I5y2z3b0f5H4X3$5d4R040P4U5k045J4j450N570g594`5Q5S542S010o0.0t0t525#4O5%0b0v0.0k125Z2$5.3F4 5h5!5j2(5m4u4o2*3U3l5n4v4G304y5x0J3V4C204E695v6c665F5R5I6p5c5:0.2s0C4*135!6r1`4 0d0O5i5b625o653?67636a5w3v3@6g215B4H3=0J3@6n6q5K6s046u6w5-6z3i4$0_4)4+4-0z4/0P4;4?0P4^5_3|6Z6A0.515Q6)5604585a706|1V5)040m6F5T5d5V040c0u0z0v0L6`4f770)5f6(7o5(0.0y7r7d5%7f4%6-4,4.4:4=4@4_7c5$6}507I5/2-5W5Y7M3F797b767x7O040A2g2l7R4~0.0h7w7J787u7*7N1V6B7$7e7P75617W7,7a7=7y0.0H3I0G4*7}7K6D5Q603|0j4h3}0G2z4a2A42142D8i0u1Q8d3 1l3e0j0S0U0W0Q04.

Retenir

suffixe : GDR (sous-arbre gauche, sous-arbre droit, racine)

Racine en dernier

Parcours suffixe

fonction parcours_suffixe(arbre) :
    si arbre is not None :
        parcours_suffixe(arbre.gauche)
        parcours_suffixe(arbre.droit)
        affiche arbre.valeur

👉 ou si on doit renvoyer une liste :

fonction parcours_suffixe(arbre) :
    si arbre is None :
        renvoyer une liste vide
    sinon :
        renvoyer parcours_suffixe(arbre.gauche) + parcours_suffixe(arbre.droit) + [arbre.valeur]

3. Le parcours infixe⚓︎

On donne le pseudo-code suivant :

fonction parcours_infixe(arbre) :
    si arbre is not None :
        parcours_infixe(arbre.gauche)
        affiche arbre.valeur
        parcours_infixe(arbre.droit)

A vous de jouer 5

Compléter le code suivant, et le tester pour arbre1 (arbre ci-dessous)
Vérifier à la main que le résultat est bien correct.

flowchart TD
    a(A)
    b(B)
    c(C)
    d(D)
    e(E)
    f(F)
    g( )
    h( )
    i(G)
    a --- b
    a --- c
    b --- d
    b --- e
    c --- f
    c --- g
    d --- h
    d --- i
    linkStyle 5 stroke-width:0px;
    linkStyle 6 stroke-width:0px;
    style g opacity:0;
    style h opacity:0;

Solution

Python

def parcours_infixe(arbre):
    if arbre is not None:
        parcours_infixe(arbre.gauche)
        print(arbre.valeur)
        parcours_infixe(arbre.droit)

A vous de jouer 6

Au lieu de simplement afficher les nœuds visités, nous allons en constituer la liste.

Compléter :

Évaluations restantes : 5/5

.128013kg[: r)S/N(.lo4yb=ac1x+ud3t28_Pwevp-fhmn]is050z0H0B0t0Q0n0R0f0u0n0t0R0R0s010B0Q0J010406050R0y0N0N0t0g0q040i0o0n0y0,0o0O050j0?0^0`0|0;0J04051c151f0j1c0;0z0Q0I0!0$0(0*0$0O0c0y0t0c0H0K0J0q0B0M130f0M0Q0c0M0n1H0M0B0/050V0r0n0H1o0%0)011G1I1K1I0B1Q1S1O0B0g1d1C0!0 0R0J0t0O0*0C011U1q010L0X0H0O0t0N0H1O1:1=1`1W1}1S20220/0a0f0F0g0o0J0o0R0Q120O0f0T1.0g0g0H0u2n15250O1d0j1C2A1*1,1+1P0z271r0Q0O1 2k1O1l1n0#1V2K2M0O0o2Q1O0J2t1d2y2A2%0=1;2o2S1{2W0g0_0n1O0t1F2t0L0*030E0E0u2X0H1K2V0o0K0D0K0v0/0v150t2(2+0:2*262-1W2/2;2?2^0H2`012|2~30322N350K1^040C3b3d1=3f2y2J013k0t2=1d2@0M2_2{2}2 0T3u2W3w0A0/0A3B2x3e0;3F3i0*3I3K053M3O3q3Q3t2L3v360p0/0p3Z163e1g2#152Q2D0z1,2I3(013R231d411e3 2)3|3D05482$2+0f0Q0z0*2}2y3w383L4l4n013:3S3=3U36380f2b0H4o3s4y334r1O0j3c3g2,1p1W0b0/0T0L3!3D0f4O3G0O0L0/1;0g2 0y0g0R0E2L1}0w0H0E1K0R0B0H4W2z4Z460.040l4{4j3h4Q3)0/0`0r2t524}55014 0h0e520;4f4|3F4m4G4q363y3,4u4G483T345q1_4E5u3;4J5y2A3c0f5H4Y3%5d4S040Q4V5k045J4k460O570g594`5Q5S542T010o0G0/0Q0R525#4P5%0b0u0/0k135Z2%5/3G4 5h5!5j2)5m4v4p2+3V3m5n4w4H314z5x0K3W4D214F6a5v6d675F5R5I6q5c5;0/2t0B4+145!6s1{4 0d0P5i5b635o663@68646b5w3w3^6h225B4I3?0K3^6o6r5K6t046v6x5.6A3j4%0`4*4,4.4#0Q4;4?5,4_6G5T5d4 515Q6*5604585a6 6!1{0o0/0m6`5$2.0/0c0t0y0u0M5`3}761W5f6)7m0*78040x7p6{5%6C7b5:7d725X74627w77797z4!0/0I3J0H4+7J4~0/6E6z7q5(0/7u7U7G6+044(6.4-4/6=4=4@6_757!0*6}7Q5d5V7C5Y7?5%7s7a7/7c7#0z2h2m7{6B0/0h6F6 0j4i3~0H2A4b2B43152E8j0t1R8e401m3f0j0T0V0X0R04.

Retenir

infixe : GRD (sous-arbre gauche, racine, sous-arbre droit)

Racine au milieu

Parcours infixe

fonction parcours_infixe(arbre) :
    si arbre is not None :
        parcours_infixe(arbre.gauche)
        affiche arbre.valeur
        parcours_infixe(arbre.droit)

👉 ou si on doit renvoyer une liste :

fonction parcours_infixe(arbre) :
    si arbre is None :
        renvoyer une liste vide
    sinon :
        renvoyer parcours_infixe(arbre.gauche) + [arbre.valeur]  + parcours_infixe(arbre.droit)

4. Quel parcours choisir ?⚓︎

Retenir

Nous avons vu que le parcours en largeur était pertinent pour avoir des renseignements plutôt par niveau, utile par exemple si on veut connaître les personnes d'une même génération.

Le parcours préfixe, parcourt l'arbre en profondeur plutôt de manière descendante, et le suffixe plutôt de manière ascendante.

Quel est l'intérêt du parcours infixe ?
Nous allons voir cela dans le paragraphe suivant. 😀

5. Parcours infixe sur un arbre binaire de recherche.⚓︎

Exemple

Le tri du bijoutier (d'après un sujet de l'APMEP)

Considérons le problème du bijoutier voulant trier par grosseur un tas de diamants : pour faire cette opération il se sert d’un tamis ce qui lui permet de séparer le tas initial en deux, et il recommence avec de nouveaux tamis pour chaque tas. On le comprend facilement l’efficacité du tri est fonction des trames des tamis utilisés.
Nous allons utiliser une idée similaire pour créer un arbre binaire, et pour construire les algorithmes permettant de le parcourir.
Mieux qu’un grand discours montrons la construction de l’arbre correspondant aux données 7, 3, 1, 8, 6.
Nous allons placer le premier élément 7 à la racine d'un arbre.
Principe du tamis : pour n'importe quel noeud, tous les noeuds se trouvant dans son sous-arbre gauche ont une valeur inférieure, et tous ceux se trouvant dans le sous arbre droit ont une valeur supérieure. Le sous arbre gauche correspond à ce qui est passé dans les trous du tamis, et le sous-arbre droit à ce qui est resté dans le tamis.
- 3 < 7 donc 3 est fils gauche de 7
- 1 < 3 donc 1 est fils gauche de 3
- 8 > 7 donc 8 est fils droit de 7. (on ne peut pas mettre 8 comme fils droit de 3, car sinon 8 serait dans le sous-arbre gauche de 7, ce qui est impossible car ce sous-arbre ne doit contenir que des nombres inférieurs à 7).
- 6 > 3 et 6 < 7 donc 6 est fils droit de 3.

On obtient l'arbre suivant :

Nous venons de créer un arbre binaire de recherche

Nous reviendrons plus tard en détail sur cette structure de données.

A vous de jouer 7

Reprenons cet exemple et implémentons le avec la classe Arbre du début.

Compléter ci-dessous. Que constatez-vous ?

Solution

Python

# Compléter ci-dessous
abr = Arbre(7)
abr.ajout_gauche(3)
abr.gauche.ajout_gauche(1)
abr.gauche.ajout_droit(6)
abr.ajout_droit(8)

On constate que l'on obtient les noeuds triés par ordre croissant.

😃

🐘 A retenir

Le parcours infixe sur un arbre binaire de recherche trie les noeuds de cet arbre.

👉 C'est un des très grands intérêts des arbres binaires de recherche, et du parcours infixe.

VI. TP final⚓︎

⌛ Avant de commencer

Vous devez travailler sur Basthon

Télécharger dans le même dossier :

🌐 Fichier module_tree_2021.py : "Clic droit", puis "Enregistrer la cible du lien sous"
🌐 TD parcours_arbre_labyrinthe_parfait_sujet_2023.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

😀 La correction est arrivée ...

Télécharger dans le même dossier :

🌐 Fichier module_tree_2021.py : "Clic droit", puis "Enregistrer la cible du lien sous"
🌐 Correction du TD parcours_arbre_labyrinthe_parfait_corr_2023_v2.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

VII. ✍ Bilan⚓︎

Parcours en largeur

aVoir <- fileVide
enfiler la racine
vus = listeVide (si on doit renvoyer le parcours)
tant que aVoir non vide :
    a <- defiler()
    visiter a (ajout dans une liste vus, ou affichage)
    si a.filsG not None: 
        enfiler a.filsG
    si a.filsD not None: 
        enfiler a.filsD

Parcours préfixe

def prefixe(arbre) :
    if arbre is None :
        return []
  else :
        return [arbre.valeur] + prefixe(arbre.filsG) +  prefixe(arbre.filsD)

Parcours suffixe

def suffixe(arbre) :
    if arbre is None :
        return []
    else :
        return  suffixe(arbre.filsG)  + suffixe(arbre.filsD) + [arbre.valeur]

Parcours infixe

def infixe(arbre) :
  if arbre is None :
      return []
  else :
      return  infixe(arbre.filsG) + [arbre.valeur] + infixe(arbre.filsD)

VIII. Vidéos pour approfondir⚓︎

Parcours préfixe

Parcours suffixe

😉 Le parcours suffixe se fait de façon analogue.

Parcours infixe

🌳 Crédits⚓︎

Jean-Louis Thirot , Mireille Coilhac, Valérie Mousseaux, Gilles Lassus