Methoden BinärBaum als String Knoten löschen

[Basha]

Hallo,

folgendes Problem, ich habe einen BinärBaum erstellt, der Strings als Knoten besitzt.
Nun habe ich eine löschmethode geschrieben die aber nicht funktionieren will.
Ich hoffe ihr könnt mir ein wenig helfen.

die Knoten classe

class Knoten {
   	public String daten;            // Datenelement
   	public Knoten links, rechts;  // Zeiger auf Nachfolgeknoten

        Knoten( String n ) {
     	daten  = n;
      	links  = null;
	rechts = null;
   	}
}

Hier die einfuege und loesch methode

public class Baum {

    public Knoten wurzel = null;    // Baum ist leer


 
// Einfuegen eines Knotens
/**
 * 
 * @param x der String das eingefügt werden soll. 
 */
    public void einfuegen(String x) {
        if (wurzel == null) {
            wurzel = new Knoten(x);
            save_value(x);
        } else {
            einrek(wurzel, x);
            save_value(x);
        }
    }


 // Knoten Loeschen

    public Knoten loeschen(String x) {
        Knoten stamm = wurzel;
        Knoten eltern = wurzel;

        boolean istEsLinks = true;

        if (wurzel == null) {
            return null;
        }

        while (stamm.daten.compareToIgnoreCase(x) != 0) {
            eltern = stamm;
            if (stamm.daten.compareToIgnoreCase(x) > 0) {
                istEsLinks = true;
                stamm = stamm.links;
            } else {
                istEsLinks = false;
                stamm = stamm.rechts;
            }
            if (stamm == null) {
                return null;
            }
            if (stamm.links == null && stamm.rechts == null) {

                if (stamm == wurzel) {
                    wurzel = null;
                } else if (istEsLinks) {
                    eltern.links = null;
                } else {
                    eltern.rechts = null;
                }

            } else if (stamm.rechts == null) {
                if (stamm == wurzel) {
                    wurzel = stamm.links;
                } else if (istEsLinks) {
                    eltern.links = stamm.links;
                } else {
                    eltern.rechts = stamm.links;
                }

            } else if (stamm.links == null) {
                if (stamm == wurzel) {
                    wurzel = stamm.rechts;
                } else if (istEsLinks) {
                    eltern.links = stamm.rechts;
                } else {
                    eltern.rechts = stamm.links;
                }

            } else {
                Knoten ersetzen = knotenErsetzen(stamm);

                if (stamm == wurzel) {
                    wurzel = ersetzen;
                } else if (istEsLinks) {
                    eltern.links = ersetzen;
                } else {
                    eltern.rechts = ersetzen;
                    ersetzen.links = stamm.links;
                }
            }
        }
        return stamm;
    }

    public Knoten knotenErsetzen(Knoten e) {
        Knoten elternErsetzen = e;
        Knoten ersetzen = e;

        Knoten stamm = e.rechts;

        while (stamm != null) {
            elternErsetzen = ersetzen;
            ersetzen = stamm;
            stamm = stamm.links;
        }
        if (ersetzen != e.rechts) {
            elternErsetzen.links = ersetzen.rechts;
            ersetzen.rechts = e.rechts;
        }
        return ersetzen;
    }

ich hoffe sehr dass ihr damit etwas anfangen könnt^^
mfg basha

 

[Adelhorst]

Hallo.
Ich würde an deiner Stelle zuerst einmal eine Methode schreiben, die dir zu deinem String den passenden Knoten findet und zurück gibt. Diese Methode kann man immer gebrauchen und damit hättest du schon einmal den ersten Schritt erledigt und hättest genau DEN Knoten, der entfernt werden muss.

Dein Ansatz hierzu ist noch nicht ganz vollständig:
Hier sagst du, wenn der stamm.string > als x ist, dann muss im linken Teilbaum gesucht werden; andernfalls muss in jedem Fall im rechten Teilbaum gesucht werden.
Du fragst hier aber NIE auf == 0 ab, somit wirst du NIE fündig werden!

            if (stamm.daten.compareToIgnoreCase(x) > 0) {
                istEsLinks = true;
                stamm = stamm.links;
            } else {
                istEsLinks = false;
                stamm = stamm.rechts;
            }

Also erstmal eine funktionierende 'Knoten find(String x)'-Methode erstellen und dann kannst du mit Entfernen weitermachen.
Was du als "stamm" bezeichnest könnte man auch als "teilbaum" oder besser "knoten" bezeichnen, und statt "eltern" würde ich eher "vater" vorschlagen, denn das sind eher die Bezeichnungen in einem Binärbaum. (Wurzel, Vater, Knoten, Blatt..)

 

[Basha]

Hallo,

eine such methode habe ich bereits.
so habe alles nu geändert was du mir vorgeschlagen hast.
aber ich verstehe um erhlich zu sein nicht warum ich auf == 0 abfragen soll es kann ja nur nach links oder rechts.

public Knoten suchen(String x) {
        Knoten knoten = wurzel;
        if (knoten.daten == null) {
            return null;
        }
        while (knoten.daten.compareToIgnoreCase(x) != 0) {
            if (knoten.daten.compareToIgnoreCase(x) > 0) {
                knoten = knoten.links;
            } else {
                knoten = knoten.rechts;
            }
        }
        return knoten;

    }

