Corrigé 28.  Enoncé

1. Forêt d'arbres de recherche binaire

Dans les algorithmes qui suivent :

1. La forêt est représentée par une liste linéaire chaînée. Chaque maillon pointe un arbre de recherche binaire de mots de même longueur. Si P est l'adresse d'un maillon, Info(P) désigne la racine de cet arbre et Longueur(P) désigne sa longueur.

2. La variable Forêt est globale et désigne l'adresse du premier maillon de la liste.

3. La fonction Lg désigne la longueur d'un mot en nombre de caractères.

4. Pile est une pile d'adresses de noeuds de l'arbre. elle est globale pour les modules Motc, Rech et Imprimersuivants.

5. Type_élément_liste désigne le type d'un maillon de la liste.

Module qui recherche le mot Mot dans la forêt Forêt et qui l'insère s'il ne le retrouve pas

Soient R et S des pointeurs vers des noeuds de l'arbre et P, Q et M des pointeurs vers des maillons de la liste linéaire chaînée ( Forêt ).

Insere (Forêt, Mot ) :

    { Recherche dans la liste }
    P := Forêt
    Q := NIL
    Trouv, Arret := FAUX
    TANTQUE P # NIL ET NON Trouv ET NON Arret :
        SI Longueur(P) = Lg(Mot) :
            Trouv := VRAI
        SINON
            SI Longueur(P) > Lg(Mot) :
                Arret := VRAI
            SINON
                Q := P
                P := Suivant(P)
            FSI
        FSI
    FINTANTQUE

    SI NON Trouv :
        { Rajouter l'élément dans la liste }

        Allouer(M, Type_élément_liste)
        Aff_Long(M, Lg(Mot) )
        Aff_Arbre(M, Creernoeud(Mot) )
        SI Q # NIL
            Aff_Adr(M, Suivant(Q) )
            Aff_Adr(Q, M)
        SINON
            Aff_Adr(M, Foret)
            Forêt:= M
        FSI
    SINON
        {Recherche dans l'arbre de recherche binaire}
        R := Arbre(P)
        Trouv := FAUX
        TANTQUE R # NIL ET NON Trouv :
            SI Info(R)= Mot :
                Trouv := VRAI
            SINON
                S := R
                SI Info(R) > Mot :
                    R := Fg(R)
                SINON
                    R := Fd(R)
                FSI
            FSI
        FINTANTQUE
        SI NON Trouv
            SI Mot < Info(R):
                Aff_Fg(S, Creernoeud(Mot) )
            SINON
                Aff_Fd(S, Creernoeud(Mot) )
            FSI
        SINON
            " Mot existe déjà "
        FSI
    FSI

Module (a) : Recherche dans un arbre binaire de racine A l'adresse Q du plus petit mot qui commence par un caractère C donné. Si ce mot existe, Exist prend la valeur Vrai, Faux sinon

La fonction Prem donne le premier caractère d'un mot donné.
    Rech(A, C, Exist, Q) :

    P := A
    Exist := FAUX
    TANTQUE P # NIL :
        SI Prem(Info(P)) = C :
            Exist := VRAI
            Q := P                 ( 1 )
        FSI
        SI Info(P)> C :
            P := Fg(P)
        SINON
            P := Fd(P)
        FSI
    FINTANTQUE

Afin de déterminer les suivants du plus petit mot commençant par C, on utilise une pile qui contiendra tous les mots parcourus qui commencent par C. Pour avoir ceci, on ajoute l'opération Empiler(Pile, P) après l'affectation (1) de l'algorithme (a) ci-dessus. On appellera ce nouvel algorithme (a').

Module (b) : détermine les suivants du plus petit mot qui commencent par C

    Imprimersuivants(C) :

    SI NON Pilevide(Pile) :
        Depiler(Pile, P)
        Ecrire( ' Mot suivant =', Info(P) )
        P := Fd(P)
        Possible := VRAI
        TANTQUE Possible :
            TANTQUE P # NIL :
                Empiler(Pile, P)
                P := Fg(P)
            FINTANTQUE
            SI NON Pilevide(Pile) :
                Depiler(Pile, P)
                SI Prem(Info(P)= C :
                    "Mot Suivant := ', Info(P)"
                FSI
                P := Fd(P)
            SINON
                Possible := FAUX
            FSI
        FINTANTQUE
    FSI

Recherche de tous les mots de la forêt qui commencent par un caractère C donné

    Motc(C) :

    Q := Forêt
    TANTQUE Q # NIL :
        Creerpile(Pile)
        "'Arbre de longueur',Lg(Q)"
        Rech(Arbre(Q), C, Trouv, P) { correspondant au module (a') }
        SI Trouv :
            "'Plus petit mot commençant par', C, ':', Info(P)"
            Imprimersuivants(C)
        FSI
        Q := Suivant(Q)
    FINTANTQUE