Ich habe mir die Mühe gemacht es schrittweise Anhand eines Bildes erklärt
Hoffe, dir wird nun klar, wie es funzt.
1. Ein sortierter Binärbaum ist gegeben
2. Der Knoten "25" soll entfernt werden
3. Entfernung des Knotens (left, right & parent merken!)
Weg A
4. Du ermittelst den
linkesten Knoten vom
rechten Teil (= 30)
Weg B
4. Du ermittelst den
rechtesten Knoten vom
linken Teil (= 10)
5. Dieser Knoten übernimmt nun einfach all die Werte vom zerstörten Knoten (left/right/parent).
6. Der Knoten, der bei 4 ermittelt wurde, wird im Anschluss mit derselben Routine auch zerstört
Btw. es ist egal, ob du Weg A oder Weg B gehst.
Vlt ist Punkt 6. nicht ganz klar - weil es sein kann, dass dieser Knoten einen Nachbarn hat, muss es nochmal ausgeführt werden.
Denk dir einfach, dass die Knoten 10 und 30 jeweils auch Kinder besitzen [10 besitzt 9 (left) und 30 besitzt 31 (right)]
Noch etwas - ich weiß nicht, wie weit ihr im Unterricht schon seid, aber Schritt 6 verlangt, dass der Algorithmus rekursiv ist!
Edit: @Zacherl
Er meinte, es soll nur ein Knoten entfernt werden. Alle darunterliegenden Subnodes müssen erhalten bleiben!