Problema de tipo de árbol de búsqueda binario genérico de Java
-
03-07-2019 - |
Pregunta
Estoy trabajando en esta tarea que me confunde ...
Se me proporciona la siguiente clase 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);
}
}
=============================================== =================================
Ahora tengo otra clase Estudiante ... Quiero crear un árbol de búsqueda binaria de objetos de Alumno ...
BinarySearchTree<Student> tree = new BinarySearchTree<Student>();
Sin embargo, cuando hago eso me sale el siguiente error:
No coinciden los límites: el tipo Estudiante no es un sustituto válido para el parámetro limitado > del tipo BinarySearchTree
Alguna idea de lo que está pasando aquí ... No puedo entenderlo.
Solución
public class BinarySearchTree<T extends Comparable<T>>
Un argumento genérico formal, en su caso T, enumera lo que se requiere para que una clase sea una T. válida. En su caso, ha dicho, " para ser una T válida, una clase debe implementar Comparable " (La palabra clave es & Quot; extiende & Quot ;, pero en la práctica eso significa & Quot; extiende o implementa & Quot ;.)
En tu instanciación, T es Student. Si sustituimos Student por T:
public class BinarySearchTree<Student extends Comparable<Student>>
¿es esa una declaración verdadera? ¿El estudiante realmente implementa Comparable?
Si es así, Student cumple con el requisito de ser una T, por lo que puede utilizar Student como el parámetro real para el parámetro formal T.
Si no, obtienes la queja del compilador que viste.
En realidad, para cubrir situaciones más complicadas en las que la implementación de una subclase de Comparable es realizada por una superclase, la forma más general sería:
public class BinarySearchTree<T extends Comparable<? super T > >
Por lo tanto, debe hacer que el Estudiante implemente Comparable < Estudiante & Gt ;.
Tenga en cuenta que no dije que el compilador está buscando un Student.compareTo
. Ni siquiera llega tan lejos. Está buscando ver si T (en su caso, Student) se declara como implementando Comparable & Lt; T & Gt; (en su caso, Comparable < Student >).
Ahora agregando implements Comparable< Student >
al Estudiante también hará que el compilador se asegure de que haya un método public int compareTo
en el Estudiante. Pero sin & Quot; implementa Comparable & Quot ;, incluso si el compilador sabe que hay un método compareTo
, no sabe que Comparable.compareTo
es <=>.
(En otras palabras, estamos buscando una implementación declarada, no solo que haya un método con el nombre y la firma correctos).
Otros consejos
¿La clase Estudiante implementa Comparable?
pero no estoy muy seguro de cómo implementar el método compareTo.
Básicamente es algo como lo siguiente. Cómo funciona el pedido tiene que decidir.
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
}
}