    public Knoten loeschen(String x) {
        Knoten knoten = wurzel;
        Knoten vater = wurzel;

        boolean istEsLinks = true;

        if (wurzel == null) {
            return null;
        }

        while (knoten.daten.compareToIgnoreCase(x) != 0) {
            vater = knoten;
            if (knoten.daten.compareToIgnoreCase(x) > 0) {
                istEsLinks = true;
                knoten = knoten.links;
            } else {
                istEsLinks = false;
                knoten = knoten.rechts;
            }
            if (knoten == null) {
                return null;
            }
            if (knoten.links == null && knoten.rechts == null) {

                if (knoten == wurzel) {
                    wurzel = null;
                } else if (istEsLinks) {
                    vater.links = null;
                } else {
                    vater.rechts = null;
                }

            } else if (knoten.rechts == null) {
                if (knoten == wurzel) {
                    wurzel = knoten.links;
                } else if (istEsLinks) {
                    knoten.links = knoten.links;
                } else {
                    knoten.rechts = knoten.links;
                }

            } else if (knoten.links == null) {
                if (knoten == wurzel) {
                    wurzel = knoten.rechts;
                } else if (istEsLinks) {
                    vater.links = knoten.rechts;
                } else {
                    vater.rechts = knoten.links;
                }

            } else {
                Knoten ersetzen = knotenErsetzen(knoten);

                if (knoten == wurzel) {
                    wurzel = ersetzen;
                } else if (istEsLinks) {
                    vater.links = ersetzen;
                } else {
                    vater.rechts = ersetzen;
                    ersetzen.links = knoten.links;
                }
            }
        }
        return knoten;
    }

    public Knoten knotenErsetzen(Knoten e) {
        Knoten elternErsetzen = e;
        Knoten ersetzen = e;

        Knoten stamm = e.rechts;

        while (stamm != null) {
            elternErsetzen = ersetzen;
            ersetzen = stamm;
            stamm = stamm.links;
        }
        if (ersetzen != e.rechts) {
            elternErsetzen.links = ersetzen.rechts;
            ersetzen.rechts = e.rechts;
        }
        return ersetzen;
    }

 

[Adelhorst]

Hallo.
Da muss ich dir Recht geben, da lag ICH falsch. Ich hatte die While-Abfrage mit !=0 übersehen, da prüfst du ja schon, ob der Knoten nicht schon den gesuchten String enthält. Sorry.

 

[Basha]

Hm hat sonst noch jemand eine idee?

 

[Adelhorst]

Hallo.
Ich kann den weiteren Code von dir nicht tatsächlich verstehen.
Du machst Ersetzungen und dergleichen in einer while-schleife, wo du den tatsächlichen zu entfernenden Knoten ja erst noch suchst; alo noch gar nicht gefunden hast! Das irritiert mich schon mal.

Das Entfernen/Löschen eines Knotens mit mehr als einem Sohn ist nicht so einfach.
Meines Erachtens müsste es so ablaufen:

1. Betreffenden Knoten erstmal suchen.
(Bei der Suche muss man sich den Knoten(Sohn) merken, der den betreffenden String-/daten-wert x enthält, UND den dazugehröigen "Vater"-Knoten)

1a. Falls kein betreffender Knoten(Sohn) gefunden, dann abbrechen...

2b. Falls betreffender Knoten(Sohn) mit dem String x gefunden, dann ...
Fall1 (sehr einfach):
Hat dieser Knoten(Sohn) selbst keine weiteren Söhne, ist also ein 'Blatt', dann braucht nur der Verweis vom Vater auf diesen Knoten(Sohn) auf Null gesetzt werden. Damit ist dieser gelöscht, fertig.
Fall2 (einfach):
Hat dieser Knoten(Sohn) selbst nur EINEN Sohn (egal, ob Sohn.links oder Sohn.rechts), dann kann der Sohn-Knoten einfach entfernt werden, indem der Verweis "Vater-Sohn" auf "Vater-Sohn.links" bzw. "Vater-Sohn.rechts" umgebogen wird. Fertig.

Fall3 (schwierig):
Hat dieser Knoten(Sohn) selbst ZWEI Söhne, dann muss im linken Teilbaum von Knoten(Sohn) der MaxKnoten gesucht werden, d.h. man geht in den linken Teilbaum des Knoten(Sohn) und von da aus dann immer nur in die rechten Teilbäume, bis es nicht mehr weiter geht. Dann hat man den Knoten mit dem maximalen daten-Wert gefunden. Den Knoten nennen wir mal MaxKnoten.
(Für dieses Suchen kann man eine eigene Methode 'Knoten maxKnoten(Knoten x)' spendieren)
Nun muss man sich den daten-Wert dieses MaxKnoten merken (tmp = MaxKnoten.daten); dann muss durch rekursiven Aufruf der Methode 'löschen' dieser MaxKnoten gelöscht werden (löschen(MaxKnoten.daten)); und zum Schluß erhält der Knoten(Sohn) den gemerkten MaxKnoten-Wert (Sohn.daten = tmp).