#include <stdio.h>
#include <stdlib.h>
#include "ABR.h"
#include "File.h"

void afficher_(ABR* a, int h)
{
     int n;
     if (a == NULL)
     {
        for (n=0; n<h; n++) printf("   ");
        printf("VIDE\n");
     }
     else
     {
        afficher_ (a->filsD, h+1);
        for (n=0; n<h; n++) printf("   ");
        printf("%d\n",a->racine);
        afficher_ (a->filsG, h+1);
     }
        
}

void afficher(ABR* a)
{
     afficher_(a, 0);
}

ABR* inserer (int n, ABR* a) {
       if (a == NULL)
       {
               a = (ABR*)malloc(sizeof(ABR));
               a->racine = n;
               a->filsG = NULL;
               a->filsD = NULL;
               return a;
       }
       else if (a->racine<n) a->filsD = inserer (n, a->filsD);
       else if (a->racine>n) a->filsG = inserer (n, a->filsG);
       return a;
}

ABR* rechercher (int n, ABR* a) {
       if (a == NULL) return NULL;
       else if (a->racine<n) return rechercher (n, a->filsD);
       else if (a->racine>n) return rechercher (n, a->filsG);
       return a;
}

int max(ABR* a) {
    if (a == NULL) return 0;
    if (a->filsD == NULL) return a->racine;
    return max(a->filsD);
}

int min(ABR* a) {
    if (a == NULL) return 0;
    if (a->filsG == NULL) return a->racine;
    return min(a->filsG);
}

ABR* supprMax(ABR* a) {
    if (a == NULL) return a;
    else if (a->filsD == NULL)
    {
           ABR* fG = a->filsG;
           free(a);
           return fG;
    }
    else
    {
           a->filsD = supprMax(a->filsD);
           return a;
    }
}

ABR* supprimer(int n, ABR* a)
{
     if (a==NULL) return a;
     else if (n > a->racine) 
     {
          a->filsD = supprimer(n,a->filsD);
          return a;
     }
     else if (n < a->racine)
     {
          a->filsG = supprimer(n,a->filsG);
          return a;
     }
     else if (a->filsG==NULL) 
     {
          ABR* fD = a->filsD;
          free(a);
          return fD;
     }
     else if (a->filsD==NULL)
     {
          ABR* fG = a->filsG;
          free(a);
          return fG;
     }
     else { // les deux fils existent:
          a->racine = max(a->filsG);
          a->filsG = supprMax(a->filsG);
          return a;
     }
}

int estABR(ABR* a)
{
    if (a == NULL) return 1;
    int b = 1;
    if (a->filsG!=NULL) b &= estABR(a->filsG) && max(a->filsG)<a->racine;
    if (a->filsD!=NULL) b &= estABR(a->filsD) && min(a->filsD)>a->racine;
    return  b;
}

void parcoursProfRec(ABR* a)
{
     if (a!=NULL)
     {
             parcoursProfRec(a->filsG);  
             printf("%d ",a->racine);               
             parcoursProfRec(a->filsD);
     }
}    

void parcoursLargeur(ABR* a)
{
     if (a == NULL) return;
     File* f = NULL;
     f = enfiler(f, a);
     while (f!=NULL)
     {
           ABR* b = (ABR*)teteFile(f);
           f = defiler(f);
           printf("%d ",b->racine);    
           if (b->filsG !=NULL) f = enfiler(f, b->filsG);
           if (b->filsD !=NULL) f = enfiler(f, b->filsD);
     }
}