Corrigé 39  Enoncé

1. Parcours non récursif avec pile d’un arbre de recherche binaire

Parcours préordre avec pile

Soit A un arbre de recherche binaire et Pil une pile d'arbre de recherche binaire.

    CREERPILE ( Pil )
    P := A
    Possible := VRAI
    TANTQUE Possible :
        TANTQUE P <> NIL :
            ECRIRE ( INFO ( P ) )
            EMPILER ( Pil , P )
            P := FG ( P )
        FTANTQUE
        SI NON PILEVIDE ( Pil ) :
            DEPILER ( Pil , P )
            P := FD ( P )
        SINON
            Possible := FAUX
        FSI
    FTANTQUE

2. Transformation d'un arbre en son image miroir ( version récursive)

Soit R un arbre de recherche binaire

    SI R <> NIL
        T := FG ( R )
        AFF_FG ( R , FD ( R ) )
        AFF_FD ( R , T )
        Miroir_recursif ( FG ( R ) )
        Miroir_recursif ( FD ( R ) )
    FSI

3. Transformation d'un arbre en son image miroir ( version non récursive avec une pile préordre )

Soit A un arbre de recherche binaire et Pil une pile d'arbres de recherche binaire.

    CREERPILE ( Pil )
    P := A
    Possible := VRAI
    TANTQUE Possible :
        TANTQUE P <> NIL :
            ECRIRE ( INFO ( P ) )
            T := FG ( P )
            AFF_FG ( P , FD ( P ) ) ; AFF_FD ( P , T )
            EMPILER ( Pil , P )
            P := FG ( P )
        FTANTQUE
        SI NON PILEVIDE ( Pil ) :
            DEPILER ( Pil , P ) ; P := FD ( P )
        SINON
            Possible := FAUX
        FSI
    FTANTQUE

Profondeur avec pile Préordre

Soit A un arbre de recherche binaire et Pil une pile d'arbres de recherche binaire. X étant le résultat, c'est à dire la profondeur de A.

    D := - 1 ; X := - 1
    CREERPILE ( Pil )
    P := A
    Possible := VRAI
    TANTQUE Possible :
        TANTQUE P <> NIL :
            D := D + 1
            SI D > X :
                X := D
            FSI
            ECRIRE ( INFO ( P ) )
            EMPILER ( Pil , P )
            Q := P
            P := FG ( P )
        FTANTQUE
        SI NON PILEVIDE ( Pil ) :
            DEPILER ( Pil , P )
            SI Q <> P
                SI Q = FG ( P )
                    D := D - 1
                SINON
                    R := FG ( P ) ; D := D - 1
                    TANTQUE FD ( R ) <> NIL :
                        R := FD ( R )
                        D := D - 1
                    FTANTQUE
                FSI
            FSI
            Q := P ; P := FD ( P )
        SINON
            Possible := FAUX
        FSI
    FTANTQUE

Puzzle : Inordre non récursif sans pile avec 'PERE' donnant tous les éléments dans l'intervalle [v1, v2]

Soit A un arbre de recherche binaire.

    /* Recherche de v1 */
    P := A
    Trouv := FAUX
    TANTQUE ( P <> NIL ) ET NON Trouv :
        Q := P
        SI V1 = INFO ( P )
            Trouv := VRAI
        SINON
            SI INFO ( P ) > V1
                P := FG ( P )
            SINON
                P := FD ( P )
            FSI
        FSI
    FTANTQUE
    SI Trouv
        ECRIRE ( V1 )
    SINON
        1. SI INFO ( Q ) > V1
                ECRIRE ( INFO ( Q ) )
            FSI     
        2. P := Q
    FSI
    Continue := VRAI
    TANTQUE Continue ET ( P <> NIL )
        SI FD ( P ) <> NIL
            3. P := FD ( P )
            TANTQUE P <> NIL
                Q := P
                P := FG ( P )
            FTANTQUE
            SI INFO ( Q ) <= V2
                ECRIRE ( INFO ( Q ) )
            FSI
            4. P := Q
        SINON
            Remonter := VRAI
            TANTQUE Remonter ET Continue
                Q := PERE ( P )
                SI Q = NIL
                    5. Continue := FAUX
                SINON
                    6. SI FG ( Q ) = P
                            Remonter := FAUX
                        SINON
                            P := Q
                        FSI
                FSI
            FTANTQUE
            SI Continue :
                SI INFO ( Q ) <= V2
                    ECRIRE ( INFO ( Q ) )
                    7. P := Q
                SINON
                    Continue := FAUX
                FSI
            FSI   
        FSI   
    FTANTQUE