Binären Bäume für beliebige Datentypen

Louis12

Aktives Mitglied
Hallo Java Community,

Könnt ihr bitte meine Fragen Beantworten zu folgender Aufgabenstellung

In dieser Aufgabe sollen Sie einen binären Baum für beliebige Datentypen implementieren. Legen Sie sich dazu zunächst ein neues Eclipse-Projekt mit dem Namen „Aufgabe 9 - GenericBinTree“ an

Die Aufagbe:

Aufgabe 9.1 – BTreeNode und BTree Kopieren Sie die Klassen BTreeNode und BTree aus den Unterverzeichnissen von https://github.com/dbermbach/prog1winf-examples-ws1819. Diese Klassen implementieren einen binären Baum für den Datentyp int. Stellen Sie beide Klassen so um, dass im Baum beliebige Datentypen abgelegt werden können. Nutzen Sie dafür Java Generics und das Interface Comparable.


Das Interface Comparable hilft durch das vergleichen, dass eine Liste sortiert werden kann, wie funktionieren dann die Ablage mehrerer Datentypen damit? . Ich habe es zumindest folgendermaßen versucht






Mein Code
Code:
/**
*
*/
package de.tuberlin.mcc.prog1winf.datastructures;

/**
* @author Dave
* @param <T>
*
*/
public class BTree<T> implements Comparable<T> {

    private BTreeNode root;

    public void insert(int value){
        if(root==null){
            this.root = new BTreeNode(value);
            return;
        }
        insert(root,value);
    }
   
    private void insert(BTreeNode node, int value) {
        if (node.value > value) {
            // links
            if (node.left == null) {
                // hier einfuegen
                node.left = new BTreeNode(value);
                return;
            } else {
                // an Kindknoten delegieren
                insert(node.left, value);
            }

        } else if (node.value < value) {
            // rechts
            if (node.right == null) {
                node.right = new BTreeNode(value);
                return;
            } else {
                insert(node.right, value);
            }
        } else {
            return;
        }
    }

    @Override
    public int compareTo(T o) {
        // TODO Auto-generated method stub
        return 0;
    }

}

Code:
/**
*
*/
package de.tuberlin.mcc.prog1winf.datastructures;

/**
* @author Dave
* @param <T>
*
*/
public class BTreeNode<T> implements Comparable<T>   {

    public int value;

    public BTreeNode left;

    public BTreeNode right;

    /**
     * @param value
     */
    public BTreeNode(int value) {
        super();
        this.value = value;
    }

    @Override
    public int compareTo(T  o) {
        // TODO Auto-generated method stub
        return 0;
    }

}

Lg
Louis
 

httpdigest

Top Contributor
Wie die Aufgabenstellung bereits beschreibt, ist die Idee der Aufgabe, dass eben nicht int sondern Werte beliebiger Datentypen im Baum gespeichert können sollen. Dann kannst du offensichtlich eben nicht int als value-Typ und als Konstruktorparametertyp, sowie als Parametertyp für insert, etc. verwenden...
 

httpdigest

Top Contributor
Außerdem überlege nochmal, warum man das `Comparable<T>` Interface eigentlich haben will und was du genau damit vergleichen willst... Schau zum Beispiel mal in der Methode `BTree.insert(BTreeNode, int)`. Dort sind ja größer-als bzw. kleiner-als Vergleiche auf aktuell Werten des Datentyps `int`. Jetzt willst du aber eben nicht mehr `int` Werte im Knoten speichern, sondern Werte eines beliebigen Typs. Das heißt, du kannst nicht mehr einfach den kleiner-als bzw. größer-als Operator verwenden, sondern musst jetzt was tun...?
 

Louis12

Aktives Mitglied
Wie die Aufgabenstellung bereits beschreibt, ist die Idee der Aufgabe, dass eben nicht int sondern Werte beliebiger Datentypen im Baum gespeichert können sollen. Dann kannst du offensichtlich eben nicht int als value-Typ und als Konstruktorparametertyp, sowie als Parametertyp für insert, etc. verwenden...


Aso Danke für die Antwort jetzt habe, ich es verstanden.

Es gibt trotzdem 2 Compiler Fehler da ja Generics kein Int wert ist, soll ich dementsprechen dann wrapper klassen benutzen ?, wenn ja frage ich mich, ob das richtig ist, denn in der Aufgaben Stellung ist das ja nicht vorhanden.

