Corrigé 41.  Enoncé

1. Suivant dans un arbre de recherche m-aire.

SuivantPreordre(n, i) : prochaine valeur préordre de la i-ème valeur contenue dans le noeud n.

    SI Fils(i, n) <> Nil
        Suivantpreordre := info( 1, Fils(i, n) )
    SINON
        SI i <= Degre(n) - 2 { Il existe une valeur à droite }
            SuivantPreordre := Info( i+1, n)
        SINON
            SI Fils(i+1, n) <> Nil
                Suivantpreordre := info( 1, Fils(i+1, n) )
            SINON
            { C'est le dernier élément du noeud et a Nil à sa droite}
                Q := Pere(n) Arret := FAUX
                TANTQUE Q <> Nil et NON arret
                    Retrouver i tel que Fils(i, Q) = n
                    SI i <= Degre(Q) - 2
                    Suivantpreordre:=info(i+1, Q)
                    Arret := VRAI
                    SINON
                        SI Fils(i+1, Q) <> Nil
                        Suivantpreordre := info(i+1, Q)
                            Arret := VRAI
                        SINON
                            n := Q ;     Q := Pere(Q)
                        FSI
                    FSI
                FTANTQUE
                SI Q = Nil
                    " Pas de suivant préordre "
                FSI
            FSI
        FSI
    FSI

SuivantInordre(n, i) : prochaine valeur Inordre de la i-ème valeur contenue dans le noeud n.

    SI Fils(i+1, n) <> Nil
        Q := Fils(i+1, n)
        TANTQUE Fils(1, Q) <> Nil
            Q := Fils(1, Q)
        FTANTQUE
        SuivantInordre := Info(1, Q)
    SINON
        SI i <= Degre(n) - 2
            SuivantInordre := Info( i+1, n)
        SINON
            Q := Pere(n) Arret := FAUX
            TANTQUE Q <> Nil et NON arret
                Retrouver i tel que Fils(i, Q) = n
                SI i <= Degre(Q) - 2
                    SuivantInordre:= info(i, Q)
                    Arret := VRAI
                SINON
                    n := Q
                    Q := Pere(Q)
                FSI
            FTANTQUE
            SI Q = Nil
                " Pas de suivant Inordre "
            FSI
        FSI
    FSI

SuivantPostordre(n, i) : prochaine valeur postordre de la i-ème valeur contenue dans le noeud n.

    SI i+2 <= Degre(n)
        SI Fils(i+2, n) <> Nil
            Q := Fils(i+2, n)
            TANTQUE Fils(1, Q) <> Nil OU Fils(2, Q) <> Nil
                SI Fils(1, Q) <> Nil
                    Q := Fils(1, Q)
                SINON
                    Q := Fils(2, Q)
                FSI
            FTANTQUE
            SuivantPostordre := Info(1, Q)
        SINON
            SuivantPostordre:= Info(i+1, n)
        FSI
    SINON
        Q := Pere(n)
        SI Q = Nil
            " Pas de suivant postordre "
        SINON
            Retrouver i tel que Fils(i, Q) = n
            SI i <> 1 { ou i > 1 }
                SuivantPostordre := Info(i-1, Q)
            SINON
                Q := Fils(2, Q)
                TQ Fils(1, Q) <> Nil OU Fils(2, Q) <>Nil
                    SI Fils(1, Q) <> Nil
                        Q := Fils(1, Q)
                    SINON
                        Q := Fils(2, Q)
                    FSI
                FTANTQUE
                SuivantPostordre := Info(1, Q)
            FSI
        FSI
    FSI