Naives links rechts einfügen in ADT Baum

[ocsme]

Hallo zusammen,

hab eine Frage ich möchte sehr gerne einen Baum "irgendwie" füllen.
Also "einfach" von links nach rechts. Die Werte sollen dabei eben nicht verglichen werden
Ich setzt den ersten Wert auf die Wurzel und dann soll geprüft werden ist links etwas NEIN da kommt der nächste Wert rein. Beim nächsten insert muss das nächste Element nach Rechts. Danach will ich eine Ebene tiefer einfügen und da ist das Problem. Muss man dabei echt immer wieder alles abfragen denn jetzt müsste ich ja fragen ist von der Wurzel etwas links oder rechts Ja Ja also Wurzel -> links bei dem Knoten nachschauen und dort abfragen ist links schon etwas oder rechts ... und immer so weiter
Funktioniert das überhaupt "so einfach"? Denn ich glaube das wird etwas komplizierter.

Mir ist leider nichts dazu eingefallen. Was man sicherlich machen könnte wäre die Ebene zu speichern und dann sagen von bis ist diese Ebene also lauf durch und füg ein. Das wollte ich jetzt aber nicht alles so umschreiben (Fauler Mensch ) deswegen mal hier nachfragen ob jemand eine Idee hat.

Momentan ist es eben totaler Quatsch und sieht so aus:

    public boolean insert(T element) {
        if (isEmpty()) {
            root = new Node<T>(element);
            return true;
        } else
            insert(element, root);
        return true;
    }

    private Node<T> insert(T element, Node<T> node) {
        if (node == null)
            node = new Node<T>(element);
        else {
            if(node.getLeft() == null && node.getRight() == null)
                node.setLeft(insert(element, node.getLeft()));
            else node.setRight(insert(element,node.getRight()));
        }
        return node;
    }

Wie gesagt wenn das ganze zu Kompiliert werden würde dann lassen wir das erst mal und ich werde mich damit wieder beschäftigen wenn ich nicht noch 1000 Aufgaben hätte die ich machen MUSS (muss naja Freiwillig doch bringt hoffentlich etwas )

Liebe Grüße

 

[mihe7]

Wenn ich Dich richtig verstanden habe, dann willst Du eine Breitensuche nach einem noch nicht vollständig gefüllten Knoten durchführen.

Dazu legst Du Dir eine Todo-Liste an. In die steckst Du zu Beginn die Wurzel. Jetzt arbeitest Du die Todo-Liste ab, bis sie leer ist. Dabei entnimmst Du das erste Element der Liste (=Knoten, zu Beginn ist das gerade die Wurzel), schaust ob dieses Element Deinen Anforderungen entspricht. Falls ja, hast Du den gesuchten Knoten gefunden. Falls nein, fügst Du alle unmittelbaren Kindknoten des Elements hinten an die Todo-Liste an.

Beispiel mit einem vollständig gefüllten, binären Baum der Höhe 3 (inkl. Wurzel). Die Knoten seien von 0 bis 8 von oben nach unten, von links nach rechts durchnummeriert:

todo = {0} // Wurzelknoten in Todo-Liste
e := todo.remove(0); // e == 0
e ist vollständig gefüllt (Kindknoten 1, 2) also beide Kinder in Todo-Liste stecken -> todo = {1,2}
e := todo.remove(0); // e == 1
e ist vollständig gefüllt (Kindknoten 3,4) also beide Kinder in Todo-Liste stecken -> todo = {2, 3, 4}
e := todo.remove(0); // e == 2
e ist vollständig gefüllt (Kindknoten 5, 6) also beide Kinder in Todo-Liste stecken -> todo = {3, 4, 5, 6}
e := todo.remove(0); // e == 3
e ist nicht vollständig gefüllt -> Suche beendet, nächster Eintrag muss also an e eingefügt werden...

 

[ocsme]

Moment Breitensuche und Tiefensuche habe ich eh noch nicht verstanden wird noch gemacht

Soll ich jedem Knoten also eine Nummer geben die könnte man dann leicht Abfragen und bei jedem insert Aufruf kommen 2 Knoten zur toDo Liste hinzu?

Danke für die schnelle Antwort

LG

 

[mihe7]

Soll ich jedem Knoten also eine Nummer geben die könnte man dann leicht Abfragen

Nein, die Nummer habe ich nur zu Darstellungszwecken gewählt. Du steckst in die Todo-Liste einfach Knoten-Objekte.

bei jedem insert Aufruf kommen 2 Knoten zur toDo Liste hinzu?

Es kommen alle Kindknoten hinzu. Bei einem binären Baum sind das 2

Das, was ich beschrieben habe, ist ein iterativer Ansatz.

 

[mihe7]

Noch was: das Vorgehen ist für Bäume, deren Knoten einen In-Grad von max. 1 haben. Für komplexere Bäume, ist die Lösung auch etwas komplizierter (Du musst Dir dann merken, welche Knoten Du bereits besucht hast).

 

[ocsme]

Noch was: das Vorgehen ist für Bäume, deren Knoten einen In-Grad von max. 1 haben. Für komplexere Bäume, ist die Lösung auch etwas komplizierter (Du musst Dir dann merken, welche Knoten Du bereits besucht hast).

Leider bekomme ich es derzeit nicht hin! Werde das ganze hinten anstellen und es später wieder versuchen wenn wir Breitensuche bzw. Graphen durch haben
Ich danke dir für die Hilfe. Werde mich nochmal melden
Schreib es mir auf die toDo Liste

Das größte Problem was ich habe ist wie komme ich nachdem ich das erste Element rechts hin gesetzt habe wieder rechts rein.
Da bin ich eher versucht das ganze Mathematisch zu lösen über 2^t. t könnte man als Datenelement abspeichern und dann aufteilen wo was hin müsste. Das ganze hab ich noch nicht durchgespielt war nur meine erste Idee
Sonst wird mir das alles zu Komplex auch wenn es sicherlich nur ein paar Zeilen sind. So lange bin ich ja noch nicht "aktiv" im Geschäft

LG

 

[mihe7]

Das größte Problem was ich habe ist wie komme ich nachdem ich das erste Element rechts hin gesetzt habe wieder rechts rein.

???

Wenn Du das rekursiv machen möchtest, dann übergibst Du in der Rekursion nicht einen einzelnen Knoten sondern die Todo-Liste.

 

[Meniskusschaden]

Da bin ich eher versucht das ganze Mathematisch zu lösen über 2^t. t könnte man als Datenelement abspeichern und dann aufteilen wo was hin müsste. Das ganze hab ich noch nicht durchgespielt war nur meine erste Idee

Für so einen Ansatz könntest du die Anzahl der enthaltenen Elemente im Baum speichern und daraus beim Einfügen den Pfad zur korrekten Position errechnen. Allerdings müsstest du beim Entfernen eines Elementes darauf achten, den Baum wieder in die korrekte Form zu bringen, damit nachfolgende Einfüge-Operationen weiterhin korrekt funktionieren.

Beispiele zum Einfügen der ersten sechs Knoten:
110 = 12 => Wurzel
210 = 102 => Wurzel, links
310 = 112 => Wurzel, rechts
410 = 1002 => Wurzel, links, links
510 = 1012 => Wurzel, links, rechts
610 = 1102 => Wurzel, rechts, links

 

[ocsme]

Noch einmal Danke
Werde das später wieder versuchen.

Hab andere Aufgaben die derzeit wichtiger sind da diese Aufgaben erledigt werden müssen

LG