BinärBaum einfügen

[ocsme]

Guten Tag,
ich hab ein Problem mit einer Übungsaufgabe 🙁
Aufgabenstellung:
Es soll eine Klasse BinTree mit einer inneren Klasse Node erstellt werden. Dazu noch eine Klasse Element die Comparable<Element> implementiert.
Nun soll eine insert Methode in BinTree geschrieben werden nach folgendem muster. public boolean insert(Element e) anhand der compareTo Methode sollen die Elemente links oder rechts im Baum landen. Bei Gleichheit soll false zurück kommen.

Das ganze habe ich bis jetzt so gemacht:

public class BinTree {
    protected Node root = null;
    
    protected class Node {
        Element value;
        Node left, right;
        
        Node(Element value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
        
        public String toString() {
            return value.toString();
        }
        
        public boolean isEmpty() {
            if(root == null)
                return true;
            return false;
        }
        
        public void inorder(Node n) {
            if (n.left != null) inorder(n.left);
            System.out.println(n.toString());
            if (n.right != null) inorder(n.right);
        }
        
        public boolean insert(Element e) {
            if(root == null) {
                root = new Node(e,null,null);
                return true;
            }
            return false;           
        }
        
    }
    
    class Element implements Comparable<Element> {
        private int value;
        
        Element(int value) {
            this.value = value;
        }
        
        public int compareTo(Element e) {
            if(getValue() > e.getValue())
                return 1;
            if(getValue() < e.getValue())
                return -1;
            return 0;
        }
        
        public String toString() {
            return ""+getValue();
        }
        
        public int getValue() {
            return value;
        }
        
    }

}

Mein Problem ist nun die insert Methode.
Der erste Ansatz war rekursiv über 2 Methoden (Schematisch so)

void rekFuegeEin  ( Knoten  ast ,i n twert ) {
    if( wert<ast.inhalt ) {
        if(ast.links ==null)
            ast.links =newKnoten(wert);
        else rekFuegeEin (ast.links,wert);
        }
    else {
        if(ast.rechts==null)
            ast.rechts=newKnoten(wert);
        else rekFuegeEin(ast.rechts,wert);
        }
    }

void fuegeEin(int wert) {
    if(wurzel==null)
        wurzel=newKnoten(wert);
    else rekFuegeEin( wurzel,wert);
    }

Das geht nur leider nicht da insert einen boolean zurück gibt.
Rekursiv klappt so also nicht an dieser Stelle.
Doch Interativ bekomme ich es nicht hin. kann mir da jemand einen Tipp geben?

LG

 

[httpdigest]

Das geht nur leider nicht da insert einen boolean zurück gibt.

Warum ist das ein Problem, dass insert() ein boolean zurück gibt? Du musst einfach nur den Rückgabewert des tiefsten rekursiven Aufrufes hoch reichen.

 

[ocsme]

Also rekursiv stehe ich leider noch auf dem Schlauch.
Iterativ sollte das ganze ca. so aussehen 😀
hab es noch nicht getestet 😀

public boolean insert(Element e) {
            if(root == null) {
                root = new Node(e,null,null);
                return true;
            }
            else {
                Node h = root;
                boolean t = false;
                while(!t) {
                    if(h.value.compareTo(e) == 1)
                        if(h.right==null) {
                            h = new Node(e,null,null);
                            t = true;
                        }
                        else h = h.right;
                    else
                        if(h.value.compareTo(e) == -1)
                            if(h.left == null) {
                                h = new Node(e,null,null);
                                t = true;
                            }
                            else h = h.left;
                }
                   
            }
            return false;          
        }

War nur mal "schnell" hin getextet 😛 doch rekursiv verursacht bei mir noch "Hirnkurzschluss" 😀
Vielleicht komme ich ja noch dahinter 🙂


Bei der Rekusivion verstehe ich nicht wie soll ich den den ganzen Baum durchwandern ohne den Teilast mit zu geben?
Benötige ich eine zweite Methode? Wenn ja wie soll ich dann ein Boolean zurück geben?

LG

 

[Blender3D]

Es soll eine Klasse BinTree mit einer inneren Klasse Node erstellt werden. Dazu noch eine Klasse Element die Comparable<Element> implementiert.

Das hast Du meiner Meinung nach falsch gemacht.
Die Klasse Element soll keine Innere Klasse sein. Der BinTree selbst soll laut Aufgabestellung mit Objekte arbeiten, die das Interface Comparable<T> implementieren. Die Klasse Element soll eine eigenständige Klasse sein die das Interface implementiert, um den BinTree zu testen. Andernfalls würde der BinTree nur mit der Klasse Element funktionieren.

 

[ocsme]

Mhhh... das macht Sinn 🙂
Das muss ich also auch noch ändern.
Ich verstehe nur einfach nicht wie ich das ganze Rekursiv machen könnte mit public boolean insert(Element e), dort kann ich ja die weiteren Referenzen nicht mit angeben. Dachte mir auch schon ich nehm mir eine Hilfsvariable doch die würde bei jedem rekursiven Methoden aufruf ja wieder z. B. auf root stehen 🙁

Wenn nicht dann mach ich es erst einmal lauffähig ohne Rekursion. Doch bei den Datenstrukturen und vor allem bei den Bäumen finde ich das mit der Rekusion einfach netter 🙂

Danke erstmal an euch für eure Nette Hilfe 🙂 War länger nicht mehr da 🙁

 

[httpdigest]

Du musst bei der Rekursion keine weiteren Referenzen mit angeben. Du hast doch immer `this`, welches bei einem rekursiven Aufruf ja dann der nächste tiefere Knoten im Braum wäre/ist. Du rufst ja schließlich die Methode rekursiv auf dem nächsten Kindknoten auf. Somit bist du dann auch im Kontext dieses Kindknotens.

 

[ocsme]

Es klappt leider immer noch nicht.

Hier mal meine Zwei java Dateien:

public class BinTree {
    protected Node root = null;
   
   
    protected class Node {
        Element value;
        Node left, right;
       
