Java通用二进制搜索树类型问题

Question

我正在做这个让我困惑的作业......

我提供了以下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);
    }
}

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

现在我有另一个班级学生....我想创建一个学生对象的二叉搜索树.

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

但是,当我这样做时,我收到以下错误:

绑定不匹配:类型Student不是BinarySearchTree类型的有界参数>的有效替代

任何想法在这里发生了什么......我无法弄明白.

Answer 1

 public class BinarySearchTree<T extends Comparable<T>> 

一个正式的泛型参数,在你的情况T中,列出了一个类成为有效T所需的内容.在你的情况下,你已经说过,"要成为有效的T,一个类必须实现Comparable"(关键字是"extends" ",但在实践中,这意味着"扩展或实施".)

在你的实例化中,T是学生.如果我们用学生代替T:

public class BinarySearchTree<Student extends Comparable<Student>>

这是一个真实的陈述吗？学生真的实施可比较吗？

如果是这样,Student符合T的要求,因此您可以使用Student作为形式参数T的实际参数.

如果没有,您会看到编译器的投诉.

实际上,为了覆盖更复杂的情况,其中子类的Comparable实现是由超类完成的,更通用的形式是:

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

因此,您需要让Student实现Comparable <Student>.

请注意,我没有说编译器正在寻找一个Student.compareTo.它甚至没有那么远.它正在查看T(在您的情况下,Student)是否被声明为实现Comparable <T>(在您的情况下,Comparable <Student>).

现在加入implements Comparable< Student >到学生将也使编译器确保有一个public int compareTo对学生的方法.但是如果没有"implements Comparable",即使编译器知道有一个方法Student.compareTo,它也不知道那compareTo是什么Comparable.compareTo.

(换句话说,我们正在寻找声明的实现,而不仅仅是恰好有一个具有正确名称和签名的方法.)