Corrigé 19.  Enoncé

1. Etude du parcours " préordre "

Algorithme récursif de parcours "préordre" d'un arbre de recherche binaire avec l'utilisation d'une pile

    Créerpile(Pile)
    N := Racine
    Possible := VRAI
    TANTQUE Possible :
        TANTQUE N # NIL :
            ECRIRE ( Info(P) )
            SI Fd(N) # NIL : Empiler(Pile, Fd(N) ) FSI
            N := Fg(N)
        FINTANTQUE
        Dépiler(Pile, N, Possible)
        { Possible prend la valeur FAUX si le dépilement est impossible }
    FINTANTQUE

Algorithme itératif et sans pile de parcours "préordre" dans un arbre binaire enfilé

Un arbre binaire enfilé est défini de telle sorte qu'un noeud au lieu de contenir un pointeur NIL dans son champ droit, il contient un pointeur vers son successeur inordre. On dit qu'il est enfilé à droite.

    P := Racine { Racine de l'arbre }
    Possible := VRAI
    TANTQUE Possible :
        Q := NIL
        TANTQUE P # NIL :
            Ecrire ( Info(P) )
            Q := P
            P := Fg(P)
        FINTANTQUE
        SI Q # NIL :
            P := Fd(Q)
            TANTQUE Enfile(Q) ET P # NIL :
                Q := P
                P := Fd(Q)
            FINTANTQUE
        FSI
        Possible := ( P # NIL )
    FINTANTQUE

Algorithme itératif sans pile de parcours "préordre" dans un arbre binaire. On utilisera en plus l'opération Père

    P := Racine { Racine de l'arbre }
    Possible := VRAI
    TANTQUE Possible :
        Q := NIL
        TANTQUE P # NIL :
            Ecrire ( Info(P) )
            Q := P
            P := Fg(P)
        FINTANTQUE
        SI Q # NIL :
            P := Fd(Q)
            TANTQUE P = NIL ET Q # NIL :
                { Le Noeud Q n'a pas de fils droit, remonter alors jusqu'à ce qu'à ce qu'un fils gauche ou   la racine est                     rencontrée}
                Existq := VRAI
                TANTQUE P = Fd(Q) ET Existq :
                    P := Q
                    SI P # Racine : Q := Père(P)
                    SINON Existq := FAUX FSI
                FINTANTQUE
                SI Existq : P := Fd(Q)
                SINON P, Q := NIL FSI
            FINTANTQUE
        FSI
        Possible := ( P # NIL )
    FINTANTQUE