#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "abr.h"

bool recherche_abr_iter (int x, struct abr* A0)
{   struct abr* A; // curseur pour se déplacer dans A0
    bool trouve;

    A = A0;
    trouve = false;
    while (A != NIL && !trouve)
    {
        if (A->valeur == x)
            trouve = true;
        else if (A->valeur < x)
            A = A->droit;
        else
            A = A->gauche;
    }
    return trouve;
}

bool recherche_abr_rec (int x, struct abr* A)
{
    if (A == NIL)
        return false;
    else if (A->valeur == x)
        return true;
    else if (A->valeur < x)
        return recherche_abr_rec (x, A->droit);
    else
        return recherche_abr_rec (x, A->gauche);
}

static struct abr* new_feuille (int x)
{   struct abr* F;

    F = (struct abr*)malloc (sizeof (struct abr));
    F->gauche = NIL;
    F->valeur = x;
    F->droit = NIL;
    return F;
}

struct abr* ajout_abr_iter (int x, struct abr* A0)
{
    if (A0 == NIL)
        return new_feuille (x);
    else
    {   struct abr* prec = NIL;
        struct abr* cour = A0;
        while (cour != NIL)
        {   prec = cour;
            if (cour->valeur < x)
                cour = cour->droit;
            else
                cour = cour->gauche;
        }
        if (prec->valeur < x)
            prec->droit = new_feuille (x);
        else
            prec->gauche = new_feuille (x);
        return A0;
    }
}

struct abr* ajout_abr_rec (int x, struct abr* A)
{
    if (A == NIL)
        return new_feuille (x);
    else if (x < A->valeur)
        A->gauche = ajout_abr_rec (x, A->gauche);
    else
        A->droit = ajout_abr_rec (x, A->droit);
    return A;
}

void clear_abr (struct abr* A)
{
    if (A != NIL)
    {   clear_abr (A->gauche);
        clear_abr (A->droit);
        free (A);
    }
}

void imprime_abr (struct abr* A)
{
    if (A != NIL)
    {   imprime_abr (A->gauche);
        printf ("%d\n", A->valeur);
        imprime_abr (A->droit);
    }
}