Binären Bäume für beliebige Datentypen

[Louis12]

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

/**
*
*/
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;
    }

}

/**
*
*/
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]

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]

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]

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) {

/**
*
*/
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;
    }

   
    }

**
*
*/
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]

Genau deshalb sagte ich ja, dass du nochmal den Sinn vom Comparable Interface untersuchen sollst, und nochmal überlegen sollst/musst, wo du es eigentlich genau einsetzen musst, um was genau zu erreichen.
Kleiner Tipp: So, wie du es aktuell verwendest, ist es falsch.
Und nein, du sollst keine Wrapper-Klassen verwenden.
Vielleicht liest du dir erstmal das hier durch: https://docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html

 

[httpdigest]

Weiterer Tipp:

// 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]

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]

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

/**
*
*/
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;
    }

}

**
*
*/
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]

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]

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

/**
*
*/
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;
        }
    }

}

/**
*
*/
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;
    }

}

 

[Xyz1]

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]

Ist alles in Ordnung. Allerdings kann man das noch etwas aufhübschen und vereinfachen:

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]

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:

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]

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

package de.tuberlin.mcc.prog1winf.datastructures;

public enum Traversal  {
   
    PREORDER , INORDER , POSTORDER;
   
   

   

   
   
}

/**
*
*/
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;
       
    }

 

[Xyz1]

Kannst bitte sagen, was hier nicht stimmt

das hat httpdigest schon....

 

[mihe7]

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

Letzteres:

Ergänzen Sie anschließend die Klasse BTree um einen mit diesem Enum parametrisierten Konstruktor