        Node(Element value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        //    root = this;
        }
       
        public String toString() {
            return value.toString();
        }
       
        public boolean isEmpty() {
            return root==null;
        }
       
        public void inorder(Node n) {
            if (n.left != null)
                inorder(n.left);
            System.out.println(n.toString());
            if (n.right != null)
                inorder(n.right);
        }

        public boolean insert(Element e) {
            if(isEmpty()) {
                root = new Node(e,null,null);
                return true;
            }
            else {
                boolean insert = false;
                Node h = root;
                while(!insert) {
                    if(h.value.compareTo(e) < 0) {
                        if(h.left == null) {
                            h.left = new Node(e,null,null);
                            return true;
                        }
                        else h = h.left;
                    }
                        if(h.right == null) {
                            h.right = new Node(e,null,null);
                            return true;
                        }
                        else h = h.right;
                }  
            }
            return false;
        }
       
    }
}

class Element implements Comparable<Element> {
    private int value;
   
    Element(int value) {
        this.value = value;
    }
   
    public int compareTo(Element e) {
        if (this.value == e.value)
            return 0;
        return this.value <= e.value ? -1 : 1;
    }

   
    public String toString() {
        return ""+getValue();
    }
   
    public int getValue() {
        return value;
    }
   
}

Das Problem ist das ich mit der inneren und äußeren Klasse auch nicht zurecht komme.
Wie kann ich denn dem root Knoten oben sagen das h dann links oder rechts eingefügt werden soll?
Hab es im Konstruktor auskommentiert denn das stimmt auch nicht wenn ich jedesmal den new Node auf root setze. Doch dann bekomme ich wenigstens meine Knoten bei inorder wieder raus.
So wie es jetzt ist bekomme ich nur den root Knoten ausgegeben der rest Fehlt einfach 🙁

Hier die Main mit ausgabe:

public class TestBinTree {
   
