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

typedef struct noeud {
  int valeur;
  struct noeud* gauche;
  struct noeud* droit;
} noeud;

noeud* nouvel_arbre (int valeur) {
 noeud* n;
 n = (noeud*)malloc(sizeof(noeud));
 n->valeur = valeur;
 n->gauche = NULL;
 n->droit = NULL;
 return n;
}

void __affiche (noeud* arbre, int profondeur, int flag) {
	int i;
	if (flag) {
		for (i = 0; i < profondeur; i++) printf ("\t");
	}
	if (arbre == NULL) {
		printf ("-");
	} else {
		printf ("%d\t", arbre->valeur);
		__affiche (arbre->gauche, profondeur+1, 0); 
		__affiche (arbre->droit, profondeur+1, 1);
	}
	if (! flag) { puts (""); }
}
void affiche (noeud* arbre) {
	__affiche (arbre, 0, 0);
}

noeud* insere (int valeur, noeud* arbre) {
 if (arbre == NULL) {
  return nouvel_arbre(valeur);
 }
 if (valeur > arbre->valeur) {
  arbre->droit = insere (valeur, arbre->droit);
 }
 else {
  arbre->gauche = insere (valeur, arbre->gauche);
 }
 return arbre;
}

// teste si valeur est dans l'arbre
noeud* recherche (int valeur, noeud* arbre) {
 if (arbre == NULL) {
  return NULL;
 }
 if (valeur == arbre->valeur) {
  return arbre;
 }
 if (valeur > arbre->valeur) {
  return recherche (valeur, arbre->droit);
 }
 else {
  return recherche (valeur, arbre->gauche);
 }
}

noeud* supprimer (int valeur, noeud* arbre) {
 noeud *pere,*fils,*n;
 int bool_droite;
 pere = NULL;
 fils = arbre;
 while (fils->valeur != valeur) {
  pere = fils;
  if (fils->valeur < valeur) {
   fils = fils->droit;
   bool_droite = 1;
  }
  else {
   fils = fils->gauche;
   bool_droite = 0;
  }
 }
 if (fils==NULL) {
  return arbre;
 }
 if (fils->droit == NULL && fils->gauche == NULL) {
  free(fils);
  if (pere == NULL) {
   return NULL;
  }
  if (bool_droite) {
   pere->droit = NULL;
  }
  else {
   pere->gauche = NULL;
  }
  return arbre;
 }
 if (fils->droit == NULL) {
  if (pere == NULL) {
   arbre = fils->gauche;
  }
  else {
   if (bool_droite) {
    pere->droit = fils->gauche;
   }
   else {
    pere->gauche = fils->gauche;
   }
  }
  free (fils);
  return arbre;
 }
 if (fils->gauche == NULL) {
  if (pere == NULL) {
   arbre = fils->droit;
  }
  else {
   if (bool_droite) {
    pere->droit = fils->droit;
   }
   else {
    pere->gauche = fils->droit;
   }
  }
  free (fils);
  return arbre;
 }
 n=fils->droit;
 pere = fils;
 bool_droite = 1;
 while (n->gauche != NULL) {
  bool_droite = 0;
  pere = n;
  n = n->gauche;
 }
 fils->valeur = n->valeur;
 if (bool_droite) {
  pere->droit = n->droit;
 } else {
  pere->gauche = n->droit;
 }
 free(n);
 return arbre;
}

int main() {
	int v, action;
	noeud* arbre = NULL;
	
	while (1) {
		puts ("Choisissez ce que vous voulez faire :");
		puts (" 1 - InsŽrer une valeur");
		puts (" 2 - Supprimer une valeur");
		puts (" 3 - Rechercher une valeur");
		puts (" 4 - Afficher l'arbre");
		puts (" 9 - Quitter le jeu");
		scanf ("%d", &action);
		
		if (action == 9) { break; }
		
		switch (action) {
			case 1:
				printf ("Nouvelle valeur : ");
				scanf ("%d",&v);
				arbre = insere (v, arbre);
				break;
			case 2:
				printf ("Valeur ˆ supprimer : ");
				scanf ("%d",&v);
				arbre = supprime (v, arbre);
				break;
			case 3:
				printf ("Valeur ˆ rechercher : ");
				scanf ("%d",&v);
				if (recherche (v, arbre) != NULL) { 
					printf ("La valeur %d a ŽtŽ trouvŽe dans l'arbre\n", v);
				} else {
					printf ("La valeur %d n'a pas ŽtŽ trouvŽe dans l'arbre\n", v);
				}
				break;
			case 4:
				affiche (arbre);
				break;
		}
		
		puts ("\n************\n");
	}
	
	return 0;
}