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 (1er partie de la définition de l'arbre binaire)
A - Description
Un arbre binaire est composé
soit d'un arbre binaire VIDE
soit d'un arbre binaire NON VIDE composé d'un noeud menant à deux sous-arbres
le sous-arbre binaire gauche peut être un arbre binaire VIDE ou un arbre binaire NON VIDE
le sous-arbre binaire droite peut être un arbre binaire VIDE ou un arbre binaire NON VIDE
Il existe deux 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.
un arbre binaire n'est pas juste un arbre où chaque noeud peut avoir deux fils au maximum. Le positionnement à gauche ou à droite doit suivre une logique interne de positionnement, ce n'est pas un choix aléatoire. Dans le cas d'un arbre généalogique, on pourrait ainsi placer le père à gauche et la mère à droite dans tout l'arbre binaire. Ou faire le choix inverse, mais dans tout l'arbre.
On symbolise parfois l'arbre vide par un symbole particulier sur les arbres binaires. Ci-dessous, c'est un petit carré jaune.
B - Exemple
Ci-dessous, vous trouverez deux arbres binaires différents :
Ces arbres binaires ne sont pas identiques car le fils-gauche de C est B sur le premier mais le fils gauche de C est G sur le deuxième.
S'il s'agissait de deux arbres enracinés, il s'agirait par contre du même arbre. Il serait simplement représenté de deux façons différentes.
(Rappel) 1.2 Les primitives (2e partie de la définition de l'arbre binaire)
Je le décris ici sous forme d'un type immuable, mais on pourait faire la même chose en muable.
nvABV() -> Arbre Binaire VIDE
Crée un nouvel ARBRE BINAIRE vide.
On le note ainsi pour dire nouvelArbreBinaireVide() mais c'est plus long.
nvAB(v:Element, g:Arbre Binaire, d:Arbre Binaire) -> Arbre Binaire NON VIDE
Crée un nouvel ARBRE BINAIRE dont la racine porte la valeur v et mène aux sous-arbres transmis à la fonction, g et d.
estABV(arbre:Arbre Binaire) -> bool
Prédicat qui renvoie True si l'arbre est un arbre binaire vide.
racine(arbre:Arbre Binaire NON VIDE) -> Noeud
Renvoie le noeud jouant le rôle de la racine pour cet arbre binaire NON VIDE.
contenu(noeud:Noeud) -> Element
Renvoie l'élément rattaché au noeud transmis.
gauche(arbre:Arbre Binaire NON VIDE) -> Arbre Binaire
Renvoie le sous-arbre gauche de arbre. On obtient bien un Arbre. Si vous voulez le noeud gauche, il faudra appliquer en plus la fonction racine().
droite(arbre:Arbre Binaire NON VIDE) -> Arbre Binaire
Renvoie le sous-arbre droite de arbre.
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.
