Nous allons représenter nos Arbres Binaires comme une structure qui est vide ou composée de noeuds reliés entre eux.
(Rappel) 1.1 L'idée générale de l'arbre binaire (1er partie de la définition)
A - Définition récursive d'un Arbre Binaire
Un arbre binaire est composé
soit d'un arbre binaire VIDE∅ ;
soit d'un arbre binaire NON VIDE, un triplet (r,g,d) composé d'un noeud-racine r menant à deux sous-arbres
le sous-arbre binaire gauche g(qui peut donc être un arbre binaire VIDE ou NON VIDE)
le sous-arbre binaire droite d(qui peut donc être un arbre binaire VIDE ou NON VIDE)
B - Différences avec l'arbre enraciné
Il existe trois différences majeures entre les arbres enracinés et les arbres binaires :
L'arbre binaire peut être VIDE, alors qu'un arbre enraciné possède au moins un noeud-racine ;
Chaque noeud mène au maximum à deux enfants ;
Il doit exister une logique interne pour savoir si on place un enfant à gauche ou à droite de son parent : ce n'est pas un choix aléatoire. Dans le cas d'un arbre généalogique, on décide souvent de placer le père à gauche et la mère à droite.
C - Exemple
On peut représenter ou pas l'arbre VIDE. Ci-dessous, on utilise un symbole particulier : le petit carré jaune.
Voici deux arbres binaires différents :
Ces arbres binaires ne sont pas identiques car l'enfant-gauche de C est B sur le premier mais l'enfant-gauche de C est G sur le deuxième.
D - Remarque importante
Chaque noeud d'un arbre binaire non vide a au maximum deux enfants mais chaque arbre binaire a exactement deux sous-arbres binaires (puisque l'arbre binaire vide est un arbre binaire).
(Rappel) 1.2 Les primitives (2e partie de la définition de l'arbre binaire)
Voici la liste des primitives :
nvABV() -> Arbre Binaire VIDE
nvAB(v:Element, g:Arbre Binaire, d:Arbre Binaire) -> Arbre Binaire NON VIDE
estABV(arbre:Arbre Binaire) -> bool
racine(arbre:Arbre Binaire NON VIDE) -> Noeud
contenu(noeud:Noeud) -> Element
gauche(arbre:Arbre Binaire NON VIDE) -> Arbre Binaire
droite(arbre:Arbre Binaire NON VIDE) -> Arbre Binaire
Nous allons voir maintenant les 3 modes de parcours en profondeur (en profondeur car on s'enfonce rapidement plutôt que de tester tout l'étage où on se trouve).
Préfixe : on lit d'abord la Racine ([R]GD)
Suffixe ou postfixe : on lit la Racine à la fin (GD[R])
Infixe : on lit la Racine au milieu de la séquence (G[R]D), infixe comme intérieur.
Voici comment on réalise un parcours en profondeur préfixe de façon récursive dans un Arbre Binaire.
2.1 Parcours PREFIXE : [R]GD
Principe et exemple du PREFIXE
Préfixe veut dire qu'on explore d'abord la Racine de l'arbre en cours avant d'aller voir à Gauche et à Droite.
Séquence [R]GD.
[R] : d'abord, on visite() le noeud actuel (la racine de l'arbre en cours donc);
G : ensuite on explore le sous-arbre gauche;
D : enfin on explore le sous-arbre droite.
La fonction visiter() reste à définir : il peut s'agir d'un simple affichage de l'étiquette, même si cela ne sert pas à grand chose.
CLIQUER SUR L'IMAGE pour ANIMER ou STOPPER
ORDRE GAUCHE-DROITE
On notera qu'on peut également parler de parcours en profondeur préfixe en explorant RACINE puis DROITE puis GAUCHE.
Le tout est de préciser clairement comment vous explorez et de garder le même ordre tout le long de l'exploration.
2.2 Algo Parcours PREFIXE d'Arbre NON VIDE
Il existe deux versions de l'algorithme : dans la première la précondition est que l'arbre soit NON VIDE, dans la deuxième version, il peut être vide ou pas.
Descriptions des ENTREES / SORTIE
ENTREE : Un Arbre Binaire
Précondition : NON VIDE
SORTIE : Rien sur l'exemple, simple fonction d'affichage. Mais on pourrait les stocker dans un tableau et renvoyer le tableau.
Description de l'ALGORITHME avec précondition
Description de parcourir(arbre: Arbre Binaire NON VIDE)
visiter(racine(arbre))
SINON estABV(gauche(arbre))
parcourir(gauche(arbre))
Fin SI
SINON estABV(droite(arbre))
parcourir(droite(arbre))
Fin SI
RenvoyerVIDE
Note importante pour éviter une erreur bête
Il s'agit ici de SI (NON condition) et pas d'un SINON SI (condition).
2.3 Algo Parcours PREFIXE d'Arbre sans précondition
Il existe deux versions de l'algorithme : dans la première la précondition est que l'arbre soit NON VIDE, dans la deuxième version, il peut être vide ou pas.
Description des ENTREES et SORTIE
ENTREE : Un Arbre Binaire
SORTIE : Rien sur l'exemple, simple fonction d'affichage. Mais on pourrait les stocker dans un tableau et renvoyer le tableau.
Description de l'ALGORITHME (sans précondition)
Description de parcourir(arbre: Arbre Binaire)
SINON estABV(arbre)
visiter(racine(arbre))
parcourir(gauche(arbre))
parcourir(droite(arbre))
Fin SI
RenvoyerVIDE
Note importante pour éviter une erreur bête
Il s'agit ici de SI (NON condition) et pas d'un SINON SI (condition).
01° Appliquer cet algorithme à l'Arbre Binaire ci-dessous en considérant que la fonction visiter() affiche simplement le résultat dans une interface imaginaire.
...CORRECTION DETAILLEE...
On commence par la racine :
Ensuite, on part dans le sous-arbre Gauche :
On y lit la racine :
On part dans le sous-arbre Gauche :
On part dans le sous-arbre Droit :
On part dans le sous-arbre Droit initial:
On lit la racine :
On explore à gauche(vide) puis à droite :
02° Appliquer cet algorithme à l'Arbre Binaire ci-dessous en considérant que la fonction visiter() affiche simplement le résultat dans une interface imaginaire.
...CORRECTION...
CLIQUER SUR L'IMAGE pour ANIMER ou STOPPER
03° Appliquer cet algorithme à l'Arbre Binaire ci-dessous en considérant que la fonction visiter affiche simplement le résultat dans une interface imaginaire.
...CORRECTION...
CLIQUER SUR L'IMAGE pour ANIMER ou STOPPER
04° Appliquer cet algorithme à l'Arbre Binaire ci-dessous en considérant que la fonction visiter() affiche simplement le résultat dans une interface imaginaire.
...CORRECTION...
05° Fournir les deux versions de l'algorithme sans regarder votre cours.
La version avec un arbre binaire NON VIDE en entrée
La version avec simplement un arbre binaire (quelconque) en entrée
Voici comment on réalise un parcours en profondeur suffixe de façon récursive dans un Arbre Binaire.
3.1 Parcours SUFFIXE / POSTFIXE : GD[R]
Principe et exemple du PREFIXE ou POSTFIXE
Suffixe veut dire qu'on explore la Racine de l'arbre en cours après avoir explorer Gauche et à Droite.
Séquence GD[R].
G : d'abord on explore le sous-arbre gauche;
D : puis on explore le sous-arbre droite;
R : enfin, on visite() le noeud actuel (la racine de l'arbre en cours).
La fonction visiter() reste à définir.
CLIQUER SUR L'IMAGE pour ANIMER ou STOPPER
ORDRE GAUCHE-DROITE
On notera qu'on peut également parler de parcours en profondeur suffixe en explorant RACINE puis DROITE puis GAUCHE.
Le tout est de préciser clairement comment vous explorez et de garder le même ordre tout le long de l'exploration.
On peut donc considérer DG[R] plutôt que GD[R].
3.2 Algo Parcours SUFFIXE-POSTFIXE d'Arbre NON VIDE
Il existe deux versions de l'algorithme : dans la première la précondition est que l'arbre soit NON VIDE, dans la deuxième version, il peut être vide ou pas.
Descriptions des ENTREES / SORTIE
ENTREE : Un Arbre Binaire
Précondition : NON VIDE
SORTIE : Rien sur l'exemple, simple fonction d'affichage. Mais on pourrait les stocker dans un tableau et renvoyer le tableau.
Description de l'ALGORITHME avec précondition
Description de parcourir(arbre: Arbre Binaire NON VIDE)
SINON estABV(gauche(arbre))
parcourir(gauche(arbre))
Fin SI
SINON estABV(droite(arbre))
parcourir(droite(arbre))
Fin SI
visiter(racine(arbre))
RenvoyerVIDE
Note importante pour éviter une erreur bête
Il s'agit ici de SI (NON condition) et pas d'un SINON SI (condition).
3.3 Algo Parcours SUFFIXE - POSTFIXE d'Arbre sans précondition
Il existe deux versions de l'algorithme : dans la première la précondition est que l'arbre soit NON VIDE, dans la deuxième version, il peut être vide ou pas.
Description des ENTREES et SORTIE
ENTREE : Un Arbre Binaire
SORTIE : Rien sur l'exemple.
Description de l'ALGORITHME (sans précondition)
Description de parcourir(arbre: Arbre Binaire)
SINON estABV(arbre)
parcourir(gauche(arbre))
parcourir(droite(arbre))
visiter(racine(arbre))
Fin SI
RenvoyerVIDE
Note importante pour éviter une erreur bête
Il s'agit ici de SI (NON condition) et pas d'un SINON SI (condition).
06° Appliquer cet algorithme à l'Arbre Binaire ci-dessous en considérant que la fonction visiter() affiche simplement le résultat dans une interface imaginaire.
...CORRECTION...
...CORRECTION DETAILLEE...
On commence par le sous-arbre gauche :
On y cherche le sous-arbre Gauche :
On part dans le sous-arbre Droit :
On y lit la racine :
On part dans le sous-arbre droit initial :
On lit le sous-arbre Gauche vide puis le sous-arbre Droit :
On lit la racine :
On lit la racine :
07° Appliquer cet algorithme à l'Arbre Binaire ci-dessous en considérant que la fonction visiter() affiche simplement le résultat dans une interface imaginaire.
...CORRECTION...
08° Appliquer cet algorithme à l'Arbre Binaire ci-dessous en considérant que la fonction visiter() affiche simplement le résultat dans une interface imaginaire.
...CORRECTION...
09° Appliquer cet algorithme à l'Arbre Binaire ci-dessous en considérant que la fonction visiter() affiche simplement le résultat dans une interface imaginaire.
Voici comment on réalise un parcours en profondeur infixe de façon récursive dans un Arbre Binaire.
4.1 Parcours INFIXE : G[R]D
Principe du INFIXE
Infixe veut dire qu'on explore la racine au milieu du parcours.
Séquence G[R]D.
G : D'abord on explore le sous-arbre gauche;
[R] : ensuite, on visite() le noeud actuel (la racine de l'arbre en cours donc);
D : enfin on explore le sous-arbre droite.
La fonction visiter() reste à définir.
ORDRE GAUCHE-DROITE
On notera qu'on peut également parler de parcours en profondeur infixe en explorant RACINE puis DROITE puis GAUCHE.
Le tout est de préciser clairement comment vous explorez et de garder le même ordre tout le long de l'exploration.
4.2 Algo Parcours INFIXE d'Arbre NON VIDE
Il existe deux versions de l'algorithme : dans la première la précondition est que l'arbre soit NON VIDE, dans la deuxième version, il peut être vide ou pas.
Descriptions des ENTREES / SORTIE
ENTREE : Un Arbre Binaire
Précondition : NON VIDE
SORTIE : Rien sur l'exemple.
Description de l'ALGORITHME avec précondition
Description de parcourir(arbre: Arbre Binaire NON VIDE)
SINON estABV(gauche(arbre))
parcourir(gauche(arbre))
Fin SI
visiter(racine(arbre))
SINON estABV(droite(arbre))
parcourir(droite(arbre))
Fin SI
RenvoyerVIDE
Note importante pour éviter une erreur bête
Il s'agit ici de SI (NON condition) et pas d'un SINON SI (condition).
4.3 Algo Parcours SUFFIXE - POSTFIXE d'Arbre sans précondition
Il existe deux versions de l'algorithme : dans la première la précondition est que l'arbre soit NON VIDE, dans la deuxième version, il peut être vide ou pas.
Description des ENTREES et SORTIE
ENTREE : Un Arbre Binaire
SORTIE : Rien sur l'exemple.
Description de l'ALGORITHME (sans précondition)
Description de parcourir(arbre: Arbre Binaire)
SINON estABV(arbre)
parcourir(gauche(arbre))
visiter(racine(arbre))
parcourir(droite(arbre))
Fin SI
RenvoyerVIDE
Note importante pour éviter une erreur bête
Il s'agit ici de SI (NON condition) et pas d'un SINON SI (condition).
11° Appliquer cet algorithme à l'Arbre Binaire ci-dessous en considérant que la fonction visiter() affiche simplement le résultat dans une interface imaginaire.
...CORRECTION...
G C B A E F
...CORRECTION DETAILLEE...
On commence par le sous-arbre gauche :
On y cherche le sous-arbre Gauche :
On y lit la racine :
On part dans le sous-arbre Droit :
On revient à la racine :
On part dans le sous-arbre Droit initial:
On lit le sous-arbre Gauche vide puis la racine :
On explore à droite :
12° Appliquer cet algorithme à l'Arbre Binaire ci-dessous en considérant que la fonction visiter() affiche simplement le résultat dans une interface imaginaire.
...CORRECTION...
D B E A F C G
13° Appliquer cet algorithme à l'Arbre Binaire ci-dessous en considérant que la fonction visiter() affiche simplement le résultat dans une interface imaginaire.
...CORRECTION...
E D C G F B A
14° Appliquer cet algorithme à l'Arbre Binaire ci-dessous en considérant que la fonction visiter() affiche simplement le résultat dans une interface imaginaire.
...CORRECTION...
G H C B A E D F
Après ces versions récursives des parcours, nous allons réaliser les versions itératives.
Et pour cela, nous allons devoir associer nos arbres à des piles.
15° Comment créer une pile, empiler, dépiler, tester si la pile est vide et lire le sommet rapidement en Python ?
...CORRECTION...
.
16° Ecrire les trois fonctions de parcours en version itérative. Votre fonction devra être documentée et devra afficher les noeuds traités. Le seul paramètre de votre fonction sera l'arbre qu'on désire parcourir.
...CORRECTION...
.
17° Modifier vos fonctions : elles doivent maintenant renvoyer un tableau contenant la liste des noeuds rencontrés pendant le parcours.
L'une des utilisations typiques des arbres est celle de la représentation d'une formule logique ou arithmétique.
La racine de l'Arbre est alors l'opérateur utilisé (dans le cas d'Arbre Binaire, il ne s'agit que d'opérateurs à deux paramètres).
Un exemple ? Voici comment on peut représenter 5*4 :
La racine est l'opérateur binaire à utiliser : la multiplication.
Les deux sous-arbres font référence au terme de gauche (5 ici) et au terme de droite (4 ici).
Que donne le parcours en profondeur de cet arbre binaire basique ?
5 * 4 en infixe (on retrouve la notation que vous connaissez, celle avec l'opérateur au milieu des arguments)
* 5 4 en préfixe (on appelle cela la notation polonaise car son utilisation est due à Jan Łukasiewicz).
5 4 * en postfixe (on appelle cela la notation polonaise inverse)
Arbre représentant une formule : exemple 2
Plus compliqué :
Cette fois, la formule est (6+4) * (2*3).
Voici les 3 parcours :
6 + 4 * 2 * 3 en infixe.
On voit bien que sans les parenthèses, il est difficile en lisant cet arbre en infixe de retrouver la formule encodée : est-ce (6+4)*(2*3) ou (6+(4*2)*3) ou encore autre chose ?
* + 6 4 * 2 3 en préfixe
Cette fois, pas besoin de parenthèses pour retrouver la formule : il suffit de savoir que les opérateurs utilisés sont tous des opérateurs binaires.
On trouve d'abord un opérateur binaire *. Il doit y avoir les deux termes derrière.
Le premier terme commence par un +, un opérateur binaire. On doit donc trouver ses deux termes derrière.
* (+ 6 4) * 2 3
On trouve ensuite un opérateur binaire + qui devrait être suivi de ses deux termes.
* (+ 6 4) (* 2 3)
L'opérateur central est donc la multiplication et on obtient
(6+4) * (2*3)
6 4 + 2 3 * * en postfixe
Même principe que précédemment mais... à l'envers.
On commence par 6 et 4, les deux termes nécessaires pour l'opérateur +.
(6 4 +) 2 3 * *
On trouve ensuite un 2 et un 3 dont l'opérateur est * :
(6 4 +) (2 3 *) *
On peut en déduire que les deux termes entre parenthèses sont reliés par la multiplication finale.
18° Retrouver la formule dont le parcours préfixe donne ceci :
+ 4 * 2 10
...CORRECTION...
+ 4 * 2 10
Opérateur + menant à un terme 4 et un autre terme qui commence par l'opérateur *.
Cet opérateur * est suivi de ces deux termes : 2 et 10.
+ 4 (* 2 10)
On en déduit que la formule est 4 + (2*10).
19° Retrouver la formule dont le parcours préfixe donne ceci :
/ * 2 10 - 8 6
...CORRECTION...
/ * 2 10 - 8 6
Opérateur / menant à un premier terme qui commence par l'opérateur *.
Cet opérateur * est suivi de ces deux termes : 2 et 10.
/ (* 2 10) - 8 6
On trouve ensuite le deuxième terme qui commence par - et des deux termes 8 et 6.
/ (* 2 10) (- 8 6)
La formule est donc (2*10) / (8-6)
20° Fournir les trois parcours de la formule logique dont l'Arbre est fourni ci-dessous.
...CORRECTION...
Pour conclure, j'ai pris juste au dessus un exemple très calculatoire de l'utilisation des arbres. Mais on peut également trouver de très nombreux exemples issus plus directement de la logique. Voici comment on peut représenter une démonstration ou une réflexion en informatique ou en logique mathématique. Cela devrait, peut-être, vous rappeler d'autres cours de Terminale : la flèche est ici le symbole de l'implication.
Au début de la IVe partie du discours, Descartes rencontre un premier principe de vérité : le fait que le sujet applique l’instrument du doute à sa propre existence, prouve paradoxalement son existence. Si « je » doute, il faut bien que « je » pense. On arrive alors à cette conclusion : "Je pense, donc je suis".
Première réflexion : "Je doute" ⇒ "Je pense"
Deuxième réflexion : "Je pense" ⇒ "Je suis"
Au total : "Je doute" ⇒ "Je pense" ⇒ "Je suis"
On notera qu'il est dangereux d'appliquer la logique mathématique et informatique à des propositions qui ne sont pas des objets mathématique ou informatique. Ici, je le fais juste pour vous montrer qu'on peut formaliser des choses que vous pensiez peut-être difficilement formalisable sous forme informatique. Mais mélanger les notions non-mathématiques à la logique est souvent source de mauvaise interprétation. Attention.
Table de vérité de l'implication
Nous avons déjà rencontré l'implication lors de l'activité sur les fonctions :
TYPES et PRECONDITIONS valides permet de garantir que la POSTCONDITION est valide.
TYPES et PRECONDITONS invalides permet de garantir... rien. La POST CONDITION peut être valide, ou pas. On n'en sait rien.
Expression a (Preconditions ?)
Expression b (Postcondition ?)
a ⇒ b
Pourquoi ?
FAUX
FAUX
VRAI
Si les préconditions donnent FAUX, la postcondition peut être FAUX, donc A IMPLIQUE B est VRAI sur cette ligne.
FAUX
VRAI
VRAI
Si les préconditions donnent FAUX, la postcondition peut être VRAI, donc A IMPLIQUE B est VRAI sur cette ligne.
VRAI
FAUX
FAUX
Si les préconditions donnent VRAI, la postcondition doit être VRAI, donc A IMPLIQUE B est FAUX sur cette ligne.
VRAI
VRAI
VRAI
Si les préconditions donnent VRAI, la postcondition doit être VRAI, donc A IMPLIQUE B est VRAI sur cette ligne.
