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 - Qu'est-ce qu'un Arbre Binaire au fond

Nous allons représenter nos Arbres Binaires comme une structure qui est vide ou composée de noeuds reliés entre eux.

Ces noeuds possèdent un identifiant et comportent trois informations :

  • Un attribut e (pour etiquette) qui contient l'informatique basique qu'on veut associer à ce noeud
  • Un attribut g (pour gauche) qui contient la référence du noeud-fils gauche ou qui fait référence à VIDE.
  • Un attribut d (pour droite) qui contient la référence du noeud-fils droit ou qui fait référence à VIDE.
1er partie de la définition de l'arbre binaire

Un arbre binaire est :

  • soit un arbre vide
  • soit l'ensemble d'un noeud et de ses deux sous-arbres binaires qu'on peut positionner clairement à gauche et à droite.
    • Le noeud possède un fils gauche qu'on peut identifier comme tel (potentiellement un arbre vide donc)
    • Le noeud possède fils droit qu'on peut identifier comme tel (potentiellement un arbre vide donc)

    La notion de distinction entre fils gauche et fils droit est fondamentale ici par rapport à l'arbre (arborescence) de la partie précédente.

    2e partie de la définition du type abstrait de données ARBRE BINAIRE : son interface

    Description de l'interface minimale du type abstrait Arbre

    Je le décris ici sous forme d'un type immutable, mais on pourait faire la même chose en non-mutable.

    1. nvNd(x:Elt) -> Noeud : on crée un nouveau noeud et son élément attaché. Ce n'est pas une fonction d'interface de l'arbre mais on a besoin au moins de pouvoir créer un Noeud (les noeuds sont en même un type abstrait en réalité...)
    2. contenu(noeud:Noeud) -> Elt : renvoie l'élément (la valeur) contenue dans le noeud.
    3. nvAV() -> Arbre : on le note ainsi pour dire nvABVide : on crée un nouvel ARBRE BINAIRE vide.
    4. nvAB(noeud:Noeud, g:Arbre, d:Arbre) -> Arbre : on crée un nouvel ARBRE BINAIRE dont la racine est noeud et dont les sous-arbres sont g et d fournis.
    5. racine(arbre:Arbre) -> Noeud : renvoie le noeud jouant le rôle de la racine pour cet arbre.
    6. gauche(arbre:Arbre) -> Arbre : 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.
    7. droite(arbre:Arbre) -> Arbre : renvoie le sous-arbre droit de arbre.

    2 - Parcours Préfixe R G D

    Voici comment on réalise un parcours préfixe de façon récursive dans un Arbre Binaire. Préfixe veut dire qu'on explore d'abord le Noeud actuel avant d'aller voir à gauche et à droite.

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

    Préfixe car on commence par visiter le noeud actuel avant de faire autre chose.

    On affiche donc le noeud racine lui-même avant ses descendants.

    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)

    Description de l'algorithme récursif parcourir(arbre: Arbre)

      visiter(racine(arbre))

      SI NON estVide(gauche(arbre))

        parcourir(gauche(arbre))

      Fin SI

      SI NON estVide(droite(arbre))

        parcourir(droite(arbre))

      Fin SI

      Renvoyer VIDE

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

    Arbre question 1

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

    Arbre question 2

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

    Arbre question 3

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

    .

    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.

    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 car on finit par la visite du noeud actuel.

    On affiche donc tous les descendants des sous-arbres avant d'afficher le noeud racine lui-même.

    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)

    Description de l'algorithme récursif parcourir(arbre: Arbre)

      SI NON estVide(gauche(arbre))

        parcourir(gauche(arbre))

      Fin SI

      SI NON estVide(droite(arbre))

        parcourir(droite(arbre))

      Fin SI

      visiter(racine(arbre))

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

    .

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

    Suffixe car on finit par la visite du noeud actuel.

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

    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)

    Description de l'algorithme récursif parcourir(arbre: Arbre)

      SI NON estVide(gauche(arbre))

        parcourir(gauche(arbre))

      Fin SI

      visiter(racine(arbre))

      SI NON estVide(droite(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 - 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 : 03 12 2020
    Auteur : ows. h.