C'est le problème en effet, sans lien vers le parent dans la feuille c'est difficile.
Regarde ma version, j'applique une autre technique 
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
struct node *lChild;
struct node *rChild;
int value;
int size;
int height;
};
struct tree {
struct node *root;
};
struct node* constructNewNode(int i) {
/* cree une nouvelle instance de node */
struct node* n = (struct node *)malloc(sizeof(struct node));
n->value = i;
n->lChild = n->rChild = NULL;
return n;
}
struct node* nodeInsert(int i, struct node* n) {
if (i < n->value)
/* si la feuille gauche est non nulle, on insere dessus, sinon on la cree */
return ( n->lChild != NULL ? nodeInsert(i, n->lChild) : (n->lChild = constructNewNode(i)) );
else
/* si la feuille droite est non nulle, on insere dessus, sinon on la cree */
return ( n->rChild != NULL ? nodeInsert(i, n->rChild) : (n->rChild = constructNewNode(i)) );
}
int nodeCalcSize(struct node* n) {
int s = 0;
if (n != NULL) {
if (n->lChild != NULL) s += (1+nodeCalcSize(n->lChild));
if (n->rChild != NULL) s += (1+nodeCalcSize(n->rChild));
n->size = s;
}
return s;
}
int nodeCalcHeight(struct node* n) {
int h = 0;
if (n != NULL) {
int hl;
int hr;
if (n->lChild != NULL) hl = 1+nodeCalcHeight(n->lChild);
if (n->rChild != NULL) hr = 1+nodeCalcHeight(n->rChild);
h = max(hl, hr);
n->height = h;
}
return h;
}
struct node* nodeFindKey(int i, struct node* n)
{
if (n != NULL) {
if (i == n->value)
return n;
else if (i < n->value)
return nodeFindKey(i, n->lChild);
else
return nodeFindKey(i, n->rChild);
}
else
return NULL;
}
void nodeDeleteKey(struct node* n) {
if (n != NULL) {
nodeDeleteKey(n->lChild);
nodeDeleteKey(n->rChild);
free(n);
}
}
struct tree* constructNewTree() {
struct tree *T = malloc(sizeof(struct tree));
T->root = NULL;
return T;
}
void insertKey(int i, struct tree* T) {
if (T->root == NULL)
T->root = constructNewNode(i);
else
nodeInsert(i, T->root);
nodeCalcSize(T->root);
nodeCalcHeight(T->root);
}
bool findKey(int i, struct tree *T) {
return ( nodeFindKey(i, T->root) != NULL );
}
void deleteKey(int i, struct tree *T) {
struct node* temp;
struct node* prev;
temp = prev = T->root;
while (temp != NULL) {
if (temp->value == i) {
/* on a trouve la key a effacer */
bool isLeft = (prev->lChild == temp);
/* cas ou une seule feuille vide */
if (temp->lChild == NULL) {
if (isLeft)
prev->lChild = temp->rChild;
else
prev->rChild = temp->rChild;
}
else if (temp->rChild == NULL) {
if (isLeft)
prev->lChild = temp->lChild;
else
prev->rChild = temp->lChild;
}
else {
/* le cas ou les 2 feuilles ne sont pas vides */
while (temp->lChild != NULL && temp->rChild != NULL) {
temp->value = temp->rChild->value;
prev = temp;
temp = temp->rChild;
}
if (temp->rChild == NULL) prev->rChild = temp->lChild;
if (temp->lChild == NULL) prev->rChild = temp->rChild;
}
free(temp);
return;
}
prev = temp;
if (temp->value < i)
temp = temp->rChild;
else
temp = temp->lChild;
}
nodeCalcSize(T->root);
nodeCalcHeight(T->root);
}
struct node* deleteKeyRecur(int i, struct node* r) {
if (r != NULL) {
if (i > r->value) {
r->rChild = deleteKeyRecur(i, r->rChild);
}
else if (i < r->value) {
r->lChild = deleteKeyRecur(i, r->lChild);
}
else {
/* on a la cle cherchee */
if (r->lChild == NULL && r->rChild == NULL) {
r = NULL;
}
else if (r->lChild != NULL && r->rChild == NULL) {
r = r->lChild;
}
else if (r->rChild != NULL && r->lChild == NULL) {
r = r->rChild;
}
else {
/* deux feuilles */
if (r->rChild->lChild == NULL) {
r->rChild->lChild = r->lChild;
r = r->rChild;
}
else {
struct node* q;
struct node* p = r->rChild;
while (p->lChild->lChild != NULL)
p = p->lChild;
q = p->lChild;
p->lChild = q->rChild;
q->lChild = r->lChild;
q->rChild = r->rChild;
r = q;
}
}
}
}
return r;
}
void nodeInOrder(struct node* n) {
if (n != NULL) {
nodeInOrder(n->lChild);
printf("V:%d, S:%d, H:%d \n", n->value, n->size, n->height);
nodeInOrder(n->rChild);
}
}
void inOrder(struct tree *T) {
nodeInOrder(T->root);
printf("\n");
}
void deleteTree(struct tree *T) {
nodeDeleteKey(T->root);
free(T);
T = NULL;
}
struct valeur {
unsigned long L;
}
unsigned long factValeur(struct valeur* L) {
}
unsigned long factorielle(unsigned long i) {
return ( i == 1 ? i : i * factorielle(i-1) );
}
int main() {
struct tree* T;
printf("Debut\n");
printf("Fact(8) = %li \n", factorielle(8));
T = constructNewTree();
/*
insertKey(5, T);
insertKey(2, T);
insertKey(9, T);
insertKey(1, T);
*/
insertKey(10, T);
insertKey(7, T);
insertKey(8, T);
insertKey(9, T);
insertKey(5, T);
insertKey(4, T);
insertKey(6, T);
insertKey(14, T);
insertKey(11, T);
insertKey(18, T);
inOrder(T);
T->root = deleteKeyRecur(6, T->root);
inOrder(T);
deleteTree(T);
printf("Fin \n\n");
return 0;
}
