Vollständige Version anzeigen : C: In einem binärem Baum einen Knoten löschen?


Gutschy
22.12.2016, 00:55

Hallo Leute,

wie lösche ich einen Knoten in einem binärem Baum, tja. Ich lese dazu die 10 Zeilen Code aber es macht nicht Klick.

Hier will ich mal versuchen einen Baum aufzubauen.

....;/--------100-------\
...;/ ........................;\
..;/-90-\ ...........;/-----110----\
.;/.......;\..........;/ ................;\
70 .....;80 ...................;/------105-----\
.........................;/----103----\ .........;108
.......................;/.................;\
....................;102..............;104

Der Code ermöglicht mir den Knoten 105 zu löschen. Diesen Code habe ich mir hier abgeschrieben.
Rheinwerk Computing :: C von A bis Z – 22;4 Suchalgorithmen – Grundlage zur Suche (;openbook;rheinwerk-verlag~de/c_von_a_bis_z/022_c_algorithmen_004;htm#mje1108bedaa52e56c3a2231952efc760d)

Den Teil der den Knoten löscht zeige ich hier:
void loesche_knoten(KNOTEN **zeiger) {
KNOTEN *temp;
int tempwert;

if(globale_wurzel == *zeiger) {
printf("Kann die Wurzel nicht loeschen!!\n");
return;
}
if((*zeiger)!=NULL) { /* Blatt! */
if((*zeiger)->links==NULL && (*zeiger)->rechts==NULL) {
free(*zeiger);
*zeiger=NULL;
}
else if((*zeiger)->links==NULL) {
/* Nur rechter Nachfolger */
temp = *zeiger;
*zeiger=(*zeiger)->rechts;
free(temp);
}
else if((*zeiger)->rechts==NULL) {
/* Nur linker Nachfolger */
temp = *zeiger;
*zeiger=(*zeiger)->links;
free(temp);
}
else { /* 2 Nachfolger, wir suchen Ersatzelement */
suche_ersatz(&tempwert, &((*zeiger)->rechts));
(*zeiger)->wert=tempwert;
}
}
}

void suche_ersatz(int *neuwert, KNOTEN **zeiger) {
KNOTEN *temp;

if(*zeiger != NULL) {
if((*zeiger)->links==NULL) {
neuwert=(*zeiger)->wert;
temp=*zeiger;
*zeiger=(*zeiger)->rechts;
free(temp);
}
else
suche_ersatz(neuwert, &((*zeiger)->links));
}
}



Es geht alles klar bis in der Funktion 'loesche_knoten' der else-Zweig aufgerufen wird, dieser ruft die Funktion 'suche_ersatz' auf. Dem Code von 'suche_ersatz' kann ich soweit Folgen das dieser rekursiv solange aufgerufen wird bis er auf das Blatt 102 kommt, dieser Wert wird dann in 'neuwert' gespeichert. Dann wird dieses Blatt gelöscht. Aber warum dann '*zeiger = (*zeiger)->rechts;' passiert und in der Funktion 'loesche_knoten' im else-Zweig noch ein '(*zeiger) -> wert = tempwert;' kommt? Wird denn diese Zeile auch rekursiv aufgerufen, nur weil 'suche_ersatz' aufgerufen wird? Ich habe den Code jetzt so begriffen das die Werte im Baum nach oben wandern müßen um den Platz vom Knoten mit dem Wert 105 zu übernehmen. Aber äähhhh....

Hänge da schon eine weile davor und es will nicht einleuchten. Den ganzen Code mache ich mal als Anhang.

Gruss,

Gutschy

..;und natürlich an alle frohes Fest und einen guten Rutsch!! :

Hardware Preisvergleich | Amazon Blitzangebote!

Videos zum Thema
Video Loading...
xXsoureXx
22.12.2016, 15:08

Vorweg, ich glaube du hast eine veraltete Datei hochgeladen, da dort Fehler drin sind, die ich bei dir im Post nicht sehe (Bsp Z. 162)

Ohne dein Programm ausgeführt zu haben, behaupte ich, dass deine Folgerung suche_ersatz lande bei Knoten 102 (ausgehend von 105), falsch ist. Richtig, einmal initialisiert sucht suche_ersatz im Baum immer weiter nach links um ein passenden Knoten zu finden, aufgerufen wird es aber mit (*zeiger)->rechts (Z. 148).

Ausgehend von Knoten 105 folgt daraus somit der Knoten 108, der wiederum ein Blatt ist. Ein perfekter Kandidat also.

Aber warum dann '*zeiger = (*zeiger)->rechts;' passiert und in der Funktion 'loesche_knoten' im else-Zweig noch ein '(*zeiger) -> wert = tempwert;' kommt? Wird denn diese Zeile auch rekursiv aufgerufen, nur weil 'suche_ersatz' aufgerufen wird?

Hat der Knoten zwei Nachfolger, so wird dieser in Wahrheit gar nicht gelöscht. Dieser kleine Kniff mag dich hier evtl. verwirren. suche_ersatz löscht nämlich in diesem Fall den gefundenen Ersatzknoten (Knoten 108) [Z. 165]. Da dies aber offensichtlich nicht das Ziel ist, speichert die Funktion die Informationen des Knotens im parameter neuwert. Der Knoten, der ursprünglich gelöscht werden sollte (Knoten 105), wird anschließend überschrieben ((*zeiger) -> wert = tempwert, Z. 149).

*zeiger = (*zeiger)->rechts; ist wichtig, da der gefundene Knoten, zwar sicher keinen linken Nachfolger hat, eventuell aber einen rechten. Der darf nicht verloren gehen!

Ziemlich hässlicher Stil imho.


Gutschy
23.12.2016, 10:06

Hi xXsoureXx,

danke für deine Hilfe, bin jetzt durch dich schon weiter. Also im else-Zweig von 'loesch_knoten' wird 'suche_ersatz(&tempwert, &((*zeiger ->rechts));' wobei '&tempwert' beim ersten Aufruf noch ohne Inhalt ist. Nach Abarbeitung der Funktion ist dort in 'tempwert' der Wert des rechten Knoten gespeichert. Dieser Wert überschreibt dann den Ausgangsknoten. '(*zeiger) -> wert = tempwert;'
Das habe ich jetzt begriffen. :thumbsup:

Nur wenn es unter dem zu löschenden Knoten noch z;B. 4 Ebenen geben sollte dann wird ja von 'suche_ersatz' der else-Zweig ausgeführt, solange bis die if-Bedingung stimmt 'if((*zeiger) -> links == NULL)'. Dann ist in 'neuwert' aber nur irgendein Wert;'neuwert=(int *)(*zeiger) -> wert;' Der Wert der letzten Ebene, die gelöscht worden ist, wird dann eine Ebene höher kopiert.

Aber dann verstehe ich es so das die Anzahl der Ebenen von 4 auf 3 geschrumpft ist, aber nur so das der Wert des letzten Blattes eine Ebene nach oben gewandert ist und der zu löschende Knoten aber gar nicht überschrieben wurde.

Mir ist klar das 'suche_ersatz' wohl irgendwie nach oben wandern müsste, aber ich begreife nicht wie das von statten gehen soll.

Anbei noch die von mir abgeschriebene Datei.

- - - - - - - - - - Beitrag zusammengefügt - - - - - - - - - -

Nachtrag:

Habe wohl einen Grundsätzlichen Fehler gemacht, auf jeden Fall ist mein Beispiel Binärbaum völlig falsch. Habe jetzt einen guten Link gefunden der alles viel ausführlicher erklärt und mir wahrscheinlich die Erleuchtung bringen wird.
(;;;hs-augsburg~de/mebib/emiel/entw_inf/lernprogramme/baeume/gdi_kap_4_1;html)

Nochmal Danke xXsoureXx


Gutschy
25.12.2016, 20:28

Nachtrag 2:

Ja, ich hatte ein Brett vor dem Kopf und das leider üblicherweise mal wieder viel zu lange!! (2 Wochen oder so..;) Auf jeden Fall ist es so, der rechte Knoten des zu löschenden Knoten hat auf seinen linken Ästen zwangsläufig nur Werte die größer sind als der zu löschende Knoten und darum kann der letzte linke Knoten einfach gelöscht werden und sein Wert auf dem zu löschenden Knoten einfach überschrieben werden. Falls der letzte linke Knoten noch einen rechten Knoten hat wird dieser Wert auf den letzten Linken Knoten übertragen.

Ist schon ziemlich peinlich das zuzugeben, aber mein Ruf ist ja schon seit langer Zeit ruiniert;:cool:


Ähnliche Themen zu C: In einem binärem Baum einen Knoten löschen?
  • schrift löschen bei einem Banner
    ------ [...]

  • [Video] Russische Polizisten versuchen einen Baum wegzuräumen
    Baum wegräumen - Video auf bildschirmarbeiter~com (;;;bildschirmarbeiter~com/video/baum_wegraeumen/) Wieviele russische Polizisten braucht man, um einen Baum wegzuräumen? Keine Ahnung, aber man braucht einen Baum um nen russischen Polizisten wegzukatapultie [...]

  • USA: Pferd konnte sich nicht mehr aus einem Baum befreien
    USA: Pferd konnte sich nicht mehr aus einem Baum befreien Ein Pferd aus Pullman, West Virginia (USA), namens Gracie blieb mit seinem Kopf in einem Baum stecken. Jason H;, der Besitzer des Pferdes, musste sein Pferd mit Hilfe einer Säge aus dessen misslicher Lage befreien. Seinem Pferd ist größ [...]

  • Wie kaue ich einen mai Baum ?
    Hey leute , Nicht mehr lange und wir haben weider den 1;mai =) das heißt maibaumklauen !!! =) Nur was muss man beachten ?? ich habe hier mal ein Paar regen. 1;Mann muss 3mal mit eine sparten an den maibaum schlagen um ihn zuklauen dabei darf ihn keiner der verteidiger berühren 2;Mann [...]



raid-rush.ws | Imprint & Contact pr