#include <stdio.h>
#include <stdlib.h>
struct TNoeud
{
    int val;
    struct TNoeud *FG,*FD;
};

struct TMaillon
{
   struct TNoeud *val;
   struct TMaillon *Suivant;
};
struct TMaillon *T=NULL,*Q=NULL;

void Enfiler(struct TNoeud *N)
{
  struct TMaillon *P=(struct TMaillon *)malloc(sizeof(struct TMaillon));
  P->Suivant=NULL;
  P->val=N;
  if(T==NULL)
  {
      T=P;
      Q=P;
  }
  else
  {
    Q->Suivant=P;
    Q=P;
  }
}

void Defiler(struct TNoeud **N)
{
    struct TMaillon *P=T;
    if(T==NULL)
    {
        printf("impossible file vide");
    }
    else
    {
        *N=T->val;
        T=T->Suivant;
        if(T==NULL){Q=NULL;}
        free(P);

    }
}

int Filevide()
{
    return T==NULL;
}


void Ajouter(struct TNoeud **R,int x)
{
    struct TNoeud *N=*R,*N1;

    if(N==NULL)
    {
        N1=(struct TNoeud *)malloc(sizeof(struct TNoeud));
        N1->val=x;
        N1->FG=NULL;
        N1->FD=NULL;
        *R=N1;
    }
    else
    {
        if(N->val==x)
        {
            printf("Impossible, il exite déjà !!!!");
        }
        if(N->val>x)
        {
            if(N->FG==NULL)
            {
                N1=(struct TNoeud *)malloc(sizeof(struct TNoeud));
                N1->val=x;
                N1->FG=NULL;
                N1->FD=NULL;
                N->FG=N1;
            }
            else
            {
                Ajouter(&N->FG,x);
            }
        }
      if(N->val<x)
        {
            if(N->FD==NULL)
            {
                N1=(struct TNoeud *)malloc(sizeof(struct TNoeud));
                N1->val=x;
                N1->FG=NULL;
                N1->FD=NULL;
                N->FD=N1;
            }
            else
            {
                Ajouter(&N->FD,x);
            }
        }
    }
}

void PPPrefixe(struct TNoeud *R)
{
    if(R!=NULL)
    {
        printf("%d,",R->val);
        PPPrefixe(R->FD);
        PPPrefixe(R->FG);
    }
}

void PPPostfixe(struct TNoeud *R)
{
    if(R!=NULL)
    {

        PPPostfixe(R->FG);
        PPPostfixe(R->FD);
        printf("%d ",R->val);
    }
}

void PPInfixe(struct TNoeud *R)
{
    if(R!=NULL)
    {

        PPInfixe(R->FG);
        printf("%d ",R->val);
        PPInfixe(R->FD);

    }
}
int main()
{
    printf("====== TP arbres ========\n");
    struct TNoeud *Racine=NULL,*N;
    Ajouter(&Racine,15);
    Ajouter(&Racine,10);
    Ajouter(&Racine,5);
    Ajouter(&Racine,13);
    Ajouter(&Racine,20);
    Ajouter(&Racine,18);
    Ajouter(&Racine,22);

    printf("\n====== Parcours en profondeur préfixe ========\n");
    PPPrefixe(Racine);

    printf("\n====== Parcours en profondeur postfixe ========\n");
    PPPostfixe(Racine);
    printf("\n====== Parcours en profondeur infixe ========\n");
    PPInfixe(Racine);

    printf("\n====== Parcours en largeur ========\n");
    Enfiler(Racine);
    while (!Filevide())
    {
        Defiler(&N);
        printf("%d ",N->val);
        if(N->FG!=NULL){Enfiler(N->FG);}
        if(N->FD!=NULL){Enfiler(N->FD);}
    }

    return 0;
}