Hilfestellellung bei Rekursivem Löschen

[Otz]

Hallo zusammen,

ich bin gerade dabei einen kleine Anwenudung zu implementieren. Diese verfügt zur Speicherung bestimmter Daten über eine Baumstruktur. siehe Anhang

Jeder der Knoten beinhaltet eine Liste mit seinen Kinderknoten.

Wie kann ich jetzt am besten einen gesammten Pfad aus der Datenstruktur entfernen.
Und zwar soll der Pfad nicht bis zur Wurzel gelöscht werden, sondern nur bis zu dem Knoten, der mindestens 2 Kindknoten besitzt. In meiner Skizze ist dies der Knoten 2 und die rot-markierten Knoten sind die zu löschenden.

Ich hoffe ich versteht mein Vorhaben und könnt mir helfen 😀

Grüße

 

[JStein52]

Ganz verstehe ich noch nicht was du vorhast, der Algorithmus wäre also: Lösche mir einen bestimmten Knoten und alles darunter, darüber aber nur bis zum nächsten Knoten der noch andere Unterknoten enthält ???

 

[Otz]

ok, ich muss wohl etwas ausholen...

in dem baum habe ich bestimmte string teile abgespeichert.
z.b.

String 1: Hallo du bla bla
String 2: Hallo du blub blub blub

wenn ich jetzt diese beide strings in meinen baum einfüge, ergibt sich genau die struktur des oben angehängten bildes.
nun möchte ich string 2 aus meinem baum entfernen. hierzu kann ich jedoch nicht den ganzen string rauswerfen, da sonst string 1 nicht mehr vollständig ist. deshalb entferne ich jetzt alle knoten des unteren pfades, bis zu dem knotenm, der mindestens 2 kinder besitzt. in diesem fall der knoten mit dem string "du". in diesem lösche ich jedoch die referenz auf den kindknoten "blub"

kann man es jetzt besser verstehen?

 

[Times]

Hm... ich hoffe ich bin nicht der einzige, sonst komm ich mir doof vor, aber ich verstehe es immernoch nicht.
Vielleicht kannst du ein Anwendungsbeispiel sagen, wofür du es genau brauchst, was willst du erreichen oder ein Beispiel ohne die Wörter:"Test, Hallo, bla, blub"... irgendetwas wodrunter man sich auch was vorstellen kann.

 

[JStein52]

So rein intuitiv verstehe ich was du machen willst auch wenn ich die Speicherstruktur noch nicht ganz durchschaue.
Wie würden z.B. folgende Strings abgespeichert:

String 1: Hallo du bla bla Freund
String 2: Hallo du blub blub blub Freund

 

[InfectedBytes]

Du fängst einfach beim tiefsten Knoten an und löscht solange rekursiv alle knoten, bis die Anzahl der Kinder > 0 ist

 

[JStein52]

@InfectedBytes : Hätte ich auch spontan gesagt, aber vielleicht können diese Bäume ja auch kompliziertere Formen (Netze? ) annehmen, deshalb meine Frage nach den beiden Strings vorhin.

 

[Otz]

So rein intuitiv verstehe ich was du machen willst auch wenn ich die Speicherstruktur noch nicht ganz durchschaue.
Wie würden z.B. folgende Strings abgespeichert:

String 1: Hallo du bla bla Freund
String 2: Hallo du blub blub blub Freund

sorry das ich mich so spät melde. hab eben erst wieder etwas zeit gefunden...

das wort freund wird einfach bei jedem der beiden pfade aus meiner zeichnung angefügt. also einmal als kind vom knoten 4 UND einmal als kind von knoten 7

also es werden keine netze gebildet...

 

[Otz]

edit: meine lösung stimmt leider noch nicht so ganz :/

 

[InfectedBytes]

und was ist deine lösung?
Wenn du uns deine Lösung verrätst, können wir versuchen den Fehler darin zu finden

 

[Otz]

currentNode ist die wurzel des baumes
stringparts ist eine arraylist mit mehrere wörtern als string

private void remove(TreeNode currentNode, List<String> stringparts) {
        for (TreeNode node : currentNode.getChilds()) {
            //alle kinder eines knoten durchlaufen
            if (node.getValue().equals(stringparts.get(0))) {
                //kinde ueberpruefen ob dieses mit dem übergeben string uebereinstimmt
                if (node.getChilds().get(0).getChilds().isEmpty()) {
                    // wenn das kind des aktuellen knoten ein blatt ist --> loeschen
                    node.getChilds().remove(0);
                } else {
                    //kind des aktuellen knoten ist kein blatt --> rekursiver aufruf
                    remove(node, stringparts.subList(1, stringparts.size()));
                  
                    //blatt wurde erreicht und geloescht
                    //alle kindknoten, die keine kinder mehr haben entfernen
                    ArrayList<TreeNode> tempList = new ArrayList<TreeNode>();
                    for(TreeNode tn : node.getChilds()){
                        if(tn.getChilds().size() > 0){
                            tempList.add(tn);
                        }
                    }
                    node.setChilds(tempList);
                }
            }
        }
    }

 

[JStein52]

Was genau geht denn deiner Meinung nach schief ? Ich sehe z.B. dass du wenn das Kind des aktuellen Knotens ein Blatt ist dieses löschst, ohne Rücksicht auf seinen Value ?? Ich kann nicht beurteilen ob das richtig ist scheint mir aber falsch. Und du gehst auch immer davon aus, dass der aktuelle Knoten nur ein Kind hat ( ...get(0)... ...remove(0)...

Aber vielleicht habe ich deine Speicherung auch immer noch nicht verstanden und denke zu kompliziert. Wie werden denn die folgenden drei Strings abgespeichert ?

1. Hugo ist froh und lacht
2. Hugo ist froh und munter
3. Hugo will essen

Gibt es da einen Bau mit dem gemeinsamen Knoten "Hugo" ? Und verzweigt der eine Teil weiter unten wieder bei dem Knoten "und" ???