C: In einem binärem Baum einen Knoten löschen?

Dieses Thema im Forum "Programmierung & Entwicklung" wurde erstellt von Gutschy, 22. Dezember 2016 .

Schlagworte:
  1. 22. Dezember 2016
    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

    Den Teil der den Knoten löscht zeige ich hier:
    Code:
    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!! :
     

    Anhänge:

  2. 22. Dezember 2016
    AW: C: In einem binärem Baum einen Knoten löschen?

    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.

    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.
     
  3. 23. Dezember 2016
    AW: C: In einem binärem Baum einen Knoten löschen?

    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.

    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.
    http://www.hs-augsburg.de/mebib/emiel/entw_inf/lernprogramme/baeume/gdi_kap_4_1.html

    Nochmal Danke xXsoureXx
     

    Anhänge:

  4. 25. Dezember 2016
    AW: C: In einem binärem Baum einen Knoten löschen?

    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.
     
  5. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.