Seite 1 von 1
Binärbaum beim Löschen einen Knoten zurück geben
Verfasst: Mo Nov 09, 2020 3:31 pm
von MiCsoft
Schönen Tag zusammen,
ich hab eine Problem und zwar habe ich in einem Binärbaum Knoten gespeichert, in diesen Knoten sind wieder Artikel gespeichert die ich aus einer Datei einlese.
Nun soll ich beim Löschen des Knoten den Inhalt als Zeiger zurück geben. Wenn ich den Knoten aber per free() frei gebe ist der Zeiger nicht mehr existent. Kann mir jemand erklären wie ich das Problem umgehen kann? Soll ich die Löschen Methode dann Iterativ Programmieren?
Hier einmal der Code des Aufbau der Struktur die vom Baum verwaltet werden:
Code: Alles auswählen
typedef struct node {
struct artikel *artikel;
struct node *left;
struct node *right;
} node;
und hier die Lösche Methode:
Code: Alles auswählen
void loesche_knoten(node **zeiger) {
node *temp;
if ((*zeiger) != NULL) {
if ((*zeiger)->left == NULL && (*zeiger)->right == NULL) { //Fall 1 Blattknoten
free(*zeiger);
*zeiger = NULL;
} else if ((*zeiger)->left == NULL) { //Fall 2 ein untergeordnetes Element
temp = *zeiger;
*zeiger = (*zeiger)->right;
free(temp);
} else if ((*zeiger)->right == NULL) { //Fall 2 ein untergeordnetes Element
temp = *zeiger;
*zeiger = (*zeiger)->left;
free(temp);
} else { //Fall 3 im linken Teilbaum den größten Wert
temp = (*zeiger)->left;
node *hilfsZeiger = NULL;
while (temp->right != NULL) {
hilfsZeiger = temp;
temp = temp->right;
}
hilfsZeiger->right = temp->left;
temp->left = (*zeiger)->left;
temp->right = (*zeiger)->right;
free(*zeiger);
*zeiger = temp;
}
}
}
void loesche(node **zeiger, int such) {
if ((*zeiger) == NULL) {
printf("Knoten nicht gefunden!\n");
}
// Knoten wurde Gefunden
else if ((*zeiger)->artikel->artikelnr == such) {
loesche_knoten(zeiger);
} else if ((*zeiger)->artikel->artikelnr >= such)
loesche(&((*zeiger)->left), such);
else
loesche(&((*zeiger)->right), such);
}
void entfernen(baum *b, int nr) {
loesche(&b->root, nr);
}
Re: Binärbaum beim Löschen einen Knoten zurück geben
Verfasst: Mo Nov 09, 2020 4:57 pm
von Xin
MiCsoft hat geschrieben: ↑Mo Nov 09, 2020 3:31 pm
Nun soll ich beim Löschen des Knoten den Inhalt als Zeiger zurück geben. Wenn ich den Knoten aber per free() frei gebe ist der Zeiger nicht mehr existent. Kann mir jemand erklären wie ich das Problem umgehen kann? Soll ich die Löschen Methode dann Iterativ Programmieren?
Was spricht dagegen, sich erst den Zeiger des Artikels zu merken, dann den Knoten zu löschen und dann den Zeiger zurück zu geben?
free() löscht den Artikel ja schließlich nicht mit.
Re: Binärbaum beim Löschen einen Knoten zurück geben
Verfasst: Mo Nov 09, 2020 7:54 pm
von MiCsoft
Das habe ich schon versucht doch ich bekomme dann NULL zurück und weiß nicht genau wieso.
Hab "einfach" bloß hier einen artikel * zurück geben lassen doch irgendwie kommt nix zurück =(
Code: Alles auswählen
artikel *loesche(node **zeiger, int such) {
if ((*zeiger) == NULL) {
printf("Knoten nicht gefunden!\n");
return NULL;
}
// Knoten wurde Gefunden
else if ((*zeiger)->artikel->artikelnr == such) {
artikel *a = (*zeiger)->artikel;
loesche_knoten(zeiger);
return a;
} else if ((*zeiger)->artikel->artikelnr >= such)
loesche(&((*zeiger)->left), such);
else
loesche(&((*zeiger)->right), such);
}
Re: Binärbaum beim Löschen einen Knoten zurück geben
Verfasst: Mo Nov 09, 2020 8:16 pm
von Xin
MiCsoft hat geschrieben: ↑Mo Nov 09, 2020 7:54 pm
Das habe ich schon versucht doch ich bekomme dann NULL zurück und weiß nicht genau wieso.
Das kann ja nur passieren, wenn der Knoten gar nicht gefunden wurde. Also stellt sich die Frage, wieso der Knoten nicht gefunden wurde...
MiCsoft hat geschrieben: ↑Mo Nov 09, 2020 7:54 pm
Code: Alles auswählen
} else if ((*zeiger)->artikel->artikelnr >= such)
loesche(&((*zeiger)->left), such);
else
loesche(&((*zeiger)->right), such);
}
Wie wird der Baum denn aufgebaut?
Re: Binärbaum beim Löschen einen Knoten zurück geben
Verfasst: Mo Nov 09, 2020 8:54 pm
von MiCsoft
Ja der Baum wird aufgebaut. Die Methoden kann ich auch gerne mal Posten.
Das was ich eben auch nicht verstehe ist das ich mir vorher den Artikel ausgeben lassen kann in der Methode.
Sprich ich
Code: Alles auswählen
// Knoten wurde Gefunden
else if ((*zeiger)->artikel->artikelnr == such) {
artikel *a = (*zeiger)->artikel;
ausgabeArtikel(a); //Zeit mir hier genau den Artikel an, doch nach loesche_knoten ist a plötzlich NULL
loesche_knoten(zeiger);
return a;
}
Hier mal das einfügen. Doch das funktioniert auch das löschen geht nur bekomme ich eben kein Zeiger mehr zurück und verstehe einfach nicht wieso =(
Code: Alles auswählen
void einfuegen(baum *b, artikel *a) {
if (b->root == NULL) {
b->root = getNode(a);
return;
} else
recEinfuegen(b->root, a);
}
node *recEinfuegen(node *zeiger, artikel *a) {
if (zeiger == NULL)
zeiger = getNode(a);
else {
if (zeiger->artikel->artikelnr > a->artikelnr)
zeiger->left = recEinfuegen(zeiger->left, a);
else
zeiger->right = recEinfuegen(zeiger->right, a);
}
return zeiger;
}
Re: Binärbaum beim Löschen einen Knoten zurück geben
Verfasst: Di Nov 10, 2020 12:52 am
von Xin
MiCsoft hat geschrieben: ↑Mo Nov 09, 2020 8:54 pm
Code: Alles auswählen
// Knoten wurde Gefunden
else if ((*zeiger)->artikel->artikelnr == such) {
artikel *a = (*zeiger)->artikel;
ausgabeArtikel(a); //Zeit mir hier genau den Artikel an, doch nach loesche_knoten ist a plötzlich NULL
loesche_knoten(zeiger);
return a;
}
"a" kann in dem Moment nicht Null sein, denn a wird nach loesche_knoten nicht überschrieben.
Wenn a dann wirklich Null wäre, würde in loesche_knoten massiv was falsch laufen.
Wenn Du also ausgabeArtikel nach loesche_knoten wieder mit a aufrufst, was kommt da raus?
Und wie sieht loesche_knoten aus?
Re: Binärbaum beim Löschen einen Knoten zurück geben
Verfasst: Di Nov 10, 2020 8:59 am
von MiCsoft
Xin danke =) jetzt habe ich den Fehler gefunden
Also es stimmt wohl alles am Code etc. ich hab hier glaube ich ein Logik Fehler drin
Hab die 2 Methoden so umgeschrieben und schon klappt es
Code: Alles auswählen
artikel *loesche(node **zeiger, int such) {
if ((*zeiger) == NULL) {
printf("Knoten nicht gefunden!\n");
}
// Knoten wurde Gefunden
else if ((*zeiger)->artikel->artikelnr == such) {
artikel *a = (*zeiger)->artikel;
loesche_knoten(zeiger);
return a;
} else if ((*zeiger)->artikel->artikelnr >= such)
loesche(&((*zeiger)->left), such);
else
loesche(&((*zeiger)->right), such);
//hier return NULL; doof!
}
artikel *entfernen(baum *b, int nr) {
return loesche(&b->root, nr);
}
Das Problem ist nur das in der Methode loesche ich nun nur 1 return drin stehen habe und sonst keinen dann mekert er ja gelb an das er ein return braucht. Wenn ich nun naiv wie die ganze Zeit ganz unten mein return NULL; rein schreibe dann bekomme ich NULL in die main.c zurück =D oh man...
Hab es nun so geändert und es klappt =) Wäre nur super Lieb wenn du das kurz überfliegen würdest und mir sagen könntest ob ich jetzt nicht einen anderen denkfehler drin habe =D
Code: Alles auswählen
artikel *loesche(node **zeiger, int such) {
artikel *a = NULL;
if ((*zeiger) == NULL) {
printf("Knoten nicht gefunden!\n");
return a;
}
// Knoten wurde Gefunden
else if ((*zeiger)->artikel->artikelnr == such) {
a = (*zeiger)->artikel;
loesche_knoten(zeiger);
return a;
} else if ((*zeiger)->artikel->artikelnr >= such)
return loesche(&((*zeiger)->left), such);
else
return loesche(&((*zeiger)->right), such);
}
Re: Binärbaum beim Löschen einen Knoten zurück geben
Verfasst: Di Nov 10, 2020 6:20 pm
von Xin
Ähh... ja... <stirnklatsch-smiley-einfügen>
Re: Binärbaum beim Löschen einen Knoten zurück geben
Verfasst: Di Nov 10, 2020 6:58 pm
von MiCsoft
Manchmal ist die Lösung so nahe und doch so fern