Programmes en C

typedef    int Element;
int        nTas = 0;

void Ajouter (int v)              /* - */
{
    int    i;

    ++nTas;
    i = nTas - 1;
    while (i > 0 && a [(i - 1)/2] <= v) {
        a[i] = a[(i - 1)/2]; 
        i = (i - 1)/2;
    }
    a[i] = v;
}

Element Maximum ()          /* - */
{
    return a[0];
}

void Supprimer ()          /* - */
{
    int i, j;
    Element v;

    a[0] = a[nTas - 1];
    --nTas;
    i = 0; v = a[0];
    while (2*i + 1 < nTas) {
        j = 2*i + 1;
        if (j + 1 < nTas) 
            if (a[j + 1] > a[j]) 
                ++j;
        if (v >= a[j]) 
            break;
        a[i] = a[j]; i = j;
    }
    a[i] = v;
}

void HeapSort ()                   /* - */
{
    int      i;
    Element  v;

    nTas = 0;
    for (i = 0; i < N; ++i) {
        Ajouter (a[i]);
        Impression();
    }
    for (i = N - 1; i >= 0; --i) { 
        v = Maximum();
        Supprimer();
        a[i] = v;
    }
}

typedef struct Noeud {           /* - */
    Element         contenu;
    struct Noeud    *filsG;
    struct Noeud    *filsD;
}  *Arbre;

typedef struct Noeud {           /* - */
    Element         contenu;
    struct Noeud    *fils[$n$];
} *Arbre;

typedef struct  Cellule {            /* - */
    struct Noeud         *contenu;
    struct Cellule       *suivant;
} *ListeArbre;

typedef struct Noeud {
    Element     contenu;
    ListeArbre  fils;
} *Arbre;

Arbre a5, a7;                     /* - */

Arbre NouvelArbre (Element v, Arbre a, Arbre b)
{
    Arbre     c;

    c = (Arbre) malloc (sizeof (struct Noeud));
    c -> contenu = v;
    c -> filsG = a;
    c -> filsD = b;
    return c;
}

int main()
{
    a5 = NouvelArbre (12, NouvelArbre (8, NouvelArbre (6, NULL, NULL), NULL),
                          NouvelArbre (13, NULL, NULL));
    a7 = NouvelArbre (20, NouvelArbre (3, NouvelArbre (3, NULL, NULL), a5),
                          NouvelArbre (25, NouvelArbre (21, NULL, NULL),
                                           NouvelArbre (28, NULL, NULL)));
    ...

}

void Imprimer (Arbre a, int tab)  /* - */
{
    int i;

    if (a != NULL) {
        printf ("%3d     ", a -> contenu);
        Imprimer (a -> filsD, tab + 8);
        if (a -> filsG != NULL) {
            putchar ('\n');
            for (i = 1; i <= tab; ++i)
                putchar (' ');
        }
        Imprimer (a -> filsG, tab);
    }
}

void ImprimerArbre (Arbre a)
{
    Imprimer (a, 0);
    putchar ('\n');
}

int Taille (Arbre a)   /* - */
{
    if (a == NULL)
        return 0;
    else
        return 1 + Taille (a -> filsG) + Taille (a -> filsD);
}

Arbre Recherche (Element v, Arbre a)   /* - */
{
    Arbre      r;

    r = NULL;
    if (a == NULL || v == a -> contenu)
         return a;
    else
         if (v < a -> contenu)
             return Recherche (v, a -> filsG);
         else
             return Recherche (v, a -> filsD);
}

void Ajouter (Element v, Arbre *ap)
{
    Arbre  a = *ap;
    if (a == NULL)
        a = NouvelArbre (v, NULL, NULL);
    else if (v <= a -> contenu) 
        Ajouter (v, &a -> filsG);
    else
        Ajouter (v, &a -> filsD);
    *ap = a;
}

int Ajouter (Element v, Arbre *ap)      /* - */
{
    int        incr, r;
    Arbre      a = *ap;
    void       RotD(Arbre *), RotG(Arbre *);
    

    r = 0;
    if (a == NULL) {
        a = NouvelArbre (v, NULL, NULL);
        a -> bal = 0;
        r = 1;
    } else {
        if (v <= a -> contenu)
            incr = -Ajouter (v, &a -> filsG);
        else 
            incr =  Ajouter (v, &a -> filsD);
        a -> bal = a -> bal + incr;
        if (incr != 0 && a -> bal != 0) 
            if (a -> bal < -1)
                /* La gauche est trop grande */
                if (a -> filsG -> bal < 0)
                    RotD (&a);
                else {
                    RotG (&a -> filsG); 
                    RotD (&a);
                }
            else
            if (a -> bal > 1)
                /* La droite est trop grande */
                if (a -> filsD -> bal > 0)
                    RotG (&a);
                else {
                    RotD (&a -> filsD); 
                    RotG (&a);
                }
            else
               r = 1;
    }
    *ap = a;
    return r;
}

#define Min(x, y)      ((x) <= (y)? (x) : (y))
#define Max(x, y)      ((x) >= (y)? (x) : (y))

void RotD (Arbre *ap)             /* - */
{
    Arbre     a, b;
    int       bA, bB, bAnew, bBnew;

    a = *ap;
    b = a;
    a = a -> filsG;
    bA = a -> bal; bB = b -> bal;
    b -> filsG = a -> filsD;
    a -> filsD = b;
    /* - */
    bBnew = 1 + bB - Min(0, bA);
    bAnew = 1 + bA + Max(0, bBnew);
    a -> bal = bAnew;
    b -> bal = bBnew;
    *ap = a;
}

void RotG (Arbre *ap)             /* - */
{
    Arbre     a, b;
    int       bA, bB, bAnew, bBnew;

    a = *ap;
    b = a -> filsD;
    bA = a -> bal; bB = b -> bal;
    a -> filsD = b -> filsG;
    b -> filsG = a;
    /* - */
    bAnew = bA - 1 - Max(0, bB);
    bBnew = bB - 1 + Min(0, bAnew);
    a -> bal = bAnew;
    b -> bal = bBnew;
    *ap = b;
}