Problema relativo al tipo di albero di ricerca binario generico Java
-
03-07-2019 - |
Domanda
Sto lavorando a questi compiti che mi confondono ...
Mi viene fornita la seguente classe BinarySearchTree
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);
}
}
=============================================== =================================
Ora ho un altro studente di classe .... Voglio creare un albero di ricerca binario di oggetti Studente ..
BinarySearchTree<Student> tree = new BinarySearchTree<Student>();
Tuttavia quando lo faccio ottengo il seguente errore:
Mancata corrispondenza associata: il tipo Student non è un sostituto valido del parametro limitato > del tipo BinarySearchTree
Qualche idea su cosa stia succedendo qui ... Non riesco a capirlo.
Soluzione
public class BinarySearchTree<T extends Comparable<T>>
Un argomento generico di generici, nel tuo caso T, elenca ciò che è necessario affinché una classe sia un T. valido. Nel tuo caso, hai detto, " per essere un T valido, una classe deve implementare Comparable " (La parola chiave è & Quot; estende & Quot ;, ma in pratica significa & Quot; estende o implementa & Quot ;.)
Nella tua istanza, T è Studente. Se sostituiamo Student per T:
public class BinarySearchTree<Student extends Comparable<Student>>
è una vera affermazione? Student implementa davvero Comparable?
In tal caso, Student soddisfa il requisito di essere una T, quindi è possibile utilizzare Student come parametro effettivo per il parametro formale T.
In caso contrario, ricevi il reclamo del compilatore che hai visto.
In realtà, per coprire situazioni più complicate in cui l'implementazione di Comparable di una sottoclasse viene eseguita da una superclasse, la forma più generale sarebbe:
public class BinarySearchTree<T extends Comparable<? super T > >
Quindi devi rendere Student implementabile Comparable < Studente & Gt ;.
Nota che non ha detto che il compilatore sta cercando un Student.compareTo
. Non arriva nemmeno così lontano. Sta cercando di vedere se T (nel tuo caso, Studente) viene dichiarato implementando Comparable & Lt; T gt &; (nel tuo caso, Comparable < Student >).
Ora aggiungendo implements Comparable< Student >
a Student anche il compilatore si assicurerà che ci sia un metodo public int compareTo
su Student. Ma senza il & Quot; implementa Comparable & Quot ;, anche se il compilatore sa che esiste un metodo compareTo
, non sa che Comparable.compareTo
è il <=>.
(In altre parole, stiamo cercando l'implementazione dichiarata, non solo che ci sia un metodo con il nome e la firma giusti.)
Altri suggerimenti
La classe Student implementa Comparable?
ma non sono sicuro di come implementare il metodo compareTo.
Fondamentalmente è qualcosa di simile al seguente. Come funziona l'ordinamento devi decidere.
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
}
}