Die Compiler Fehler:

if (node.value > value) {

else if (node.value < value) {

Code:
/**
*
*/
package de.tuberlin.mcc.prog1winf.datastructures;

/**
* @author Dave
* @param <T>
*
*/
public class BTreeNode<T> implements Comparable<T>   {

    public T value;

    public BTreeNode left;

    public BTreeNode right;

    /**
     * @param value
     */
    public BTreeNode(T value) {
        super();
        this.value = value;
    }

    @Override
    public int compareTo(T o) {
        // TODO Auto-generated method stub
        return 0;
    }

   
    }


Code:
**
*
*/
package de.tuberlin.mcc.prog1winf.datastructures;

/**
* @author Dave
* @param <T>
*
*/
public class BTree <T> implements Comparable<T> {

    private BTreeNode root;

    public void insert( T value){
        if(root==null){
            this.root = new BTreeNode(value);
            return;
        }
        insert(root,value);
    }
   
    private void insert(BTreeNode node, T value) {
        if (node.value > value) {
            // links
            if (node.left == null) {
                // hier einfuegen
                node.left = new BTreeNode(value);
                return;
            } else {
                // an Kindknoten delegieren
                insert(node.left, value);
            }

        } else if (node.value < value) {
            // rechts
            if (node.right == null) {
                node.right = new BTreeNode(value);
                return;
            } else {
                insert(node.right, value);
            }
        } else {
            return;
        }
    }

    @Override
    public int compareTo(T o) {
        // TODO Auto-generated method stub
        return 0;
    }

}
 

httpdigest

Top Contributor
Weiterer Tipp:
Java:
// Mit primitiven Datentypen, für die Operatoren definiert sind:
int a = ...;
int b = ...;
boolean lessThan = a < b;

// Nun mit Datentypen, für die keine solche Operatoren definiert sind:
Comparable<T> a = ...;
T b = ...;
boolean lessThan = a.compareTo(b) < 0;
 

httpdigest

Top Contributor
Nächster Tipp: Das, was du nutzen musst, trägt in der Typtheorie den Begriff "F-bounded polymorphism" (oder "F-bounded quantification").
Siehe hier: https://en.wikipedia.org/wiki/Bounded_quantification#F-bounded_quantification
Da ist sogar ein schönes Beispiel mit genau dem Comparable<T> Interface. Interessant für dich ist die `Fmin` Methode. Nur, dass du die Typquantifizierung eben nicht an die Methode schreibst, sondern an deine Klasse.
Du willst ja schließlich ausdrücken, dass die Werte, die du in den Baum einfügst, eben eine Möglichkeit besitzen, sich zu vergleichen, um eine Ordnung auf den Werten zu haben. Und das wiederum brauchst du ja, damit der Binärbaum weiß, ob nun im linken oder rechten Teilbaum eingefügt werden soll.
 

Louis12

Aktives Mitglied
Hallo,
danke für die Tipps erstmal. Bin auf jeden Fall weiter gekommen, aber es scheint trotzdem nicht genau richtig zu sein.

Hier erstmal der Code

Code:
/**
*
*/
package de.tuberlin.mcc.prog1winf.datastructures;

/**
* @author Dave
* @param <T>
*
*/
public class BTree <T>  {

    private  BTreeNode <T>  root;

    public void insert( T value){
        if(root==null){
            this.root = new BTreeNode<T>(value);
            return;
        }
        insert(root,value);
    }
   
    private void insert ( BTreeNode <T> node, T value) {
        if (node.value.compareTo(value) <0) {
            // links
            if (node.left == null) {
                // hier einfuegen
                node.left = new BTreeNode <T>(value);
                return;
            } else {
                // an Kindknoten delegieren
                insert(node.left, value);
            }

        } else if (node.value.compareTo(value) < 0) {
            // rechts
            if (node.right == null) {
                node.right = new BTreeNode <T>(value);
                return;
            } else {
                insert(node.right, value);
            }
        } else {
            return;
        }
    }

    public int compareTo(T o) {
        // TODO Auto-generated method stub
        return 0;
    }

}



Code:
**
*
*/
package de.tuberlin.mcc.prog1winf.datastructures;

/**
* @author Dave
* @param <T>
*
*/
public class BTreeNode<T extends Comparable<T>>   {

    public T value;

    public BTreeNode<T> left;

    public BTreeNode<T> right;

    /**
     * @param value
     */
    public BTreeNode(T value/*,BTreeNode<T> left,BTreeNode<T> right*/) {
        super();
        this.value = value;
//        this.left = left;                                       // soll ich das ebenfalls hinzufügen ?
//        this.right = right;
    }

    public int compareTo(T o) {
        // TODO Auto-generated method stub
        return 0;
    }

   
    }



lG
 

httpdigest

Top Contributor
Du hast die <T extends Comparable<T>> Quantifizierung ja genau an die Klasse geklebt, die es gerade nicht braucht. Du brauchst doch die Zusicherung, dass T ein Comparable<T> ist, dort, wo du halt compareTo auf einem T aufrufst...
Und nimm die überflüssigen compareTo()-Methodenimplementierungen raus.
 

Louis12

Aktives Mitglied
Danke für die Antwort !!. Habe das jetzt ausgebessert ist das jetzt in Ordnung ?

Code:
/**
*
*/
package de.tuberlin.mcc.prog1winf.datastructures;

/**
* @author Dave
* @param <T>
*
*/
public class BTree<T extends Comparable<T>> {

    private BTreeNode<T> root;

    public void insert(T value) {
        if (root == null) {
            this.root = new BTreeNode<T>(value);
            return;
        }
        insert(root, value);
    }

    private void insert(BTreeNode<T> node, T value) {
        if (node.value.compareTo(value) < 0) {
            // links
            if (node.left == null) {
                // hier einfuegen
                node.left = new BTreeNode<T>(value);
                return;
            } else {
                // an Kindknoten delegieren
                insert(node.left, value);
            }

        } else if (node.value.compareTo(value) < 0) {
            // rechts
            if (node.right == null) {
                node.right = new BTreeNode<T>(value);
                return;
            } else {
                insert(node.right, value);
            }
        } else {
            return;
        }
    }

}



Code:
/**
*
*/
package de.tuberlin.mcc.prog1winf.datastructures;

/**
*
*
*
* @author Dave
* @param <T>
*
*/
public class BTreeNode<T> {

    public T value;

    public BTreeNode<T> left;

    public BTreeNode<T> right;

    /**
     * @param value
     */
    public BTreeNode(T value/* ,BTreeNode<T> left,BTreeNode<T> right */) {
        super();
        this.value = value;
//        this.left = left;
//        this.right = right;
    }

}
 
X

Xyz1

Gast
if (node.value.compareTo(value) < 0) {
// links
if (node.left == null) {
// hier einfuegen
node.left = new BTreeNode<T>(value);
return;
} else {
// an Kindknoten delegieren
insert(node.left, value);
}

} else if (node.value.compareTo(value) < 0) {
// rechts
if (node.right == null) {
node.right = new BTreeNode<T>(value);
return;
} else {
insert(node.right, value);
}
} else {
return;
}
da stimmt noch etwas nicht....
 

httpdigest

Top Contributor
Ist alles in Ordnung. Allerdings kann man das noch etwas aufhübschen und vereinfachen:
Java:
public class BTreeNode<T> {
  public T value;
  public BTreeNode<T> left;
  public BTreeNode<T> right;
  public BTreeNode(T value) {
    this.value = value;
  }
}

public class BTree<T extends Comparable<T>> {
  private BTreeNode<T> root;
  public void insert(T value) {
    root = newOrInsert(root, value);
  }
  private void insertLeftOrRight(BTreeNode<T> node, T value) {
    if (node.value.compareTo(value) > 0)
      node.left = newOrInsert(node.left, value);
    else if (node.value.compareTo(value) < 0)
      node.right = newOrInsert(node.right, value);
  }
  private BTreeNode<T> newOrInsert(BTreeNode<T> node, T value) {
    if (node == null)
      return new BTreeNode<>(value);
    insertLeftOrRight(node, value);
    return node;
  }
}
 

Louis12

Aktives Mitglied
da stimmt noch etwas nicht....
Kannst bitte sagen, was hier nicht stimmt :) ?



Ist alles in Ordnung. Allerdings kann man das noch etwas aufhübschen und vereinfachen:
Java:
public class BTreeNode<T> {
  public T value;
  public BTreeNode<T> left;
  public BTreeNode<T> right;
  public BTreeNode(T value) {
    this.value = value;
  }
}

public class BTree<T extends Comparable<T>> {
  private BTreeNode<T> root;
  public void insert(T value) {
    root = newOrInsert(root, value);
  }
  private void insertLeftOrRight(BTreeNode<T> node, T value) {
    if (node.value.compareTo(value) > 0)
      node.left = newOrInsert(node.left, value);
    else if (node.value.compareTo(value) < 0)
      node.right = newOrInsert(node.right, value);
  }
  private BTreeNode<T> newOrInsert(BTreeNode<T> node, T value) {
    if (node == null)
      return new BTreeNode<>(value);
    insertLeftOrRight(node, value);
    return node;
  }
}


Jo Danke sieht wirklich so besser aus :).
 

