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

Schnelle objektorientierte, kompilierende Programmiersprache.
Antworten
MiCsoft
Beiträge: 7
Registriert: So Nov 08, 2020 8:18 pm

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

Beitrag von MiCsoft » Mo Nov 09, 2020 3:31 pm

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

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8641
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

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

Beitrag von Xin » Mo Nov 09, 2020 4:57 pm

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.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

MiCsoft
Beiträge: 7
Registriert: So Nov 08, 2020 8:18 pm

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

Beitrag von MiCsoft » Mo Nov 09, 2020 7:54 pm

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

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8641
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

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

Beitrag von Xin » Mo Nov 09, 2020 8:16 pm

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?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

MiCsoft
Beiträge: 7
Registriert: So Nov 08, 2020 8:18 pm

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

Beitrag von MiCsoft » Mo Nov 09, 2020 8:54 pm

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

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8641
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

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

Beitrag von Xin » Di Nov 10, 2020 12:52 am

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?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

MiCsoft
Beiträge: 7
Registriert: So Nov 08, 2020 8:18 pm

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

Beitrag von MiCsoft » Di Nov 10, 2020 8:59 am

Xin danke =) jetzt habe ich den Fehler gefunden :-D
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);

}

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8641
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

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

Beitrag von Xin » Di Nov 10, 2020 6:20 pm

Ähh... ja... <stirnklatsch-smiley-einfügen> :-D
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

MiCsoft
Beiträge: 7
Registriert: So Nov 08, 2020 8:18 pm

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

Beitrag von MiCsoft » Di Nov 10, 2020 6:58 pm

Manchmal ist die Lösung so nahe und doch so fern :-D

Antworten