Comment insérer correctement / supprimer dans un arbre de recherche binaire en C?
https://stackoverflow.com/questions/676048
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai un peu à mettre mes questions précédentes C en attente cause de celui-ci est plus important maintenant ...
Je l'ai déjà codé l'insertion et la suppression des fonctions sur mon arbre de recherche binaire, mais la fonction de suppression est incomplète. Il y a deux ou trois choses que je besoin d'aide dans ...
1) Ma bonne fonction d'insertion ou peut-il être amélioré en quelque sorte?
2) Ma fonction de suppression n'a pas la suppression d'un nœud à la fois la Childs gauche et droite. J'ai beaucoup cherché dans le passé quelques heures mais ne pouvait pas trouver une bonne façon 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 la bonne fonction de suppression ou peut-il être amélioré? Celui-ci, je sais que cela peut parce que je me répète beaucoup de code dans les ifs, mais je ne vois pas comment je peux l'améliorer, je besoin d'aide sur ce point également.
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 remarquerez probablement, mais permettez-moi de faire 2 remarques:
- Cet arbre utilise des chaînes au lieu de la représentation normale int. Voilà pourquoi j'utilise strcmp () tout le chemin, je pense que je l'utilise bien.
- Je ne suis pas en utilisant récursion, je passe plutôt le pointeur (d'un pointeur de structure dans ce cas) et travailler avec cela. Il semble en quelque sorte plus propre et à l'avenir je veux retourner une valeur de succès si un nœud a été supprimé.
Mise à jour DESSOUS: Je l'ai déjà fait ma version itérative de la fonction de suppression mais je n'aime pas certaines choses à ce sujet, peut-être qu'ils peuvent être améliorés (ou non) mais je ne vois pas comment. J'ai aussi essayé de coder le cas, il était absent, la suppression d'un nœud avec 2 Childs, mais il ne fonctionne pas comme il se doit ...
Je l'ai commenté le code tout où je pense que le code peut être amélioré et où est le problème. J'ai aussi nommé ces problèmes comme A, B (il n'y a pas plus B), C et D afin que nous puissions faire 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;
}
La solution
Lorsque vous supprimez un nœud, vous devez faire quelque chose au sujet de ses enfants.
S'il n'y a pas d'enfants - pas de problème. Vous supprimez juste le nœud.
Si un enfant à gauche, aussi aucun problème; vous supprimez le nœud et déplacer son enfant à gauche dans sa place.
Idem pour l'enfant droit; il suffit de déplacer l'enfant dans le lieu du nœud supprimé.
Le problème vient quand vous voulez supprimer un noeud qui a deux enfants gauche et à droite. Vous pouvez déplacer la gauche ou l'enfant à droite dans la place du nœud supprimé, mais que faites-vous alors faire l'autre enfant et de son sous-arbre?
La solution est ce; vous recherchez le successeur logique au nœud en cours de suppression. Par suite logique, je veux dire cela; dire que vous avez un arbre fait d'entiers et que vous supprimez le noeud avec la valeur 35, le successeur logique est le prochain plus grand nombre . Ya? si vous faisiez un en ordre de marche, ce serait l'élément que vous venez après l'élément vous supprimez.
Maintenant, il y a une règle simple pour trouver le successeur logique; vous allez un droit (vous avez toujours un droit, parce que c'est le cas où vous avez deux enfants) et puis vous aller aussi loin à gauche que vous pouvez.
Cet élément vous finissez à est le successeur logique. Il est plus grand que l'élément supprimé (vous êtes allé droit au début, rappelez-vous?), Mais il est le plus petit élément suivant le plus grand .
Maintenant, cet élément a toujours qu'un seul ou pas d'enfants - parce que vous êtes allé à gauche aussi loin que vous pouvez, souvenez-vous? de sorte que vous ne pouvez pas aller à gauche plus - parce qu'il n'y a pas de gauche - de sorte que l'élément n'a pas d'enfant ou juste un enfant droit et cela signifie qu'il tombe dans l'une des catagories faciles à unlink (pas d'enfants ou un seul enfant) . Alors dissociant ce est facile.
Maintenant vient le peu frais - considérer cela; si ce prochain élément le plus important était au même endroit dans l'arbre que l'élément que vous souhaitez supprimer, l'arbre serait toujours valide et correcte - parce que tout à la gauche de chaque élément est plus petit, tout à le droit est plus grand.
Alors qu'est-ce que vous faites est ce; vous copiez les données utilisateur dans le prochain plus grand nœud dans le noeud étant supprimé et vous supprimez qui suivant le plus grand noeud (il n'a pas d'enfant ou juste un enfant à droite, il est donc facile de dissocier et supprimer).
Et voilà!
Donc, en gros - trouver votre successeur logique, unlink lui de l'arbre et de mettre ses données utilisateur dans l'élément que vous êtes en train de supprimer l'origine (que vous ne supprimez ensuite, bien sûr, parce qu'il fait encore partie physiquement du arbre).
Autres conseils
Tout d'abord, vous avez mentionné que vous n'utilisez pas récursion, mais chaque fonction a un chemin logique qui appelle lui-même.
Sur les questions suivantes:
1) Retirez la récursivité. Cela peut vous obtenir dans beaucoup d'ennuis si votre arbre est assez grand pour faire sauter votre pile. Gcc a un soutien limité pour récursion de queue, mais je ne compte pas là-dessus.
2) En règle générale, lorsque vous supprimez un enfant avec deux noeuds, vous favorisez le noeud gauche ou à droite à la position du nœud supprimé était. (Ceci est un cas très simpliste, je suppose que votre arbre est pas équilibré)
2.b) Votre code de suppression a des problèmes. Je recommande la marche à travers avec quelques situations hypothétiques. Immédiatement évident pour moi était free'ing un pointeur et deferencing il:
free(cliPtr);
cliPtr->clientProfile = NULL;
Bien sûr, vous pouvez toujours vous soucier de style une fois que vous obtenez la chose de la décision correcte au carré loin.
Idéalement, il y a trois cas pour la suppression d'un nœud BST:
Cas 1:
X has no children: remove X
Cas n ° 2:
X has one children : Splice out X
Cas n ° 3:
X has two children : swap X with its successor and follow case #1 or #2
Donc, pour la suppression cas manquants:
Lorsque X (nœud à supprimer) a deux enfants, remplacez X par le successeur de X et suivre le cas n ° 1 ou n ° 2 cas. Vous pouvez également remplacer par son prédécesseur, pourrait être une bonne alternative.
if ( X->left && X->right)
{
NODE *Successor = FindSuccessor(X);
X->data = Successor->data;
free(Successor);
}
codes binaires sont insérer, supprimer, rechercher et arrêter de fumer. Exemples:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Binary Tree {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
LinkedList ll = new LinkedList();
ll.add("\n"+"mai 0020");
ll.add("\n"+"king 0019");
ll.add("\n"+"maan 0002");
ll.add("\n"+"dimple 0024");
ll.add("\n"+"eman 0004");
ll.add("\n"+"lara 0005");
ll.add("\n"+"cute 0008");
ll.add("\n"+"irene 0011");
ll.add("\n"+"sheena 0030");
ll.add("\n"+"aisy 0003");
System.out.println("display: " + ll);
System.out.println("\n\n");
for(int c=0; c<=10; c++) {
System.out.println("select from: 1-insert, 2-delete," +
" 3-display, 4-search, 5-quit");
String x = br.readLine();
int y = Integer.parseInt(x);
switch (y) {
case 1: //inserting
System.out.println("input name");
String n= br.readLine();
System.out.println("input a list number");
String o = br.readLine();
int z = Integer.parseInt(o);
ll.add("\n"+n+" "+z);
break;
case 2: // delete
ll.removeFirst();
break;
case 3: //Display
System.out.println("\n\n"+"List of employee: " + ll);
System.out.println("\n\n");
break;
case 4: //search
System.out.println("\n");
System.out.println("Search");
System.out.println("first element of the Linkedlist is: "
+ ll.getFirst());
System.out.println("\n\n");
System.out.println("last element of linkedlist:"
+ ll.getLast());
break;
case 5: //quit
System.out.println("\n\n\n\n\n"
+ " Thank You Very Much!!!!!!!\n\n\n");
System.exit(0);
break;
}
}
}
}
int delete_value(Tree*&root,Tree*&find,Tree*&ptr,int numb){
if(find->value==number){
//the number exist in the root,so we should find the highest value inside the right brache and replace it with the root.
Tree*ptr2=NULL;
Tree*ptr3=NULL;//pointer pointing to the parent of the last element of ptr2.
ptr2=root->right;
while(ptr2!=NULL){
ptr3=ptr2;
ptr2=ptr2->left;
}
if(ptr2->right!=NULL){
ptr3->left=ptr2->right;
}
swap(ptr2->value,root->value);
delete ptr2;
ptr2=ptr3=NULL;
}
else{
while(find->value!=numb){
if(find->value!=numb){
ptr=find;
}
if(find->value < numb){
find=find->right;
return delete_value(root,find,ptr,numb);
}
else{
find=find->left;
return delete_value(root,find,ptr,numb);
}
}//end of while
}//end of else
//the pointer find is pointing at the element we want to delete.
//the pointer ptr is pointing at the element before the one's we want to delete.
//case 1:the element to delete don't have any children
if(find->right==NULL && find->left==NULL){
if(ptr->left=find){
ptr->left=NULl;
delete find;
}
else{
ptr->right=NULL;
delete find;
}
}//end of the first case.
//case 2:the element has one child it could be to the left or to the right.
//a-child to the right.
if( find->right!=NULL && find->left==NULL ){
Tree*ptr2=find->right;
while(ptr2!=NULL){
ptr2=ptr2->left;//find the highest value in the right branche and replace it with the delete element
}
swap(find->value,ptr2->value);
delete ptr2;
ptr2=NULL;
}
//b-child to the left.
if(find->right==NULL && find->left!=NULL){
Tree*ptr2=find->left;
//check wether the find element is to the right or to the left of ptr.
if(ptr->left==find){
ptr->left=ptr2;
delete find;
}
else{
ptr->right=ptr2;
delete find;
}
}//end of the second case.
//case3: the element has to children.
if(find->right!=NULL&&find->left!=NULL){
Tree*ptr2=find->left;
while(ptr2->right!=NULL){
ptr2=ptr2->right;
}
swap(ptr2->value,find->value);
delete ptr2;
ptr2=NULL;
}//end of case 3.
}//end of the function.
