#include <stdlib.h>
#include <stdio.h>

typedef struct noeud arbre;
struct noeud
{
    int data;
    arbre* gauche;
    arbre* droit;
};

arbre* creer(){
    arbre* abr;
    abr=malloc(sizeof(arbre));
    abr->gauche=NULL;
    abr->droit=NULL;
    return abr;
}
arbre* recherche(arbre *abr,int n){
    arbre* courant;
    if(!abr)
        return NULL;
    if(abr->data==n)
        return abr;
    if(abr->data<n)
        return (recherche(abr->gauche,n));
    if(abr->data>n)
        return(recherche(abr->droit,n));
}
int max(arbre* abr)
{
    if(!abr)
        return -32000;
    if(!abr->droit)
        return abr->data;
    return max(abr->droit);
}
int min(arbre* abr)
{
    if(!abr)
        return -32000;
    if(!abr->gauche)
        return abr->data;
    return min(abr->gauche);
}
int ABRTrue(arbre* abr)
{
    if(!abr)
        return 1;
    if((abr->data>=min(abr))&&(abr->data<=max(abr)))
        return ABRTrue(abr->gauche)*ABRTrue(abr->droit);
    else
        return 0;
}
arbre* ajout(arbre *abr,int n)
{

    if(!abr){
        arbre * temp=creer();
        temp->data=n;
        return temp;
    }
    else if(abr->data==n){
        printf("l'entier existe deja\n");
        return abr;
    }
    else if(abr->data<n){
        abr->droit=ajout(abr->droit,n);
    }
    else{
        abr->gauche=ajout(abr->gauche,n);
    }
    return abr;
}
arbre* conc(arbre* abr,arbre* Ag,arbre* Ad)
{
    abr->droit=Ad;
    abr->gauche=Ag;
    return abr;
}
arbre* concat(arbre* abr,arbre* Ag,arbre* Ad)
{
    if((abr->data<min(Ad))&&(abr->data>max(Ag))&&(ABRTrue(Ad))&&(ABRTrue(Ag)))
    {
        return conc(abr,Ag,Ad);
    }
    return NULL;
}
arbre* supp_racine(arbre *abr){
    if(abr){
        arbre *temp =abr;
        if((!abr->droit)&&(!abr->gauche)){
            free(abr);
            return NULL;
        }
        else if((abr->droit)&&(!abr->gauche)){
            abr=abr->droit;
            free(temp);
            return abr;
        }
        else if((!abr->droit)&&(abr->gauche)){
            abr =abr->gauche;
            free(temp);
            return abr;
        }
        else if(!abr->droit->gauche){
            temp =abr;
            abr=abr->droit;
            abr->gauche=temp->gauche;
            free (temp);
            return abr;
        }
        else{
            arbre *courant=abr->droit;
            while(courant->gauche->gauche)
                courant=courant->gauche;
            temp=courant->gauche;
            courant->gauche=courant->gauche->droit;
            temp->gauche=abr->gauche;
            temp->droit=abr->droit;
            free(abr);
            return temp;
        }
    }
}
arbre* supp_Val(arbre *abr,int n){//n existes.
    if(abr){
        if(abr->data==n)
            abr=supp_racine(abr);
        else if(n<abr->data){
            abr->gauche=supp_Val(abr->gauche,n);
        }
        else{
            abr->droit=supp_Val(abr->droit,n);
        }
        return abr;
    }
}
void affiche(arbre* abr)
{
    if(abr){
        affiche(abr->gauche);
        printf("%d\n",abr->data);
        affiche(abr->droit);
    }
}
int main(){
    arbre * abr;
    abr=ajout(abr,0);
    abr=ajout(abr,-1);
    abr=ajout(abr,2);
    abr=ajout(abr,0);
    abr=supp_Val(abr,2);
    printf("%d\n",ABRTrue(abr));
    affiche(abr);
}