Binärbaum beim Löschen einen Knoten zurück geben

[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);
}

[Xin]

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.

[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);
}

[Xin]

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...

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?

[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;
}

[Xin]

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?

[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);

}

[Xin]

Ähh... ja... <stirnklatsch-smiley-einfügen>

[MiCsoft]

Manchmal ist die Lösung so nahe und doch so fern