java - 扩展可比较的泛型

Question

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

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 认为该对象属于不同类型...如何解决这个问题？

这是我的代码:

树.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 个。如下: javac -d ../bin *.java

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;