Algo Arbre Parcours

Identification

Infoforall

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 :

  • soit un arbre binaire vide
  • soit l'ensemble d'un noeud et de deux sous-arbres binaires
    • 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

    1. nvABV() -> Arbre Binaire VIDE
    2. Crée un nouvel ARBRE BINAIRE vide.
      On le note ainsi pour dire nouvelArbreBinaireVide() car c'est trop long.

    3. nvAB(e:Element, g:Arbre Binaire, d:Arbre Binaire) -> Arbre Binaire NON VIDE
    4. 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.

    5. estABV(arbre:Arbre Binaire) -> bool
    6. 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.

    7. racine(arbre:Arbre Binaire NON VIDE) -> Noeud
    8. Renvoie le noeud jouant le rôle de la racine pour l'arbre binaire NON VIDE reçu.

    9. gauche(arbre:Arbre Binaire NON VIDE) -> Arbre
    10. Renvoie le sous-arbre binaire gauche de arbre NON VIDE.

    11. droite(arbre:Arbre Binaire NON VIDE) -> Arbre
    12. Renvoie le sous-arbre binaire droite de arbre NON VIDE.

    13. contenu(noeud:Noeud) -> Element
    14. 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).

    1. Préfixe : on lit d'abord la Racine (RGD)
    2. Suffixe ou postfixe : on lit la Racine à la fin (GDR)
    3. 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.

    1. R : on explore d'abord le noeud actuel (la racine de l'arbre en cours donc),
    2. G : ensuite on explore le sous-arbre gauche
    3. 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.

    Animation du parcours en profondeur préfixe RGD
    CLIQUER SUR L'IMAGE pour ANIMER ou STOPPER

    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.

    Arbre question 10

    ...CORRECTION DETAILLEE...

    On commence par la racine :

    Arbre question 1

    Ensuite, on part dans le sous-arbre Gauche :

    Arbre question 1

    On y lit la racine :

    Arbre question 1

    On part dans le sous-arbre Gauche :

    Arbre question 1

    On part dans le sous-arbre Droit :

    Arbre question 1

    On part dans le sous-arbre Droit initial:

    Arbre question 1

    On lit la racine :

    Arbre question 1

    On explore à gauche(vide) puis à droite :

    Arbre question 1

    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.

    Arbre question 16

    ...CORRECTION...

    Animation du parcours en profondeur préfixe RGD
    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.

    Arbre question 18

    ...CORRECTION...

    Animation du parcours en profondeur préfixe RGD
    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.

    Arbre question 18

    ...CORRECTION...

    Arbre question 4

    05° Fournir les deux versions de l'algorithme sans regarder votre cours.

    1. La version avec un arbre binaire NON VIDE en entrée
    2. 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.

    1. G : on explore d'abord le sous-arbre gauche
    2. D : puis on explore le sous-arbre droit
    3. 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.

    Animation du parcours en profondeur suffixe GDR
    CLIQUER SUR L'IMAGE pour ANIMER ou STOPPER

    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.

    Arbre question 10

    ...CORRECTION...

    Arbre question 6

    ...CORRECTION DETAILLEE...

    On commence par le sous-arbre gauche :

    Arbre question 1

    On y cherche le sous-arbre Gauche :

    Arbre question 1

    On part dans le sous-arbre Droit :

    Arbre question 1

    On y lit la racine :

    Arbre question 1

    On part dans le sous-arbre droit initial :

    Arbre question 1

    On lit le sous-arbre Gauche vide puis le sous-arbre Droit :

    Arbre question 1

    On lit la racine :

    Arbre question 1

    On lit la racine :

    Arbre question 1

    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.

    Arbre question 16

    ...CORRECTION...

    Arbre question 7

    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.

    Arbre question 18

    ...CORRECTION...

    Arbre question 8

    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.

    Arbre question 18

    ...CORRECTION...

    Arbre question 9

    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.

    1. G : on explore d'abord le sous-arbre gauche
    2. R : puis on explore le noeud actuel (la racine de l'arbre en cours donc),
    3. 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.

    Arbre question 11

    ...CORRECTION...

    G C B A E F

    Arbre question 1

    ...CORRECTION DETAILLEE...

    On commence par le sous-arbre gauche :

    Arbre question 1

    On y cherche le sous-arbre Gauche :

    Arbre question 1

    On y lit la racine :

    Arbre question 1

    On part dans le sous-arbre Droit :

    Arbre question 1

    On revient à la racine :

    Arbre question 1

    On part dans le sous-arbre Droit initial:

    Arbre question 1

    On lit le sous-arbre Gauche vide puis la racine :

    Arbre question 1

    On explore à droite :

    Arbre question 1

    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.

    Arbre question 16

    ...CORRECTION...

    D B E A F C G

    Arbre question 12

    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.

    Arbre question 18

    ...CORRECTION...

    E D C G F B A

    Arbre question 13

    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.

    Arbre question 18

    ...CORRECTION...

    G H C B A E D F

    Arbre question 14

    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 :

    Arbre de la formule 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é :

    Arbre de la formule (6+4)*(2*3)

    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.

    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.

    Arbre logique

    ...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.

    Je doute implique je pense implique je suis

    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.

    6 - FAQ

    Rien pour le moment

    Après cette introduction à l'exploration des arbres, il reste à voir pourquoi trois méthodes, comment choisir et voir s'il existe d'autres façons de faire. Mais, c'est pour la prochaine fois.

    Activité publiée le 29 11 2020
    Dernière modification : 05 12 2021
    Auteur : ows. h.