我正在做这个让我有点困惑的家庭作业......
我得到了以下 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);
}
}
============================================= =================================
现在我有另一个类(class)学生.... 我想创建一个学生对象的二叉搜索树..
BinarySearchTree<Student> tree = new BinarySearchTree<Student>();
但是，当我这样做时，出现以下错误:
边界不匹配:类型 Student 不是 BinarySearchTree 类型的边界参数 > 的有效替代
知道这里发生了什么……我想不通。
最佳答案
public class BinarySearchTree<T extends Comparable<T>>
一个正式的泛型参数，在你的例子中是 T，列出了一个类成为有效 T 的要求。在你的例子中，你已经说过，“要成为一个有效的 T，一个类必须实现 Comparable”(关键字是“扩展”，但实际上意味着“扩展或实现”。)
在您的实例化中，T 是 Student。如果我们用 Student 代替 T:
public class BinarySearchTree<Student extends Comparable<Student>>
这是真的吗？ Student 真的实现了 Comparable 吗？
如果是，则Student符合作为T的条件，那么可以将Student作为形参T的实参。
如果不是，您会看到编译器的投诉。
实际上，为了涵盖更复杂的情况，即子类对 Comparable 的实现是由父类(super class)完成的，更一般的形式是:
public class BinarySearchTree<T extends Comparable<? super T > >
所以你需要让Student实现Comparable
请注意，我没有说编译器正在寻找 Student.compareTo .它甚至没有那么远。它正在查看 T(在您的情况下为 Student)是否被声明为实现 Comparable< T>(在您的情况下为 Comparable< Student >)。
现在添加implements Comparable< Student >给 Student 也让编译器确保有一个 public int compareTo学生的方法。但是如果没有“可比较的实现”，即使编译器知道有一个方法 Student.compareTo ，它不知道 compareTo是 Comparable.compareTo .
(换句话说，我们正在寻找声明的实现，而不仅仅是恰好有一个具有正确名称和签名的方法。)
关于Java通用二进制搜索树类型问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/814212/