Wie man richtig einsetzen / Löschen in einem binären Suchbaum in C?
https://stackoverflow.com/questions/676048
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
ich irgendwie muss meine vorherige C Fragen zu halten Ursache setzen diese ist heute wichtiger denn je ...
Ich habe bereits den Einsatz codiert und löschen Funktionen auf meine binäre Suchbaum aber die Löschfunktion ist unvollständig. Es gibt ein paar Dinge, die ich brauche Hilfe in ...
1) Ist meine Insert-Funktion gut oder kann es irgendwie verbessert werden?
2) Meine Löschfunktion fehlt das Löschen eines Knotens mit der linken und rechten Kindes. Ich habe viel in den letzten paar Stunden gesucht, aber konnte keine richtige Art und Weise zu tun, es finden.
2.a) Wie soll ich einen Knoten mit zwei untergeordneten Knoten löschen?
2.b) Wie in der ersten Frage ist die Löschfunktion gut oder kann sie verbessert werden? Dies Ich weiß, es kann, weil ich eine Menge Code in dieser ifs zu wiederholen, aber ich sehe nicht, wie kann ich es verbessern, ich brauche Hilfe auf das auch.
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
}
}
}
Sie werden wahrscheinlich feststellen, aber lassen Sie mich zwei Bemerkungen einfach machen:
- Dieser Baum verwendet Strings anstelle der normalen int Darstellung. Deshalb habe ich strcmp () den ganzen Weg benutzen, ich glaube, ich verwende es richtig.
- Ich bin Rekursion nicht verwenden, gibt ich lieber den Zeiger (eine Struktur Zeiger in diesem Fall) und damit arbeiten. Es sieht mehr sauber irgendwie und in der Zukunft möchte ich einen Erfolg Wert zurückgeben, wenn ein Knoten gelöscht.
UPDATE unten:
Ich habe schon habe meine iterative Version der Lösch-Funktion, aber ich mag es nicht, ein paar Dinge über sie, vielleicht können sie verbessert werden (oder nicht), aber ich kann nicht sehen, wie. Ich habe auch versucht, den Fall zu codieren, es fehlte, einen Knoten mit 2 Kindern zu löschen, aber es funktioniert nicht, wie es sollte ...
Ich habe den ganzen Code kommentiert, wo ich der Code denke verbessert werden kann und wo ist das Problem. Ich habe auch solche Probleme wie A, B (es gibt keine B mehr) genannt, C und D so können wir auf sie verweisen leicht.
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;
}
Lösung
Wenn Sie einen Knoten löschen, müssen Sie etwas über seine Kinder tun.
Wenn es keine Kinder - kein Problem. Sie entfernen Sie einfach den Knoten.
Wenn es ein linkes Kind, auch kein Problem; Sie den Knoten entfernen und sein linkes Kind in seinen Platz bewegen.
Das Gleiche gilt für das rechte Kind; bewegen Sie einfach das Kind an die Stelle des gelöschten Knotens.
Das Problem kommt, wenn Sie einen Knoten löschen möchten, die links und rechts Kinder hat. Sie könnten das linke oder das rechte Kind in den Ort des gelöschten Knoten verschieben, aber was tun Sie dann über das andere Kind und den Baum?
Lösung ist dies; Sie finden die logische Nachfolger des Knotens gelöscht werden. Durch die logischen Nachfolger, dann meine ich das; sagen, Sie haben einen Baum von ganzen Zahlen gemacht und Sie Knoten mit dem Wert 35, die logischen Nachfolger löschen ist die nächste größte Zahl . Ya? wenn Sie einen in Ordnung zu Fuß tun, wäre es das Element sein, das Sie zu, nachdem das Element kommen Sie zu löschen.
Jetzt gibt es eine einfache Regel die logischen Nachfolger zu finden; Sie gehen Sie nach rechts ein (Sie immer das Recht haben, weil dies der Fall ist, wo Sie zwei Kinder haben), und dann gehen Sie so weit links wie möglich.
Das Element, das Sie am Ende ist der logische Nachfolger. Es ist größer als das gelöschte Element (Sie ging gleich zu Beginn, erinnern Sie sich?), Aber es ist die kleinste nächstgrößte Element .
Nun, immer das Element nur eine oder gar keine Kinder - weil Sie so weit nach links ging, wie Sie können, schon vergessen? so kann man nicht mehr nach links -, weil es keine links ist - so dass das Element keine Kinder hat oder nur ein Recht, Kind und das bedeutet, es fällt in einer der einfach zu unlink catagories (keine Kinder oder nur ein Kind) . So Entkoppeln das Element ist einfach.
Jetzt kommt die kühle Bit - betrachtet dies; wenn das nächste größte Element an der gleichen Stelle im Baum als Element waren Sie löschen möchten, würde der Baum noch gültig und richtig sein - weil alles auf der linken Seite jedes Elements kleiner ist, alles zu das Recht größer ist.
Also, was Sie tun, ist dies; Sie kopieren die Benutzerdaten in den nächstgrößeren Knoten in den Knoten gelöscht werden und Sie löschen , die nächstgrößere node (es hat keine Kinder oder nur ein Recht, Kind, so ist es leicht zu entkoppeln und löschen).
Und das ist es!
Also, im Grunde - logische Nachfolger finden, entkoppeln ihn vom Baum und seine Benutzerdaten setzen in das Element Sie eigentlich ursprünglich zu löschen (die Sie nicht löschen Sie dann, natürlich, weil es immer noch physisch Teil der ist Baum).
Andere Tipps
Zunächst einmal, Sie erwähnten Sie nicht mit Rekursion, aber jede Funktion einen logischen Pfad, der sich selbst aufruft.
Auf die Fragen:
1) Entfernen Sie die Rekursion. Dies können Sie in einer Menge Ärger bekommen, wenn Ihr Baum groß genug ist, um Ihr Geld zu blasen. Gcc hat begrenzte Unterstützung für Endrekursion, aber ich würde nicht auf sie zählen.
2) Normalerweise, wenn Sie ein Kind mit zwei Knoten löschen, können Sie den linken oder rechten Knoten in die Position war in der gelöschten Knoten fördern. (Dies ist eine sehr vereinfach Fall ist, ich deinen Baum gehe davon ist nicht symmetrisch)
2.b) Ihr Lösch Code hat einige Probleme. Ich würde empfehlen, mit ein paar hypothetische Situationen durch sie zu Fuß. Unmittelbar ich klar einen Zeiger wurde free'ing und dann deferencing es:
free(cliPtr);
cliPtr->clientProfile = NULL;
Natürlich können Sie immer Sorgen über Stil, wenn Sie die Richtigkeit Ding quadriert weg.
Im Idealfall gibt es drei Fälle zum Löschen eines Knotens in BST:
Fall 1:
X has no children: remove X
Fall 2:
X has one children : Splice out X
Fall 3:
X has two children : swap X with its successor and follow case #1 or #2
So für den fehlende Lösch Fall:
Wenn X (Knoten löschen zu) hat zwei Kinder, X mit dem Nachfolger von X ersetzen und Fall # 1 oder # 2 Fall folgen. Sie können auch mit seinem Vorgänger ersetzen, könnte eine gute Alternative sein.
if ( X->left && X->right)
{
NODE *Successor = FindSuccessor(X);
X->data = Successor->data;
free(Successor);
}
Diese binäre Codes einfügen, löschen, suchen und beenden. Beispiele:
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.