Louis12

Aktives Mitglied
Jo ich habe weiter mit den Aufgaben gemacht, weshalb ich fragen wollte, ob mir jemand mir bei diesem Teil mir helfen kann.


Fügen Sie dem Projekt das Enum Traversal mit den Werten PREORDER, INORDER und POSTORDER hinzu. Ergänzen Sie anschließend die Klasse BTree um einen mit diesem Enum parametrisierten Konstruktor und speichern Sie den übergebenen Wert in einem Attribut traversal. Überschreiben Sie letztlich die toString()-Methode der Klasse BTree: Je nachdem, mit welchem Wert das Attribut traversal belegt ist, soll die toString()- Methode den Baum in entsprechender Reihenfolge ausgeben.





Soll ich den Konstruktor in das Enum oder in die Klasse BTree einfügen ?


Hier mein Code
Code:
package de.tuberlin.mcc.prog1winf.datastructures;

public enum Traversal  {
   
    PREORDER , INORDER , POSTORDER;
   
   

   

   
   
}

Code:
/**
*
*/
package de.tuberlin.mcc.prog1winf.datastructures;

/**
* @author Dave
* @param <T>
*
*/
public class BTree<T extends Comparable<T>> {

    private BTreeNode<T> root;

    public void insert(T value) {
        if (root == null) {
            this.root = new BTreeNode<T>(value);
            return;
        }
        insert(root, value);
    }

