扩展可比的泛型

Question

我正在Java中开发一个基于模板的类，实现各种树结构(例如标准二叉树、红黑树或B树)。我的想法是让它像Java集合中的各种列表一样完成。这是一个接口类，然后由指定的树展开。然而，我遇到了一个奇怪的问题：

BSTree.java:12: error: BSTree is not abstract and does not override abstract method     search(Comparable) in Tree
public class BSTree<T extends Comparable<T>> extends Tree {
       ^

BSTree.java:20: error: name clash: add(T#1) in BSTree and add(T#2) in Tree have the same erasure, yet neither overrides the other
    public void add(T key) throws NullPointerException {
                ^
  where T#1,T#2 are type-variables:
    T#1 extends Comparable<T#1> declared in class BSTree
    T#2 extends Comparable<T#2> declared in class Tree

BSTree.java:28: error: method compareTo in interface Comparable<T#2> cannot be applied     to given types;
                if (key.compareTo(ptr.key) == -1) {
                   ^
  required: T#1
  found: Comparable
  reason: actual argument Comparable cannot be converted to T#1 by method invocation conversion
  where T#1,T#2 are type-variables:
    T#1 extends Comparable<T#1> declared in class BSTree
    T#2 extends Object declared in interface Comparable

BSTree.java:42: error: name clash: remove(T#1) in BSTree and remove(T#2) in Tree have the same erasure, yet neither overrides the other
    public void remove(T key) throws NullPointerException, TreeException {
                ^
  where T#1,T#2 are type-variables:
    T#1 extends Comparable<T#1> declared in class BSTree
    T#2 extends Comparable<T#2> declared in class Tree

BSTree.java:49: error: method compareTo in interface Comparable<T#2> cannot be applied     to given types;
            if (key.compareTo(ptr.key) == 0) {
                   ^
  required: T#1
  found: Comparable
  reason: actual argument Comparable cannot be converted to T#1 by method invocation conversion
  where T#1,T#2 are type-variables:
    T#1 extends Comparable<T#1> declared in class BSTree
    T#2 extends Object declared in interface Comparable

BSTree.java:81: error: method compareTo in interface Comparable<T#2> cannot be applied to given types;
            else if (key.compareTo(ptr.key) < 0) ptr = ptr.left;
                        ^
  required: T#1
  found: Comparable
  reason: actual argument Comparable cannot be converted to T#1 by method invocation conversion
  where T#1,T#2 are type-variables:
    T#1 extends Comparable<T#1> declared in class BSTree
    T#2 extends Object declared in interface Comparable

BSTree.java:89: error: name clash: search(T#1) in BSTree and search(T#2) in Tree have     the same erasure, yet neither overrides the other
    public Node<T> search(T key) throws NullPointerException, KeyNotStoredException {
                   ^
  where T#1,T#2 are type-variables:
    T#1 extends Comparable<T#1> declared in class BSTree
    T#2 extends Comparable<T#2> declared in class Tree

BSTree.java:94: error: method compareTo in interface Comparable<T#2> cannot be applied to given types;
            if (key.compareTo(ptr.key) == 0) return ptr;
                   ^
  required: T#1
  found: Comparable
  reason: actual argument Comparable cannot be converted to T#1 by method invocation conversion
  where T#1,T#2 are type-variables:
    T#1 extends Comparable<T#1> declared in class BSTree
    T#2 extends Object declared in interface Comparable

BSTree.java:95: error: method compareTo in interface Comparable<T#2> cannot be applied to given types;
            else if (key.compareTo(ptr.key) < 0) ptr = ptr.left;
                    ^
  required: T#1
  found: Comparable
  reason: actual argument Comparable cannot be converted to T#1 by method invocation conversion
  where T#1,T#2 are type-variables:
    T#1 extends Comparable<T#1> declared in class BSTree
    T#2 extends Object declared in interface Comparable

看起来Java认为对象是不同类型的..。怎么解决这个问题？

下面是我的代码：

Tree.java

class Node<T extends Comparable<T>> {

    protected T key;
    protected Node parent, left, right;

    public Node(T key, Node parent) {
        this.key = key;
        this.parent = parent;
        this.left = null;
        this.right = null;
    }

}

public abstract class Tree<T extends Comparable<T>> {
    protected Node<T> root;
protected Integer nodesCount;

    public abstract void add(T key) throws NullPointerException;

    public abstract void remove(T key) throws NullPointerException, TreeException;

    public abstract Node<T> search(T key) throws NullPointerException, KeyNotStoredException;
}

BSTree.java

public class BSTree<T extends Comparable<T>> extends Tree {

    public BSTree() {
        root = null;
        nodesCount = new Integer(0);
    }

    @Override
    public void add(T key) throws NullPointerException {
        if (root == null) root = new Node<T>(key, null);    
        else {      
            boolean left = false;
            Node ptr = root, parent = ptr.parent;
            while (ptr != null) {
                parent = ptr;
                left = false;
                if (key.compareTo(ptr.key) == -1) {
                    ptr = ptr.left;
                    left = true;
                } else ptr = ptr.right;
            }

            if (left) parent.left = new Node<T>(key, parent);
            else parent.right = new Node<T>(key, parent);
        }

        nodesCount++;
    }

    @Override
    public void remove(T key) throws NullPointerException, TreeException {
        /* implementation */
    }

    @Override
    public Node<T> search(T key) throws NullPointerException, KeyNotStoredException {
        /* implementation */
    }

}

编辑:多亏了您的建议，我能够将错误数量减少到5个。

BSTree.java:28: error: method compareTo in interface Comparable<T#2> cannot be applied to given types;
                if (key.compareTo(ptr.key) == -1) {
                       ^
  required: T#1
  found: Comparable
  reason: actual argument Comparable cannot be converted to T#1 by method invocation conversion
  where T#1,T#2 are type-variables:
    T#1 extends Comparable<T#1> declared in class BSTree
    T#2 extends Object declared in interface Comparable

BSTree.java:49: error: method compareTo in interface Comparable<T#2> cannot be applied to given types;
            if (key.compareTo(ptr.key) == 0) {
               ^
  required: T#1
  found: Comparable
  reason: actual argument Comparable cannot be converted to T#1 by method invocation conversion
  where T#1,T#2 are type-variables:
    T#1 extends Comparable<T#1> declared in class BSTree
    T#2 extends Object declared in interface Comparable

BSTree.java:81: error: method compareTo in interface Comparable<T#2> cannot be applied to given types;
            else if (key.compareTo(ptr.key) < 0) ptr = ptr.left;
                        ^
  required: T#1
  found: Comparable
  reason: actual argument Comparable cannot be converted to T#1 by method invocation     conversion
  where T#1,T#2 are type-variables:
    T#1 extends Comparable<T#1> declared in class BSTree
    T#2 extends Object declared in interface Comparable

BSTree.java:94: error: method compareTo in interface Comparable<T#2> cannot be applied to given types;
            if (key.compareTo(ptr.key) == 0) return ptr;
                   ^
  required: T#1
  found: Comparable
  reason: actual argument Comparable cannot be converted to T#1 by method invocation conversion
  where T#1,T#2 are type-variables:
    T#1 extends Comparable<T#1> declared in class BSTree
    T#2 extends Object declared in interface Comparable

BSTree.java:95: error: method compareTo in interface Comparable<T#2> cannot be applied to given types;
            else if (key.compareTo(ptr.key) < 0) ptr = ptr.left;
                        ^
  required: T#1
  found: Comparable
  reason: actual argument Comparable cannot be converted to T#1 by method invocation conversion
  where T#1,T#2 are type-variables:
    T#1 extends Comparable<T#1> declared in class BSTree
    T#2 extends Object declared in interface Comparable

现在，我的代码有它缺少的Node<T>和Tree<T>。但还有什么问题吗？

Answer 1

当您在JDK中复制功能时，您应该阅读代码以获得一些想法。

您的代码需要使用Node和Tree泛型。

 public class BSTree<T extends Comparable<T>> extends Tree<T> {

和

protected Node<T> parent, left, right;

顺便说一句:当您可以使用原语时，不应该使用包装器。

protected int nodesCount;

Answer 2

您在Tree声明中缺少了BSTree上的泛型参数：

public class BSTree<T ...> extends Tree<T>

这意味着add(T)方法在BSTree中不会覆盖Tree中的方法，因为它们没有相同的参数类型。

但是，由于T作为一个类并不比Object更精确(我们只知道它实现了Comparable接口)，所以这两种方法具有与add(Object)相同的擦除性，并且可能不兼容类型(在编译器的错误输出中识别为T#1和T#2)。

Answer 3

尝试：

public class BSTree<T extends Comparable<T>> extends Tree<T> {