Corrigé 22.  Enoncé

1. Parcours d'un arbre de recherche binaire - Transformation récursif --> itératif

Algorithme non récursif de recherche d'un élément E

    P := Arbre
    Trouv := FAUX
    TANTQUE P # NIL ET NON Trouv :
        SI Info(P) = Val :
            Trouv := VRAI
        SINON
            SI Info(P) > E :
                P := Fg(P)
            SINON
                P := Fd(P)
            FSI
        FSI
    FINTANTQUE

Algorithme non récursif de parcours inordre avec une pile

    Créerpile(Pile)
    Possible := VRAI
    TANTQUE Possible :
        TANTQUE P # NIL :
            Empiler (Pile, P) ;     P := Fg(P)
        FINTANTQUE
        SI NON Pilevide(Pile) :
            Dépiler(Pile, P)
            " Info(P) " ;      P := Fd(P)
        SINON
            Possible := FAUX
        FSI
    FINTANTQUE

Algorithme récursif de parcours "postordre"

    Post(N) :
    SI N # NIL :
        Post(Fg(N)) ; Post(Fd(N))
        " Info(N)"
    FSI

Traduction automatique de l'algorithme récursif de parcours "postordre"

Soit Zdd une variable composée de deux champs : le paramètre N et l'adresse de retour Adr.

             Créerpile(Pile)
            Zdd.N := N
            Zdd.Adr := 1
            Empiler(Pile, Zdd)
10:       SI Zdd.N # NIL :
            Empiler(Pile, Zdd)
            Zdd.N := Fg(Zdd.N)
            Zdd.Adr := 2
            Allera 10
   
2:         { Retour du premier appel }
            Empiler(Pile, Zdd)
            Zdd.N := Fd(Zdd.N)
            Zdd.Adr := 3
            Allera 10
3:         Ecrire(  Info(P)  )
            I := Zdd.Adr
            Dépiler(Pile, Zdd)
            Allera I
    SINON
            I := Zdd.Adr
            Dépiler(Pile, Zdd)
            Allera I
    FSI


2. Implémentation d'une pile

Créerpile(Pile)             :     Pile := NIL
Pilevide(Pile)               :     Pilevide := ( Pile = NIL)
Empiler(Pile, Val)        :     Allouer (Q, Typemaillon)
                                             Aff_Val(Q, Val)
                                             Aff-Adr(Q, Pile)
                                             Pile := Q

Dépiler(Pile, Val)     :     SI NON Pilevide(Pile) :
                                            Q := Pile
                                            Valeur := Info(Pile)
                                            Pile := Suivant(Pile)
                                            Libérer(Q)
                                        SINON " Pile Vide" FSI


3. Implémentation d'une pile de files d'attente

Première implémentation
Schéma :

Description

    TYPE Typepile = POINTEUR( Typemaillon1)
    Typemaillon1 = STRUCTURE
        Info : Typefile
        Lien : POINTEUR(Typemaillon1)
    FIN
    TYPE Typefile = STRUCTURE
        Tete, Queue : POINTEUR( Typemaillon)
    FIN
    TYPE Typemaillon = STRUCTURE
        Info : Typeqq
        Lien : POINTEUR (Typemaillon)
    FIN       

Deuxième implémentation

Schéma

Description :

    TYPE Typepile = STRUCTURE
        Tab : TABLEAU[1..N] DE Typefile
        Sommet : ENTIER
    FIN
    TYPE Typefile = STRUCTURE
        Tete, Queue : POINTEUR ( Typemaillon)
    FIN
    TYPE Typemaillon = STRUCTURE
        Info : Typeqq
        Lien : POINTEUR (Typemaillon)
    FIN


4. Code de Huffman

5. Arbre de recherche m-aire

6. Arbre B