Corrigé 36  Enoncé

Suivant dans un arbre.

Soient Q, P des pointeurs vers un arbre binaire Trouv et Continue des booléens

Suivant_Inordre ( P )

    SI FD(P) <> NIL
        P := FD(P)
        TANTQUE FG(P) <> NIL :     P := FG(P)     FTANTQUE
        Suivant_Inordre := INFO(P)
    SINON
        Q := PERE(P)
        Continue := VRAI
        TANTQUE (Q <> NIL) ET Continue
            SI P = FD(Q)
                P := Q
                Q := PERE(P)
            SINON
                Continue := FAUX
            FSI
        FTANTQUE
        Suivant_Inordre := Q)
    FSI

Suivant_Préordre(P)

    SI FG(P) <> NIL
        Suivant_Préordre := FG(P)
    SINON
        SI FD(P) <> NIL
            Suivant_Préordre := FD(P)
        SINON
            Q := PERE(P)
            Continue := VRAI
            TANTQUE (Q <> NIL) ET Continue
                SI P = FD(Q)
                     P := Q
                     Q := PERE(P)
                SINON
                     SI FD(Q) <> NIL
                         Continue := FAUX
                     SINON
                         P := Q
                         Q := PERE(P)
                     FSI
                 FSI
            FTANTQUE

            SI Q <> NIL
                Suivant_Préordre := FD(Q)
            SINON
                Suivant_Préordre := NIL
            FSI
        FSI
    FSI

Suivant_Postordre (P)

    Q := PERE(P)
    SI Q= NIL
        Suivant_Postordre := NIL
    SINON
        SI P = FG(Q)
            SI FD(Q) <> NIL
                P := FD(Q)
                TANTQUE NON FEUILLE(P)
                    SI FG(P) <> NIL :    P := FG(P)
                    SINON P := FD(P)FSI
                FTANTQUE
                Suivant_Postordre := P
            SINON
                Suivant_Postordre := Q
            FSI
        SINON
            Suivant_Postordre := Q
        FSI
    FSI


Feuille droite d'une feuille F donnée.

    P := Suivant_Préordre( F)
    Trouv : = FAUX
    TANTQUE P <> NIL ET NON Trouv
        SI FG(P) = NIL ET FD(P) = NIL
            Trouv : = VRAI
        SINON
            P := Suivant_Préordre (P)
        FSI
    FTANTQUE

La feuille droite est P.

Les parcours préordre, inordre et postordre donnent les feuilles dans le même ordre.
La démonstration utilise ce dernier algorithme et se fait sur la complexité des arbres. En effet, le résultat est le même SI on remplace Suivant_Préordre par Suivant_Postordre ou Suivant_Inordre.