#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;

int main(void) {

  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))
                                 )
                        );


}

noeud* suppression_imp(int cle, noeud* abr) {
  noeud* z = recherche_imp(cle, abr);
  if (z == NULL) { /* ??? */ }
  // Noeud a supprimer effectivement appelé y
  noeud* y = /* ??? */;
  /* Ici y doit être le noeud à supprimer effectivement */
  /* Si ce n'est pas z, la clé de z doit devenir celle de y */

  // Il faudra supprimer y qui n'a qu'un fils que l'on appelle x
  noeud* x = /* ??? */;
  /* Ici x doit être l'unique fils de y */
  // Détachons maintenant y
  if (y->parent == NULL) {
    // Cas particulier : y était la racine de l'arbre
    abr = x;
    x->parent = NULL;
  } else if (/* ??? */) {
    // y est un fils gauche
    /* ??? */
  } else {
    // y est un fils droit
    /* ??? */
  }
  // Ne pas oublier de libérer y
  /* ??? */
  return abr;
}