    private void insert(BTreeNode<T> node, T value) {
        if (node.value.compareTo(value) < 0) {
            // links
            if (node.left == null) {
                // hier einfuegen
                node.left = new BTreeNode<T>(value);
                return;
            } else {
                // an Kindknoten delegieren
                insert(node.left, value);
            }

        } else if (node.value.compareTo(value) < 0) {
            // rechts
            if (node.right == null) {
                node.right = new BTreeNode<T>(value);
                return;
            } else {
                insert(node.right, value);
            }
        } else {
            return;
        }
    }
   
    private  void Traversal (BTreeNode root) {
        this.root=root;
       
    }
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Binären Baum Kinder setzen Java Basics - Anfänger-Themen 12
U Input/Output Elemente eines Binären Suchbaums ausgeben Java Basics - Anfänger-Themen 10
C Methoden Methode zu einem Binären Suchbaum Java Basics - Anfänger-Themen 8
L Indorder Traversierung eines binären Suchbaumes Java Basics - Anfänger-Themen 1
T Rekursiv Tiefe eines binären Suchbaums ermitteln Java Basics - Anfänger-Themen 22
T Algorithmus zur Überprüfung eines binären Suchbaums Java Basics - Anfänger-Themen 2
N Binären Suchbaum erstellen, nachzuvollziehen Java Basics - Anfänger-Themen 0
W binären Suchbaum Kantenanzahl Java Basics - Anfänger-Themen 3
K Datentypen Umwandlung einer Textfeldeingabe in einen binären Wert Java Basics - Anfänger-Themen 2
J Ebene eines binären Baumes Java Basics - Anfänger-Themen 3
N Tiefe im binären Suchbaum Java Basics - Anfänger-Themen 9
A OOP Binären Datenstrom in Datei schreiben Java Basics - Anfänger-Themen 4
E Alternativen zur binären Serialisierung ? Java Basics - Anfänger-Themen 9
N Rekursive Berechnung der Höhe eines binären Baumes Java Basics - Anfänger-Themen 4
G Pfadlänge eines binären Suchbaums Java Basics - Anfänger-Themen 4
H Tiefensuche im binären Baum Java Basics - Anfänger-Themen 2
G suchen und ersetzen in einer binären Datei Java Basics - Anfänger-Themen 4
H Löschen in einem binären Baum führt zu einem StackOverflow Java Basics - Anfänger-Themen 2
L Binären Baum speichern Java Basics - Anfänger-Themen 6
J String in binären Baum umwandeln Java Basics - Anfänger-Themen 7
P Bäume Java Basics - Anfänger-Themen 13
Cassy3 Binäre Bäume Rekursiv durchlaufen und bestimmte Elemente Zählen Java Basics - Anfänger-Themen 6
E Bäume/ allgemeine Fragen Java Basics - Anfänger-Themen 21
G Rot-Schwarz-Bäume Java Java Basics - Anfänger-Themen 10
M Rot Schwarz Bäume, ausführen? Java Basics - Anfänger-Themen 6
B Theorie Rot-Schwarz-Bäume Java Basics - Anfänger-Themen 2
D Klausur Vorbereitung: Listen, Rekursion, Bäume & Vererbung Java Basics - Anfänger-Themen 3
M Bäume und Listener Java Basics - Anfänger-Themen 2
L 2-3-4 Bäume Konstruktor Java Basics - Anfänger-Themen 2
E Binäre Bäume Java Basics - Anfänger-Themen 7
W Bäume - containsValueRec Java Basics - Anfänger-Themen 2
R Crashkurs Listen / Bäume Java Basics - Anfänger-Themen 10
J bäume Java Basics - Anfänger-Themen 5
C Bäume in Java. Knoten in Array speichern Java Basics - Anfänger-Themen 3
C Bäume in Java. Code funktioniert nicht Java Basics - Anfänger-Themen 12
G Tertiäre Bäume Java Basics - Anfänger-Themen 2
G Bäume implementieren Java Basics - Anfänger-Themen 7
F Bäume in Java Java Basics - Anfänger-Themen 4
F Bäume zeichnen Java Basics - Anfänger-Themen 5
D n-näre Bäume (DOM) durchsuchen Java Basics - Anfänger-Themen 4
G Frage zur Bäume ? Java Basics - Anfänger-Themen 3
L [Aufgabe] Huffman Bäume Java Basics - Anfänger-Themen 10
Kerstininer Vererbung Hilfe beim lernen von Objektorientierung für eine Klausur Java Basics - Anfänger-Themen 10
Sniper1000 Java 391 für Windows Java Basics - Anfänger-Themen 37
P Wieso kann ich als Index für einen Array einen Char angeben? Java Basics - Anfänger-Themen 3
benny1993 Java Programm erstellen für ein Fußball-Turnier Java Basics - Anfänger-Themen 3
V Durchschnittliche Volatility in Prozent für 4 Stunden berechnen Java Basics - Anfänger-Themen 14
P Welches SDK für das erstellen einer ausführbaren Datei? Java Basics - Anfänger-Themen 4
C negamax-Algorithmus für Tic-Tac-Toe spielt manchmal falsch Java Basics - Anfänger-Themen 10
D Apache HTTPClient für alle Fälle Java Basics - Anfänger-Themen 41
J Layout Manager, welcher ist der Richtige für mein Program? Java Basics - Anfänger-Themen 1
J Fehlermeldung unverständlich für Jakarta Java Basics - Anfänger-Themen 17
M Minimax-Algorithmus für Vier gewinnt Java Basics - Anfänger-Themen 11
M GUI für Vier-Gewinnt. Java Basics - Anfänger-Themen 4
I JPA Query für mehrere Klassen Java Basics - Anfänger-Themen 3
D Quellcode für cmd funktioniert nicht Java Basics - Anfänger-Themen 9
R Operatoren Rechenoperation in Java verwenden für Calculator Java Basics - Anfänger-Themen 2
R Operatoren Rechenoperation verwenden für Taschenrechner. Java Basics - Anfänger-Themen 32
Ostkreuz Counter für Booleanwerte Java Basics - Anfänger-Themen 8
B Regex Ausdrücke für Monate Java Basics - Anfänger-Themen 7
I BlueJ Queue Frage für Klausur Java Basics - Anfänger-Themen 2
K loop pausieren für eine bestimmte Anzahl? Java Basics - Anfänger-Themen 1
Jxhnny.lpz Randomisier für Buttons Java Basics - Anfänger-Themen 13
W Intuitive interface für Komponenten Java Basics - Anfänger-Themen 4
M "Class<T> clazz" im Constructor - auch für int möglich? Java Basics - Anfänger-Themen 7
B Schrankensystem mit Farberkennung für Flashgame funktioniert nicht wie geplant Java Basics - Anfänger-Themen 4
I Code für Bezahlsystem (auch bei Offline Aktivität) Java Basics - Anfänger-Themen 7
U jUnit 5 Test für eine addMethode Java Basics - Anfänger-Themen 18
M monte carlo Algorithmus für 4 gewinnt Java Basics - Anfänger-Themen 12
frager2345 Java Singleton Muster -> Methode für Konstruktor mit Parametern Java Basics - Anfänger-Themen 3
izoards Sortier Algorithmus für Bounding Box Elememte Links nach Rechts und von Oben nach Unten Java Basics - Anfänger-Themen 33
M generate Methode für Streams Java Basics - Anfänger-Themen 6
I Datenmodell für "Tags" Java Basics - Anfänger-Themen 6
Lion.King for-Kontrollstruktur für Pyramide Java Basics - Anfänger-Themen 8
B Mit Countdown Midnestdauer für Teilaufgabenerledigung erzwingen Java Basics - Anfänger-Themen 8
J File length als Prüfwert für Download Java Basics - Anfänger-Themen 5
K Spieleidee gesucht für Informatikprojekt - JAVA (BlueJ)? Java Basics - Anfänger-Themen 15
P Zähler Variable für mehrere Objekte Java Basics - Anfänger-Themen 6
javamanoman Java für Online Banking Java Basics - Anfänger-Themen 12
NadimArazi Wie kann ich eine collision detection für die Paddles in meinem Pong Programm hinzufügen? Java Basics - Anfänger-Themen 4
JordenJost Java ist auch eine Insel für Anfänger Java Basics - Anfänger-Themen 2
P9cman Tipps für Rekursive Aufgaben mit Strings oder allgemein Java Basics - Anfänger-Themen 2
F Suche nach betreuender Person für eine Jahresarbeit der 12. Klasse. Java Basics - Anfänger-Themen 6
I SQL / JPA Query für StartDate und EndDate Java Basics - Anfänger-Themen 1
T getMethode für ein Array Java Basics - Anfänger-Themen 2
Fats Waller Farben mixen für den Hintergrund ? Java Basics - Anfänger-Themen 1
H Suche jemanden für kleine Uni-Abgabe/ mit Vergütung Java Basics - Anfänger-Themen 1
K Für was braucht man die left und right shift operatoren? Was bringen die, also welchen Zweck haben die? Java Basics - Anfänger-Themen 15
N Api nur für Textdatein (.txt) Java Basics - Anfänger-Themen 2
bluetrix Programmieren eines Bots für Zahlen-Brettspiel Java Basics - Anfänger-Themen 9
M Wie kann eine Methode für ein vorhandenes "Array von char" einen Index-Wert zurückliefern? Java Basics - Anfänger-Themen 3
R Ist Java das Richtige für mich? Java Basics - Anfänger-Themen 4
E Mittelquadratmethode für Hexadezimalzahlen Java Basics - Anfänger-Themen 1
P Einfacher regulärer Ausdruck (RegEx) für E-Mail-Adressen Java Basics - Anfänger-Themen 2
Kiki01 Wie würde eine geeignete Schleife aussehen, die die relative Häufigkeit für jeden Charakter in einem Text bestimmt? Java Basics - Anfänger-Themen 3
N Fehler im Code (Aufgabe für Anfänger) Java Basics - Anfänger-Themen 11
O Wie erstelle ich eine Instanz in einer Klasse für die ich die Instanz will? Java Basics - Anfänger-Themen 4
S BubbleSort für ArrayLists Java Basics - Anfänger-Themen 3
T Übungsbuch für Anfänger Java Basics - Anfänger-Themen 3
L Konzept für Quiz Java Basics - Anfänger-Themen 33

Ähnliche Java Themen

Neue Themen


Oben