2009-05-02 10 views
1

ich auf diesen Hausaufgaben bin arbeiten, die mir Art von verwirrend ...Java Generisches binärer Suchbaum Typ Ausgabe

ich mit der folgenden BinarySearchTree-Klasse am

import java.util.NoSuchElementException; 

/** 
* 
* @param <T> The type of data stored in the nodes of the tree, must implement Comparable<T> with the compareTo method. 
*/ 
public class BinarySearchTree<T extends Comparable<T>> { 


    BinaryTree<T> tree; 

    int size; 
    public BinarySearchTree() { 
     tree = new BinaryTree<T>(); 
     size = 0; 
    } 

    public boolean isEmpty() { 
     return tree.isEmpty(); 
    } 

    protected BinaryTree<T> recursiveSearch(BinaryTree<T> root, T key) { 
     if (root == null) { 
      return null; 
     } 
     int c = key.compareTo(root.data); 
     if (c == 0) { 
      return root; 
     } 
     if (c < 0) { 
      return recursiveSearch(root.left, key); 
     } else { 
      return recursiveSearch(root.right, key); 
     } 
    } 

    public T search(T key) { 
     if (tree.isEmpty()) { 
      return null; 
     } 
     return recursiveSearch(tree, key).data; 
    } 

    public void insert(T item) { 

     if (tree.isEmpty()) { // insert here 
      tree.makeRoot(item); 
      size++; 
      return; 
     } 

     // do an iterative descent 
     BinaryTree<T> root = tree; 
     boolean done=false; 
     BinaryTree<T> newNode = null; 
     while (!done) { 
      int c = item.compareTo(root.data); 
      if (c == 0) { // duplicate found, cannot be inserted 
       throw new OrderViolationException(); 
      } 
      if (c < 0) { // insert in left subtree 
       if (root.left == null) { // insert here as left child 
        newNode = new BinaryTree<T>(); 
        root.left = newNode; 
        done=true; 
       } else { // go further down left subtree 
        root = root.left; 
       } 
      } else { // insert in right subtree 
       if (root.right == null) { // insert here as right child 
        newNode = new BinaryTree<T>(); 
        root.right = newNode; 
        done=true; 
       } else { // go further down right subtree 
        root = root.right; 
       } 
      } 
     } 
     // set fields of new node 
     newNode.data = item; 
     newNode.parent = root; 
     size++; 
    } 

    /** 
    * @param deleteNode Node whose parent will receive new node as right or left child, 
    *     depending on whether this node is its parent's right or left child. 
    * @param attach The node to be attached to parent of deleteNode. 
    */ 
    protected void deleteHere(BinaryTree<T> deleteNode, BinaryTree<T> attach) { 

     // deleteNode has only one subtree, attach 
     BinaryTree<T> parent = deleteNode.parent; 
     deleteNode.clear(); // clear the fields 
     if (parent == null) { 
      return; 
     } 
     if (deleteNode == parent.left) { 
      // left child of parent, attach as left subtree 
      parent.detachLeft(); 
      parent.attachLeft(attach); 
      return; 
     } 
     // attach as right subtree 
     parent.detachRight(); 
     parent.attachRight(attach); 
    } 


    protected BinaryTree<T> findPredecessor(BinaryTree<T> node) { 
     if (node.left == null) { 
      return null; 
     } 
     BinaryTree<T> pred = node.left; // turn left once 
     while (pred.right != null) { // keep turning right 
      pred = pred.right; 
     } 
     return pred; 
    } 


