Comment bien insérer/supprimer dans un arbre de recherche binaire en C?

J'ai un peu obligé de mettre mon précédent C questions sur la prise de provoquer ce que l'on est de plus en plus importants...

J'ai déjà codé de l'insérer et de supprimer des fonctions sur mon arbre de recherche binaire, mais la fonction de suppression est incomplète. Il ya un couple de choses que j'ai besoin d'aide dans...

1) Est mon insérer une fonction bien ou peut-il être amélioré en quelque sorte?

2) Ma fonction de suppression manque la suppression d'un nœud à la fois à gauche et à droite de childs. J'ai beaucoup cherché dans le passé quelques heures, mais ne pouvait pas trouver un bon moyen de le faire.

2.a) Comment dois-je supprimer un nœud avec 2 nœuds enfants?

2.b) Comme dans la première question, est-ce la fonction de suppression de bonne ou peut-il être amélioré? Celui-ci, je sais qu'il peut, parce que je répète beaucoup de code dans les fi mais je ne vois pas comment je peux l'améliorer, j'ai besoin d'aide sur ce que trop.

typedef struct sClientProfile *ClientProfile;
typedef struct sClientTree *ClientTree;
typedef struct sClientProfile {
char *clientName;
int clientAge;
int clientNIF;
} nClientProfile;
typedef struct sClientTree {
ClientProfile clientProfile;
char *clientName;
ClientTree leftTree;
ClientTree rightTree;
} nClientTree;
void addClientToTree(ClientTree *cTree, ClientProfile cProfile) {
if(!*cTree) {
ClientTree new = (ClientTree)malloc(sizeof(nClientTree));
if(!new) {
perror("malloc");
}
new->clientName = strdup(cProfile->clientName);
new->clientProfile = cProfile;
new->leftTree = NULL;
new->rightTree = NULL;
*cTree = new;
} else {
if(strcmp((*cTree)->clientName, cProfile->clientName) > 0) {
addClientToTree(&(*cTree)->leftTree, cProfile);
} else {
addClientToTree(&(*cTree)->rightTree, cProfile);
}
}
}
void deleteClientFromTree(ClientTree *cTree, char *cName) {
if(!cTree) return;
int nCompare = strcmp((*cTree)->clientName, cName);
if(nCompare > 0) {
deleteClientFromTree(&(*cTree)->leftTree, cName);
} else if(nCompare < 0) {
deleteClientFromTree(&(*cTree)->rightTree, cName);
} else {
if(!(*cTree)->leftTree && !(*cTree)->rightTree) {
ClientTree cliPtr = *cTree;
free(cliPtr->clientProfile);
free(cliPtr);
cliPtr->clientProfile = NULL;
cliPtr = NULL;
*cTree = NULL;
} else if(!(*cTree)->leftTree) {
ClientTree cliPtr = *cTree;
free(cliPtr->clientProfile);
free(cliPtr);
cliPtr->clientProfile = NULL;
*cTree = (*cTree)->rightTree;
} else if(!(*cTree)->rightTree) {
ClientTree cliPtr = *cTree;
free(cliPtr->clientProfile);
free(cliPtr);
cliPtr->clientProfile = NULL;
*cTree = (*cTree)->leftTree;
} else {
//MISSING DELETE CASE
}
}
}

Vous aurez probablement remarqué, mais permettez-moi juste de faire 2 remarques:

• Cet arbre utilise des chaînes à la place de l'int de la représentation. C'est pourquoi je utiliser strcmp() tout le chemin, je pense que je vais l'utiliser.
• Je ne suis pas en utilisant la récursivité, je préfère passer le pointeur (un pointeur de structure dans ce cas) et de travailler avec cela. Il a l'air plus propre en quelque sorte et dans l'avenir je veux retourner une valeur de succès si un nœud a été supprimé.

DE MISE À JOUR CI-DESSOUS:

J'ai déjà fait ma version itérative de la fonction supprimer mais je n'aime pas certaines choses à ce sujet, peut-être qu'ils peuvent être améliorés (ou pas) mais je ne vois pas comment. J'ai aussi essayé de code le cas, il a été absent, la suppression d'un nœud avec 2 enfants, mais il ne fonctionne pas comme il se doit...

J'ai commenté le code entier où je pense que le code peut être amélioré et où est le problème. J'ai également nommé ces problèmes, B (il n'y a pas de B plus), C et D afin que nous puissions référence à eux facilement.

bool deleteClientFromTree(ClientTree *cTree, char *cName) {
if(!cTree) return FALSE;
ClientTree currPtr = *cTree;
ClientTree prevPtr = NULL;
int nCompare;
while(currPtr) {
nCompare = strcmp(currPtr->clientName, cName);
if(nCompare > 0) {
prevPtr = currPtr;
currPtr = currPtr->leftTree;
} else if(nCompare < 0) {
prevPtr = currPtr;
currPtr = currPtr->rightTree;
} else {
/*
* A)
* 
* The following cases have 3 lines in common, the free()
* calls and return statement. Is there anyway to improve
* this code and make it more compact?
* 
* Of course, the printf's are to be removed...
*/
if(!prevPtr && !currPtr->leftTree && !currPtr->rightTree) {
printf("CASE #1\n");
*cTree = NULL;
free(currPtr->clientProfile);
free(currPtr);
return TRUE;
} else if(!currPtr->leftTree || !currPtr->rightTree) {
printf("CASE #2\n");
if(prevPtr->leftTree == currPtr) {
prevPtr->leftTree = currPtr->rightTree;
} else {
prevPtr->rightTree = currPtr->leftTree;
}
free(currPtr->clientProfile);
free(currPtr);
return TRUE;
} else {
printf("CASE #3\n");
ClientTree tempPtr = currPtr->rightTree;
while(tempPtr->leftTree) {
tempPtr = tempPtr->leftTree;
}
/*
* C)
* 
* This has a big problem...
* 
* If you take a look at the ClientProfile structure,
* in the first post, you'll see two ints
* (clientNIF/clientAge) and one char* (clientName).
* 
* The problem is that the following code line is only
* copying the integer data, not the string. For some
* reason, the string remains the old one.
* 
* I tried to use strdup() directly on clientName like:
* currPtr->clientProfile->clientName = strdup(tempPtr->clientProfile->clientName);
* but it still doesn't work.
* 
* Why everything is being copied but the strings?
*/
currPtr->clientProfile = tempPtr->clientProfile;
/*
* D)
* 
* Is there anyway to not call the function itself
* and make the while loop once again and delete the
* corresponding leaf?
*/
return deleteClientFromTree(&currPtr->rightTree, tempPtr->clientProfile->clientName);
}
}
}
return FALSE;
}

OriginalL'auteur Ricardo Amaral | 2009-03-24