Problème de type d'arborescence de recherche binaire générique Java
-
03-07-2019 - |
Question
Je travaille sur ce devoir qui me déroute un peu ...
On me fournit la classe BinarySearchTree suivante
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);
}
}
============================================ =====================================
Maintenant, j'ai une autre classe étudiant .... Je souhaite créer un arbre de recherche binaire d'objets Student.
BinarySearchTree<Student> tree = new BinarySearchTree<Student>();
Cependant, lorsque je le fais, le message d'erreur suivant s'affiche:
Discordance liée: le type Student n'est pas un substitut valide du paramètre lié > de type BinarySearchTree
Toute idée de ce qui se passe ici ... Je ne peux pas le comprendre.
La solution
public class BinarySearchTree<T extends Comparable<T>>
Un argument générique formel, dans votre cas, T, répertorie ce qui est requis pour qu'une classe soit un T. valide. Dans votre cas, vous avez dit, & "pour être un T valide, une classe doit implémenter Comparable. " (Le mot clé est & "; Étend &"; Mais, dans la pratique, cela signifie & "; Étend ou implémente &";).)
Dans votre instanciation, T est étudiant. Si nous substituons Student à T:
public class BinarySearchTree<Student extends Comparable<Student>>
est-ce une affirmation vraie? Student met-il vraiment en œuvre Comparable?
Si c'est le cas, Student répond à l'exigence d'être un T et vous pouvez donc utiliser Student comme paramètre effectif pour le paramètre formel T.
Sinon, vous recevez la plainte du compilateur que vous avez vue.
En fait, pour couvrir des situations plus complexes où la mise en œuvre de Comparable par une sous-classe est effectuée par une super-classe, la forme la plus générale serait:
public class BinarySearchTree<T extends Comparable<? super T > >
Il faut donc que Student implémente Comparable < Étudiant & Gt ;.
Notez que je n'ai pas dit que le compilateur recherche un Student.compareTo
. Cela ne va même pas si loin. Il cherche à voir si T (dans votre cas, Student) est déclaré comme implémentant Comparable & Lt; T & Gt; (dans votre cas, Comparable < Étudiant >).
Ajouter maintenant implements Comparable< Student >
à Student permettra également au compilateur de s’assurer qu’il existe une méthode public int compareTo
sur Student. Mais sans & "; Implémente Comparable &" ;,, même si le compilateur sait qu’il existe une méthode compareTo
, il ne sait pas que Comparable.compareTo
est la <=>.
(En d'autres termes, nous recherchons une implémentation déclarée, pas seulement une méthode portant le nom et la signature appropriés.)
Autres conseils
La classe Student implémente-t-elle Comparable?
mais je ne sais pas trop comment implémenter la méthode compareTo.
En gros, cela ressemble à ce qui suit. Vous devez décider comment fonctionne la commande.
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
}
}