    public T delete(T key) { 
     if (tree.isEmpty()) { // can't delete from an empty tree 
      throw new NoSuchElementException(); 
     } 

     // find node containing key 
     BinaryTree<T> deleteNode = recursiveSearch(tree, key); 
     if (deleteNode == null) { // data not found, can't delete 
      throw new NoSuchElementException(); 
     } 

     BinaryTree<T> hold; 

     // case c: deleteNode has exactly two subtrees 
     if (deleteNode.right != null && deleteNode.left != null) { 
      hold = findPredecessor(deleteNode); 
      deleteNode.data = hold.data; 
      deleteNode = hold; // fall through to case a or b 
     } 

     // case a: deleteNode is a leaf 
     if (deleteNode.left == null && deleteNode.right == null) { 
      deleteHere(deleteNode, null); 
      size--; 
      return deleteNode.data; 
     }  

     // case b: deleteNode has exactly one subtree 
     if (deleteNode.right != null) { 
      hold = deleteNode.right; 
      deleteNode.right = null; 
     } else { 
      hold = deleteNode.left; 
      deleteNode.left = null; 
     } 

     deleteHere(deleteNode,hold); 
     if (tree == deleteNode) { // root deleted 
      tree = hold; 
     } 
     size--; 
     return deleteNode.data; 
    } 


    public T minKey() { 
     if (tree.data == null) { // tree empty, can't find min value 
      throw new NoSuchElementException(); 
     } 

     BinaryTree<T> root = tree; 
     T min=root.data; 
     root = root.left; // turn left once 
     while (root != null) { // keep going left to leftmost node 
      min = root.data; 
      root = root.left; 
     } 
     return min; 
    } 


    public T maxKey() { 
     if (tree.getData() == null) { // tree empty, can't find max value 
      throw new NoSuchElementException(); 
     } 

     BinaryTree<T> root=tree; 
     T max=root.data; 
     root = root.right; // turn right once 
     while (root != null) { // keep going to rightmost node 
      max = root.data; 
      root = root.right; 
     } 
     return max; 
    } 


    public int size() { 
     return size; 
    } 


    protected void recursivePreOrder(BinaryTree<T> root, Visitor<T> visitor) { 
     if (root != null) { 
      visitor.visit(root); 
      recursivePreOrder(root.left, visitor); 
      recursivePreOrder(root.right, visitor); 
     } 
    } 


    public void preOrder(Visitor<T> visitor) { 
     if (tree.isEmpty()) { 
      return; 
     } 
     recursivePreOrder(tree, visitor); 
    } 


    protected void recursiveInOrder(BinaryTree<T> root, Visitor<T> visitor) { 
     if (root != null) { 
      recursiveInOrder(root.left, visitor); 
      visitor.visit(root); 
      recursiveInOrder(root.right, visitor); 
     } 
    } 


    public void inOrder(Visitor<T> visitor) { 
     if (tree.isEmpty()) { 
      return; 
     } 
     recursiveInOrder(tree, visitor); 
    } 


    protected void recursivePostOrder(BinaryTree<T> root, Visitor<T> visitor) { 
     if (root != null) { 
      recursivePostOrder(root.left, visitor); 
      recursivePostOrder(root.right, visitor); 
      visitor.visit(root); 
     } 
    } 

    public void postOrder(Visitor<T> visitor) { 
     if (tree.isEmpty()) { 
      return; 
     } 
     recursivePostOrder(tree, visitor); 
    } 
} 

====== ================================================= ======================

Jetzt habe ich eine andere Klasse Student .... Ich möchte eine binäre Suchbaum von Student Objekte erstellen ..

Jedoch
BinarySearchTree<Student> tree = new BinarySearchTree<Student>(); 

, wenn ich tun, dass ich die folgende Fehlermeldung erhalten:

Bound Mismatch: Der Typ: Student ist kein gültiger Ersatz für den beschränkten Parameter> des Typs BinarySearchTree

Irgendwelche Ideen, was hier passiert. .. Ich kann es nicht herausfinden.

+0

Durch die Art, wie ich empfehle, dass die „BinarySearchTree > "statt nur" BinarySearchTree > ". Die Art, wie Sie es haben, ist restriktiver als es sein muss und wird zu Problemen führen, wenn Sie Unterklassen von Klassen haben, die Comparable implementieren. – newacct

Antwort