    public static void main(String[] args) {
       
        Element e1 = new Element(12);
        Element e2 = new Element (3);
        Element e3 = new Element(15);
       
        BinTree bt = new BinTree();
        BinTree.Node test = new BinTree().new Node(e1,null,null);
        System.out.println(test.insert(e2));
        System.out.println(test.insert(e3));


        System.out.println("inorder");
        test.inorder(test);
       

    }

}

true
true
inorder
12


Kann mir das vielleicht jemand erklären?
Er fügt angeblich ein doch hängt den Zeiger nicht dorthin wo er hin soll.
Wenn man test.left.toString() aufruft bekommt man eine null-Pointer!

 

[httpdigest]

Deine Baumstruktur ist immer noch komplett schräg designed... Erstmal, wie @Blender3D ja schon sagte, soll Element KEINE innere Klasse sein! Es kann ein Typparameter (Generics) sein.
Desweiteren ist es total umständlich, dass Benutzer dieses Baumes die innere Node Klasse sehen und verwenden müssen. Kapsel diese besser weg. Findest du es nicht umständlich, dass du in deinem Test sowohl einen BinTree als auch einen initialen BinTree.Node erzeugen musst?
Ich würde alle Methoden, die man auf einem Baum aufrufen kann, wie etwa insert() und inorder(), auch in der Klasse des Baumes selbst (BinTree) implementieren und im Falle eines nicht-null root dann entsprechend an den Root Node delegieren. Das heißt, die eigentliche Musik spielt dann schon noch in der Node Klasse und deren Methoden, aber die Schnittstelle nach außen sind die Methoden im BinTree.

 

[ocsme]

Das verstehe ich ja alles und danke für die Tipps doch leider ist es uns so vorgegeben worden 🙁

Das Problem ist eben das ich alles in der Klasse Node zuweise und die Informtion nicht an das Datenelement des Baumes / root geht 🙁 Ich verstehe nicht wie ich das tun soll.

Wenn das keine vorgaben wären hätte ich es so gemacht wie du geschrieben hast 🙂 Doch leider dürfen wir das nicht.
Habe auch jetzt verstanden wieso wir das nicht dürfen 😀 denke das soll eine Übung sein zu Outer.inner Classes 😛
Ich sitze hier nur leider schon eine Ewigkeit dran und bekomme es nicht hin.
3DBlender hat mir gut auf die Sprünge geholfen das ganze rekursiv zu machen. Das ganze habe ich auch verstanden doch auch dort habe ich das selbe Problem das die Information in der inner Class bleibt 🙁

Danke trozdem für eure mühe 🙂

LG

 

[httpdigest]

Doch leider dürfen wir das nicht. Habe auch jetzt verstanden wieso wir das nicht dürfen 😀 denke das soll eine Übung sein zu Outer.inner Classes 😛

Ich verstehe nicht, warum das ein Widerspruch sein soll. Du hast doch dann immer noch eine äußere und eine innere Klasse: BinTree ist die äußere Klasse und Node ist die innere. Ich sehe keinen Grund (und glaube auch nicht, dass das in der Aufgabe so stand), dass Element auch noch eine weitere Klasse sein soll, die bei dir ja auch nur ein int aufnehmen kann.
Wie lautet denn ganz exakt überhaupt die Aufgabe und was ist ganz ganz exakt unveränderlich so vorgegeben?

 

[ocsme]

Aufgabenstellung:

Aufgabe 2:
Gegeben ist eine Klasse BinTree zur Repräsentation binärer Bäume:

class BinTree {

protected Node root = null;

protected class Node {

Element value;

Node left, right;

Node(Element value, Node left, Node right) { ... }

public String toString() { ... }

}

public boolean isEmpty() { ... }

public void inorder( Node n ) { ... }

}

class Element implements Comparable<Element> {

private int value;

Element(int value) { ... }

public int compareTo(Element e) { ... }

public String toString() { ... }

public int getValue() { ... }

}

Implementieren Sie eine Methode public boolean insert(Element e) , die Elemente
in den Baum einfügt.
Eine Instanz e1 der Klasse Element wird als neuer Knoten im linken Teilbaum eines
bestehenden Knotens, welcher eine Instanz e2 der Klasse Element beinhaltet,
eingefügt, wenn e1.getValue() < e2.getValue() .
Im Falle von e1.getValue() > e2.getValue() wird das Element e1 im rechten
Teilbaum eingefügt. Herrscht Gleichheit, so soll die Funktion false zurückliefern.
Benutzen Sie für Ihre Implementierung das vorstehende Codefragment als
Grundlage. Testen Sie Ihr Programm in dem Sie die Werte 4, 2, 6, 8, 9, 7, 5, 3 und 1
in den Baum einfügen und danach für dessen Wurzel die Methode inorder(...)
aufrufen.

 

[temi]

Meiner Ansicht nach sollte deine main() ungefähr so aussehen:

public class TestBinTree {
  
    public static void main(String[] args) {
      
        Element e1 = new Element(12);
        Element e2 = new Element (3);
        Element e3 = new Element(15);
      
        BinTree bt = new BinTree();
        bt.insert(e1);
        bt.insert(e2);       
        bt.insert(e3);

        // ...
    }

}

 

[ocsme]

OMG!!!
Augen auf 😀 ja klar!
so geht es jetzt auch! 😛

Jetzt könnte ich aber echt abkotzen ich sitze an dem "misst" jetzt schon 3 Tage immer ein paar Stunden 🙁

Danke

LG

 

[Blender3D]

Jetzt könnte ich aber echt abkotzen ich sitze an dem "misst" jetzt schon 3 Tage immer ein paar Stunden 🙁

Wenn das AHA - Erlebnis da ist, dann waren die Stunden nicht umsonst. Das sind wichtige Grundlagen, die es hier zu erlernen gilt.
😉