Corrigé 12. Enoncé

1. Navigation dans un arbre de recherche binaire

Module de recherche

Un élément de la pile est le couple ( Pointeur, Sens).

    Créerpile( Pile)
    Trouv := FAUX
    P := Arbre
    TANTQUE P # NIL ET NON Trouv :
        SI Info(P) = A :
            Trouv := VRAI
        SINON
            SI A < Info(P) :
                Empiler(Pile, (P, Gauche))
                P := Fg(P)
            SINON
                Empiler(Pile, (P, Droite))
                P := Fd(P)
            FSI
        FSI
    FINTANTQUE

Fonction Suivantinordre(p)

    Recherche( Arbre, A, P, Pile)
    Q := Fd(P)
    SI Q # NIL :
        Sens := Droit
        TANTQUE Q # NIL :
            Empiler( Pile, (P, Sens))
            P:= Q
            Q := Fg(P)
            Sens := Gauche
        FINTANTQUE
        Suivantinordre := P
    SINON
        Dépiler( Pile, (N, Sens), Possible)
        { Possible est Vrai si le dépilement est possible }
        SI Possible :
            SI Sens = Gauche :
                Suivantinordre := N
            SINON
                Arrêt := FAUX
                TANTQUE NON Arrêt ET Possible :
                    SI Sens = Gauche :
                        Arrêt := VRAI
                    SINON
                        Dépiler(Pile,(N, Sens), Possible)
                    FSI
                FINTANTQUE
                SI Arrêt : Suivantinordre := N
                SINON Suivantinordre := NIL FSI
            FSI
        SINON
            Suivantinordre := NIL
        FSI
    FSI

Listage des éléments compris entre A et B ( A existe dans l'arbre)

    Recherche( Arbre, A, P, Pile)
    ECRIRE(A)
    R := Suivantinordre(P)
    Continue := VRAI
    TANTQUE Continue ET R # NIL :
        SI Info(R) <= B :
            ECRIRE( Info(R)) ; R :=Suivantinordre(R)
        SINON
            Continue := FAUX
        FSI
    FINTANTQUE

Listage des feuilles de l'arbre de gauche à droite

    { Recherche de la feuille la plus à gauche et construction du chemin }
    Créerpile(Pile)
    P := Arbre
    TANTQUE P # NIL :
        Empiler( Pile, (P, Gauche))
        Q := P
        P := Fg(P)
    FINTANTQUE
    R :=Q

    { Parcours séquentiel }
    TANTQUE R # NIL :
        SI Fg(R) = NIL ET Fd(R) = NIL :
            ECRIRE ( Info(R) )
        FSI
        R := Suivantinordre(R)
    FINTANTQUE


Complexité de Suivantinordre

On peut facilement montrer que la complexité est O(log2(n)), n étant le nombre de noeuds dans l'arbre de recherche binaire.