6
public class BinarySearchTree<T extends Comparable<T>> 

Ein formales Argument Generika, in Ihrem Fall T listet, was erforderlich ist für eine Klasse einen gültigen T. In Ihrem Fall zu sein, du gesagt hast „, eine gültigen T zu sein, eine Klasse muss Comparable implementieren "(Das Schlüsselwort ist" extends ", aber in der Praxis bedeutet das" extends oder implements ").

In Ihrer Instanziierung ist T Student. Wenn wir Student für T ersetzen:

ist das eine wahre Aussage? Implementiert Student wirklich Vergleichbar?

Ist dies der Fall, Schüler passt das Erfordernis eines T zu sein, und so können Sie Schüler als eigentlicher Parameter für die formalen Parameter T.

Wenn nicht verwenden, erhalten Sie die Beschwerde der Compiler Sie sahen.

Eigentlich kompliziertere Situationen abzudecken, in denen eine Umsetzung der Unterklasse von Vergleichbar mit einer Super-Klasse getan wird, würde die allgemeinere Form:

public class BinarySearchTree<T extends Comparable<? super T > > 

So müssen Sie Studenten implementieren Comparable < Schüler> machen.

Beachten Sie, dass ich nicht sagen, dass der Compiler auf der Suche nach einem Student.compareTo. Es kommt nicht einmal so weit. Es wird geprüft, ob T (in Ihrem Fall Student) für die Implementierung von Comparable < T> (in Ihrem Fall vergleichbar < Student>) deklariert ist.

Hinzufügen Jetzt implements Comparable<Student> zum Student wird auch die Compiler machen sicherzustellen, dass eine public int compareTo Methode auf Schüler gibt.Aber ohne die "implements Comparable", auch wenn der Compiler weiß, es gibt eine Methode Student.compareTo, weiß es nicht, dass compareTo die Comparable.compareTo ist.

(Mit anderen Worten, wir sind bei deklarierten Implementierung suchen, nicht nur, dass es passiert, ein Verfahren mit dem richtigen Namen und Unterschrift.)

+0

Danke für Ihre Hilfe ... Es hat funktioniert ... Ich habe T für Student geändert, Comparable implementiert und die CompareTo-Methode hinzugefügt. – user69514

+0

Whoa - nicht ändern T für Schüler in BinarySearchTree - tpdi wollte nur sagen, was passiert, wenn Sie neue BinarySearchTree aufrufen - der Compiler wird Student für T einstecken. Ihre Deklaration sollte weiterhin öffentliche Klasse BinarySearchTree >. –

+0

Ja, Scott hat Recht. T ist das formale Argument, Student das eigentliche Argument. – tpdi

0

Führt die Klasse Student Comparable?

+0

Nein, tut es nicht .... das ist, was ich dachte, ich sollte tun, aber ich bin mir nicht ganz sicher, wie man die compareTo Methode implementiert. – user69514

+0

Wenn Sie nicht vergleichbar implementieren, erfüllen Sie nicht die Anforderungen für >. Ohne Vergleich ist eine binäre Suche bedeutungslos. –

+0

Ok ich Vergleichbar in der Schülerklasse implementiert ... meine compareTo wie folgt aussieht: \t public int compareTo (Object o) { \t \t Schüler cr = (Student) o; \t \t int cn1 = Ganzzahl.parseInt (this.id); \t \t int cn2 = Ganzzahl.parseInt (cr.id); \t \t wenn (cn1> cn2) \t \t \t zurück 1; \t \t sonst if (cn1 user69514

0

but I'm not quite sure how to implement the compareTo method.

Grundsätzlich ist es so etwas wie das Folgende. Wie die Bestellung funktioniert, müssen Sie entscheiden.

class Student implements Comparable<Student> { 

    //... 

    int compareTo(Student other) { 
     // return some negative number if this object is less than other 
     // return 0 if this object is equal to other 
     // return some positive number if this object is greater than other 
    } 
}