Corrigé 31.  Enoncé

1. Arbres de recherche binaires enfilés

Construction d'un arbre de recherche binaire enfilé à droite à partir d'une suite de M nombres

R étant une variable globale (initialisée à NIL) qui désigne la racine de l'arbre en cours de construction.

    POUR I:=1, M :
        Lire(V)
        P := R
        Q, Sauv := NIL
        Trouv, Arret := FAUX;
        TANTQUE P # NIL ET NON Trouv ET NON Arret:
            SI Info(P) = V :
                Trouv := VRAI
            SINON
                Q := P
                SI V < Info(P)
                    Sauv := P ; P := Fg(P)
                SINON
                    SI Enfilé(P) : Arret := VRAI
                    SINON P := Fd(P) FSI
                FSI
            FSI   
        FINTANTQUE

        SI NON Trouv :
            N := Créernoeud(V)
            SI Q = NIL { Première création)
                Aff_Enfilé(N, VRAI)
                R := N
            SINON    
                SI V < Info(Q)
                    Aff_Fg(Q, N)
                    Aff_Enfilé(N, VRAI)
                    Aff_Fd(N, Q)
                SINON
                    Aff_Enfilé(Q, FAUX)
                    Aff_Fd(Q, N)
                    Aff_Enfilé(N, VRAI)
                    Aff_Fd(N, Sauv)
                FSI
            FSI
        FSI
   
    FINPOUR


Module Suivant(S) qui détermine le suivant inordre d'un noeud d'adresse S

    SI Enfilé(S)
        Suivant := Fd(S)
    SINON
        P := Fd(S)
        TANTQUE Fg(P) # NIL :
            P := Fg(P)
        FINTANTQUE
        Suivant := P
    FSI


Module Pluspetitx qui recherche du plus petit X tel que X >= V

    P, Q := R { R désigne la racine de l'arbre }
    Trouv, Arret := FAUX
    TANTQUE P # NIL ET NON Trouv ET NON Arret :
        SI Info(P) = V :
            Trouv := VRAI
        SINON
            SI V < Info(P)
                Q := P; P := Fg(P)

            SINON
                SI Enfilé(P) : Arret := VRAI FSI
                P := Fd(P)
            FSI
        FSI
    FINTANTQUE
    SI Trouv : Pluspetit := P SINON Pluspetit := Q FSI

Module Requête(a, b) qui détermine toutes les valeurs X telles que A <= X <= B

    P := Pluspetitx(A)
    Arret := FAUX
    TANTQUE NON Arret ET P # NIL :
        SI Valeur(P) <= B :
            Ecrire( Valeur(P) )
            P := Suivant(P)
        SINON
            Arret := VRAI
        FSI
    FINTANTQUE


Suppression

Exploiter le champ fils gauche quand sa valeur est NIL. On obtient ainsi un arbre de recherche binaire enfilé à gauche. Ce champ contiendrait le pointeur vers le prochain inordre inverse(T2 N T1). La structure du noeud est alors :
- Information
- Bit d'enfilement à droite
- Bit d'enfilement à gauche
- Fils gauche
- Fils droit