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

struct noeud {
  int cle;
  struct noeud* gauche;
  struct noeud* droit;
  struct noeud* parent;
};
typedef struct noeud noeud;

/* Exercice 1 */

// Q1
noeud* feuille(int cle) {
  noeud* f = (noeud*)malloc(sizeof(noeud));
  f->cle = cle;
  f->gauche = NULL;
  f->droit = NULL;
  f->parent = NULL;
  return f;
}

// Q2
bool est_feuille(noeud* n) {
  return (n != NULL && n->gauche == NULL && n->droit == NULL);
}

// Q3
noeud* enracine(int cle, noeud* gauche, noeud* droit) {
  assert((gauche == NULL || gauche->parent == NULL) && gauche != droit);
  assert(droit == NULL || droit->parent == NULL);
  noeud* n = (noeud*)malloc(sizeof(noeud));
  n->cle = cle;
  n->gauche = gauche;
  n->droit = droit;
  n->parent = NULL;
  if (gauche != NULL) {gauche->parent = n;}
  if (droit != NULL) {droit->parent = n;}
  return n;
}

// Q4
// Il faut que gauche et droit soient des arbres (des racines) sinon
// on va avoir du partage de mémoire ce qui va poser des problèmes
// pour la libérer. Pour la même raison il ne faut pas que les deux
// fils soient le même arbre.

// Q5
// cf. main()

/* Exercice 2 */

// Q1
noeud* parent(noeud* n) {
  if (n == NULL) {
    return NULL;
  } else {
    return n->parent;
  }
}

// Q2
noeud* grandparent(noeud* n) {
  return parent(parent(n));
}

// Q3
noeud* frere(noeud* n) {
  noeud* p = parent(n);
  if (p == NULL) {
    return NULL;
  } else if (p->gauche == n) {
    return p->droit;
  } else {
    return p->gauche;
  }
}

// Q4
noeud* oncle(noeud* n) {
  return frere(parent(n));
}

/* Exercice 3 */

// Q1
int taille_rec(noeud* n) {
  if (n == NULL) {
    return 0;
  } else {
    return 1 + taille_rec(n->gauche) + taille_rec(n->droit);
  }
}

// Q2
int profondeur_imp(noeud* n) {
  assert (n != NULL);
  int p = 0;
  while (n->parent != NULL) {
    n = n->parent;
    p++;
  }
  return p;
}

// Q3
// En dehors des appels récursifs, il ne faut appeler cette fonction
// que sur la racine d'un arbre sinon le noeud père se retrouve avec
// un *dangling pointer*
void libere_arbre_rec(noeud* n) {
  if (n != NULL) {
    libere_arbre_rec(n->gauche);
    libere_arbre_rec(n->droit);
    free(n);
  }
}

// Q4
// Il suffit de modifer l'agencement des trois instructions pour avoir
// un parcours préfixe/infixe/suffixe
void affiche_infixe_rec(noeud* n) {
  if (n != NULL) {
    affiche_infixe_rec(n->gauche);
    printf("%d\n", n->cle);
    affiche_infixe_rec(n->droit);
  }
}

/* Exercice 4 */

// Q1
// Il n'y a rien à apporter comme modifications à la structure. On a
// simplement rajouté une condition à vérifier.

// Q2
noeud* recherche_rec(int cle, noeud* abr) {
  if (abr == NULL || abr->cle == cle) {
    return abr;
  } else if (cle < abr->cle) {
    return recherche_rec(cle, abr->gauche);
  } else {
    return recherche_rec(cle, abr->droit);
  }
}

// Q3
noeud* recherche_imp(int cle, noeud* abr) {
  while (abr != NULL && abr->cle != cle) {
    if (cle < abr->cle) {
      abr = abr->gauche;
    } else {
      abr = abr->droit;
    }
  }
  return abr;
}

// Q4
// Il suffit de parcourir la branche la plus à gauche
noeud* minimum_imp(noeud* abr) {
  if (abr == NULL) {return NULL;}
  while (abr->gauche != NULL) {
    abr = abr->gauche;
  }
  return abr;
}

// Q5
// Il suffit de parcourir la branche la plus à droite
noeud* maximum_rec(noeud* abr) {
  if (abr == NULL || abr->droit == NULL) {
    return abr;
  }
  return maximum_rec(abr->droit);
}

// Q6
noeud* insertion_imp(int cle, noeud* abr) {
  noeud* pere = NULL;
  noeud* fils = abr;
  while (fils != NULL) {
    pere = fils;
    if (cle <= fils->cle) {
      fils = fils->gauche;
    } else {
      fils = fils->droit;
    }
  }
  if (pere == NULL) {
    return feuille(cle);
  } else if (cle <= pere->cle) {
      noeud* f = feuille(cle);
      pere->gauche = f;
      f->parent = pere;
  } else {
      noeud* f = feuille(cle);
      pere->droit = f;
      f->parent = pere;
  }
  return abr;
}

// Q7
noeud* insertion_rec(int cle, noeud* abr) {
  if (abr == NULL) {
    abr = feuille(cle);
  } else if (cle <= abr->cle) {
    abr->gauche = insertion_rec(cle, abr->gauche);
    abr->gauche->parent = abr;
  } else {
    abr->droit = insertion_rec(cle, abr->droit);
    abr->droit->parent = abr;
  }
  return abr;
}

// Q8
noeud* suppression_imp(int cle, noeud* abr) {
  noeud* z = recherche_imp(cle, abr);
  if (z == NULL) {return abr;}
  // Noeud a supprimer effectivement appelé y
  noeud* y = z;
  if (z->gauche != NULL && z->droit != NULL) {
    y = minimum_imp(z->droit);
    // On "remplace" alors z par y
    z->cle = y->cle;
  }
  // Il faudra supprimer y qui n'a qu'un fils que l'on appelle x
  noeud* x = y->gauche;
  if (y->droit != NULL) {
    assert(y->gauche == NULL);
    x = y->droit;
  }
  // Détachons maintenant y
  if (y->parent == NULL) {
    // Cas particulier : y était la racine de l'arbre
    abr = x;
    if (x!=NULL) {x->parent = NULL;}
  } else if (y->parent->gauche == y) {
    // y est un fils gauche
    y->parent->gauche = x;
    if (x != NULL) {x->parent = y->parent;}
  } else {
    // y est un fils droit
    assert(y->parent->droit == y);
    y->parent->droit = x;
    if (x != NULL) {x->parent = y->parent;}
  }
  // Ne pas oublier de libérer y
  free(y);
  return abr;
}

int main(void) {

  noeud* ex0 = feuille(42);

  // Q5
  noeud* ex1 = enracine(5,
                        enracine(3, feuille(2), feuille(5)),
                        enracine(7, NULL, feuille(8))
                        );

  noeud* ex2 = enracine(15,
                        enracine(5,
                                 feuille(3),
                                 enracine(12,
                                          enracine(10,
                                                   enracine(6, NULL, feuille(7)),
                                                   NULL),
                                          NULL)
                                 ),
                        enracine(16,
                                 NULL,
                                 enracine(20, feuille(18), feuille(23))
                                 )
                        );

  libere_arbre_rec(ex0);
  libere_arbre_rec(ex1);
  libere_arbre_rec(ex2);

}