13 - Parcours des Arbres Binaires
Nous allons voir aujourd'hui à quel point l'Arbre est une structure récursive.
Vous allez découvrir trois premières façons d'explorer un arbre noeud par noeud.
Logiciel nécessaire pour l'activité : -
Prérequis : Données : Arbre et Arbre Binaire
Evaluation ✎ :
Documents de cours : open document ou pdf
1 - Arbre Binaire
Nous allons représenter nos Arbres Binaires comme une structure qui est vide ou composée de noeuds reliés entre eux.
1er partie de la définition de l'arbre binaire
Un Arbre Binaire est :
- Le noeud mène vers un sous-arbre binaire gauche (potentiellement vide donc)
- Le noeud mène vers un sous-arbre binaire droite (potentiellement vide donc)
La distinction entre gauche et droite est fondamentale : placer un noeud à gauche plutôt qu'à droite doit être dû à une raison précise puisqu'il s'agit d'une arbre binaire et pas d'un arbre enraciné d'arité 2.
2e partie de la définition du type abstrait de données ARBRE BINAIRE : ses primitives
Description des primitives que nous allons utiliser
- nvABV() -> Arbre Binaire VIDE
- nvAB(e:Element, g:Arbre Binaire, d:Arbre Binaire) -> Arbre Binaire NON VIDE
- estABV(arbre:Arbre Binaire) -> bool
- racine(arbre:Arbre Binaire NON VIDE) -> Noeud
- gauche(arbre:Arbre Binaire NON VIDE) -> Arbre
- droite(arbre:Arbre Binaire NON VIDE) -> Arbre
- contenu(noeud:Noeud) -> Element
Crée un nouvel ARBRE BINAIRE vide.
On le note ainsi pour dire nouvelArbreBinaireVide() car c'est trop long.
Crée un nouvel ARBRE BINAIRE dont le noeud-racine porte l'étiquette e et mène vers les sous-arbres binaires g et d transmis.
Prédicat qui répond True si l'arbre binaire est un arbre binaire vide.
On le note ainsi pour dire estArbreBinaireVide() car c'est trop long.
Renvoie le noeud jouant le rôle de la racine pour l'arbre binaire NON VIDE reçu.
Renvoie le sous-arbre binaire gauche de arbre NON VIDE.
Renvoie le sous-arbre binaire droite de arbre NON VIDE.
Renvoie la valeur du Noeud.
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 (RGD)
- Suffixe ou postfixe : on lit la Racine à la fin (GDR)
- Infixe : on lit la Racine au milieu de la séquence (GRD), infixe comme intérieur.
2 - Parcours Préfixe R G D
Voici comment on réalise un parcours en profondeur préfixe de façon récursive dans un Arbre Binaire.
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 RGD.
- R : on explore d'abord le noeud actuel (la racine de l'arbre en cours donc),
- G : ensuite on explore le sous-arbre gauche
- D : puis on explore le sous-arbre droit
Parcours en profondeur Préfixe (sous forme d'une simple exploration qui ne renvoie rien)
La fonction visiter() reste à définir : il peut s'agir d'un simple affichage, même si cela ne sert pas à grand chose.
PREFIXE donc on utilise l'ordre RACINE - GAUCHE - DROITE.
Description des ENTREES / SORTIE
- ENTREE : Un Arbre Binaire
- Précondition : NON VIDE
- SORTIE : Rien sur l'exemple. Il s'agit d'une fonction d'affichage sur l'interface utilisateur, mais on pourrait les stocker dans un tableau et renvoyer le tableau.
On présente ici deux versions de l'algorithme : dans la première l'arbre binaire a comme précondition d'être NON VIDE, dans la deuxième version, il peut être vide ou pas.
Description de l'algorithme 1 récursif de parcourir(arbre: Arbre Binaire NON VIDE)
ENTREE : Un Arbre Binaire (Précondition : NON VIDE)
SORTIE : Rien (sur l'exemple)
visiter(racine(arbre))
SI NON estABV(gauche(arbre))
parcourir(gauche(arbre))
Fin SI
SI NON estVide(droite(arbre))
parcourir(droite(arbre))
Fin SI
Renvoyer VIDE
Description de l'algorithme récursif 2 de parcourir(arbre: Arbre Binaire)
ENTREE : Un Arbre Binaire
SORTIE : Rien (sur l'exemple)
SI NON estABV(arbre)
visiter(racine(arbre))
parcourir(gauche(arbre))
parcourir(droite(arbre))
Fin SI
Renvoyer VIDE
REMARQUE TRES IMPORTANTE
Il s'agit ici de SI (NON condition) et pas d'un SINON SI (condition).
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.
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...
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...
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 en entrée
...CORRECTION...
.
3 - Parcours suffixe (ou postfixe) G D R
Voici comment on réalise un parcours suffixe de façon récursive dans un Arbre Binaire : on explore d'abord le sous-arbre gauche puis droite et on finit par le noeud actuel.
SUFFIXE donc on utilise l'ordre GAUCHE - DROITE - RACINE.
- G : on explore d'abord le sous-arbre gauche
- D : puis on explore le sous-arbre droit
- R : enfin on explore le noeud actuel (la racine de l'arbre en cours donc)
Parcours Suffixe (sous forme d'une simple exploration qui ne renvoie rien)
La fonction visiter() reste à définir : il peut s'agir d'un simple affichage, même si cela ne sert pas à grand chose.
SUFFIXE donc on utilise l'ordre GAUCHE - DROITE - RACINE.
Description de l'algorithme récursif 1 parcourir(arbre: Arbre NON VIDE)
ENTREE : Un Arbre Binaire (Précondition : NON VIDE)
SORTIE : Rien (sur l'exemple)
SI NON estABV(gauche(arbre))
parcourir(gauche(arbre))
Fin SI
SI NON estABV(droite(arbre))
parcourir(droite(arbre))
Fin SI
visiter(racine(arbre))
Renvoyer VIDE
Description de l'algorithme récursif 2 de parcourir(arbre: Arbre Binaire)
ENTREE : Un Arbre Binaire
SORTIE : Rien (sur l'exemple)
SI NON estABV(arbre)
parcourir(gauche(arbre))
parcourir(droite(arbre))
visiter(racine(arbre))
Fin SI
Renvoyer VIDE
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.
...CORRECTION...
10° Retrouver les deux versions de l'algorithme.
...CORRECTION...
.
4 - Parcours infixe G R D
Voici comment on réalise un parcours infixe de façon récursive dans un Arbre Binaire : on explore d'abord le sous-arbre gauche puis le noeud actuel et on finit par le sous-arbre droit.
- G : on explore d'abord le sous-arbre gauche
- R : puis on explore le noeud actuel (la racine de l'arbre en cours donc),
- D : enfin on explore le sous-arbre droit
Parcours Infixe (sous forme d'une simple exploration qui ne renvoie rien)
La fonction visiter reste à définir : il peut s'agir d'un simple affichage, même si cela ne sert pas à grand chose.
INFIXE donc on utilise l'ordre GAUCHE - RACINE - DROITE.
On affiche donc tous les descendants du sous-arbre gauche avant d'afficher le noeud racine lui-même puis les descendants du sous-arbre droite.
Description de l'algorithme récursif 1 parcourir(arbre: Arbre NON VIDE)
ENTREE : Un Arbre Binaire (Précondition : NON VIDE)
SORTIE : Rien (sur l'exemple)
SI NON estABV(gauche(arbre))
parcourir(gauche(arbre))
Fin SI
visiter(racine(arbre))
SI NON estVide(droite(arbre))
parcourir(droite(arbre))
Fin SI
Renvoyer VIDE
Description de l'algorithme récursif 2 de parcourir(arbre: Arbre Binaire)
ENTREE : Un Arbre Binaire
SORTIE : Rien (sur l'exemple)
SI NON estABV(arbre)
parcourir(gauche(arbre))
visiter(racine(arbre))
parcourir(droite(arbre))
Fin SI
Renvoyer VIDE
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
15° Fournir un algorithme équivalent mais dont la PRECONDITION est simplement que le paramètre fourni est un ARBRE BINAIRE (potentiellement, il peut donc être un Arbre Vide).
...CORRECTION...
.
5 - Arbre d'une formule
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)
- * 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 inversée)
Plus compliqué :
Cette fois, la formule est (6+4) * (2*3).
Voici les 3 parcours :
- 6 + 4 * 2 * 3 en infixe.
- * + 6 4 * 2 3 en préfixe
- 6 4 + 2 3 * * en postfixe
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 ?
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)
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.
16° 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).
17° 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)
18° 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 rappeller 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"
6 - FAQ
Rien pour le moment
Activité publiée le 29 11 2020
Dernière modification : 05 12 2021
Auteur : ows. h.