Corrigé 34.  Enoncé

1. Arbres de recherche binaire en niveaux

Module de recherche récursif dans un arbre de recherche binaire

    R(A, X) :

    SI A = NIL
        R := NIL
    SINON
        SI X = Info(A) : R := A
        SINON
            SI X < Info(A) : R := R(Fg(A), X)
            SINON
                R := R(Fd(A), X)
            FSI
        FSI
    FSI

Module d'insertion récursif dans un arbre de recherche binaire

Ce module rend dans la variable A l'adresse de la racine et dans B l'adresse du noeud créé.

    Insere (X, A, B) :

    SI A = NIL
        A := Creernoeud(X) ; B := A
    SINON
        SI X < Info(A)
            B := A ; Insere(X, Fg(A), B)
        SINON
            B := A ; Insere(X, Fd(A), B )
        FSI
    FSI

Préfixe

    Préfixe(Mot, Longueur, Adresse) :

    Arret := FAUX
    I := 1
    Adresse := NIL
    S1 := S
    TANTQUE NON Arret
        R := Rech( S1, Mot(I) )
        SI R = NIL
            Arret := TRUE
        SINON
            I := I + 1    
            Adresse := R
            S1:= Arbre(R)
        FSI
    FINTANTQUE
    Longueur := I

Recherche d'un mot donné dans la structure

    Prefixe( Mot, Longueur, Adresse)
    SI Longueur = Long(Mot) : " Mot Existe "
    SINON " Mot n'existe Pas " FSI


Insertion d'un mot dans la structure

    Préfixe(Mot, Longueur, Adresse) :

    SI Longueur = Long(Mot)
        " Mot existe"
    SINON
        POUR J := Longueur + 1, Long(Mot)
            SI Adresse # NIL
                Adr := Arbre(Adresse)
            SINON
                Adr := S
            FSI
            Insere(Mot(J), Adr, B)
            SI S = NIL : S := Adr FSI
            SI Adresse # NIL :
                SI Arbre(Adresse) # Adr
                    Aff_Arbre(Adresse, Adr )
                FSI
            FSI
            Adresse := B
        FINPOUR
    FSI
       
Encombrement de la structure

Nous utiliserons l'algorithme suivant de parcours de la structure :

    Inordre(N) :

    SI N # NIL
        Inordre(Fg(N))
        Nbre := Nbre + 1 ; Inordre( Arbre(N) )
        Inordre(Fd(N))
    FSI

L' encombrement est donc donné par l'algorithme suivant :

    Nbre := 0; Inordre(N) ; Ecrire ( 7 * Nbre)