Fonctions sur les arbres

Parcours d'arbres

Parcours préfixe

FCT PROFONDEUR_PREFIXE(A : arbre binaire strict) :
    SI A est une feuille ALORS :
        TRAITER(A)
    SINON A est un noeud interne de la forme N(e,g,d) :
        TRAITER(e)
        PROFONDEUR_PREFIXE(g)
        PROFONDEUR_PREFIXE(d)
    FIN SI
FIN FCT

Parcours infixe

FCT PROFONDEUR_INFIXE(A : arbre binaire strict) :
    SI A est une feuille ALORS :
        TRAITER(A)
    SINON A est un noeud interne de la forme N(e,g,d) :
        PROFONDEUR_INFIXE(g)
        TRAITER(e)
        PROFONDEUR_INFIXE(d)
    FIN SI
FIN FCT

Parcours postfixe

FCT PROFONDEUR_POSTFIXE(A : arbre binaire strict) :
    SI A est une feuille ALORS :
        TRAITER(A)
    SINON A est un noeud interne de la forme N(e,g,d) :
        PROFONDEUR_POSTFIXE(g)
        PROFONDEUR_POSTFIXE(d)
        TRAITER(e)
    FIN SI
FIN FCT

Parcours largeur

FCT PARCOURS_LARGEUR(A : arbre binaire strict) :
    a_traiter <- file vide
    a_traiter <- enfiler A
    TANT QUE a_traiter non vide FAIRE :
    a <- defiler(a_traiter)
    SI a est une feuille ALORS :
        TRAITER(a)
    SINON a est un noeud interne de la forme N(e,g,d) :
        TRAITER(e)
        a_traiter <- enfiler(g)
        a_traiter <- enfiler(d)
    FIN Si
FIN FCT

Binarisation

FCT AUX(foret : liste d'arbres frères) :
    SI foret est vide ALORS :
        RENVOYER ⊥
    SINON foret est de la forme N(e,fils) :
        RENVOYER(e, AUX(fils), AUX(queue de foret))
    FIN SI
FIN FCT

FCT BINARISE(A : arbre d'arité quelconque non vide) :
    RENVOYER AUX([A])
FIN FCT

Rappel : Un arbre d'arité quelconque est stocké sous la forme N(e,[a₁,...,a_n]) où e est l'étiquette et a_n,...,a_n sont des arbres d'arité quelconque placés dans une liste

Débinarisation

FCT AUX(A) :
    SI A est vide ALORS :
        RENVOYER ⊥
    SINON A est de la forme N(e,g,d) :
        lc <- AUX(g)
        rs <- AUX(d)
        RENVOYER N(e,lc)::rs
    FIN SI
FIN FCT

FCT DEBINARISE(A : arbre binaire correspondant à une représentation LCRS) :
    RENVOYER tete de AUX(A)
FIN FCT