无法强制转换为java.lang.Comparable

Question

虽然这个问题已经被问过，但我有一个实现上的疑问。

我正在尝试打印二叉树的顶部视图，以下是完整的代码：

import java.util.*;

class Node{
    int data;
    Node right;
    Node left;
    Node(int data){
        this.data = data;
    }
}

class Pair<F,S>{
    private F first;
    private S second;
    public Pair(F first, S second){
        this.first = first;
        this.second = second;
    }
    
    public F getFirst(){return first;}
    public S getSecond(){return second;}
}

class BinaryTreeTopView{

    public static void printTopView(Node root){

        if(root == null)
            return;

    Queue <Pair<Node,Integer>> q = new Queue<>();
    Map <Integer,Node> map = new HashMap<>();
    Pair<Node,Integer> p = new Pair<>(root, 0);
    q.add(p);
    
    /*
    I am storing nodes and the corresponding horizontal distances 
    in the form of a pair which then are being stored in the queue
    to ensure level order traversal
    */

    while(!q.isEmpty()){
        Pair<Node,Integer> temp = q.peek();
        q.remove();

        if(map.containsKey(temp.getSecond())==true){
            map.put(temp.getSecond(),temp.getFirst());
        } else {
            System.out.println(temp.getFirst().data);
            map.put(temp.getSecond(),temp.getFirst());                
        }

        if(temp.getFirst().left!=null){
            Pair<Node,Integer> left = new Pair<>(temp.getFirst().left, temp.getSecond()-1);
            q.add(left);
        }
        
        if(temp.getFirst().right!=null){
            Pair<Node,Integer> right = new Pair<> (temp.getFirst().right, temp.getSecond()+1);
            q.add(right);
        }
        
    }
}
public static void main(String[] args) {
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.right = new Node(5);
    root.left.left = new Node(4);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
    root.right.left.right = new Node(8);
    root.right.right.left = new Node(10);
    root.right.right.right = new Node(9);
    root.right.right.left.right = new Node(11);
    root.right.right.left.right.right = new Node(12);
    
    printTopView(root);
}
}

编译通过，但在运行时引发了异常。现在我一直收到以下异常，但我无法弄清楚问题所在：

Exception in thread "main" java.lang.ClassCastException: 
Pair cannot be cast to java.lang.Comparable at  java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:652)
at java.util.PriorityQueue.siftUp(PriorityQueue.java:647)
at java.util.PriorityQueue.offer(PriorityQueue.java:344)
at java.util.PriorityQueue.add(PriorityQueue.java:321)

- pkenil96

---

完整的堆栈跟踪是什么？即它对应于您的代码中的哪一行？ - Oliver Charlesworth

另外，我不相信这是您的真实代码，因为new Queue<>()无法编译。 - Oliver Charlesworth

@OliverCharlesworth..哦，我很抱歉...但这是我的代码...我实际上发布了未编辑的代码...当然它无法编译...但我实际编译的那个有PriorityQueue... 所以... 无论如何，谢谢你指出来！ - pkenil96

Answer 1

这是因为Pair没有实现Comparable接口。要么实现它：

public class Pair implements Comparable<Pair> {
    public int compareTo(Pair o) {
        // ...
    }
}

或者在你的优先队列中使用比较器

使用比较器;

PriorityQueue<DummyObject> pq = new
             PriorityQueue<DummyObject>(5, new DummyObjectComparator());

定义你的比较器：

class DummyObjectComparator implements Comparator<DummyObject>{

      // Overriding compare()method of Comparator 

       public int compare(DummyObject s1, DummyObject s2) {
                   //some code
       }
 }

- gati sahu

---

好的，运行成功了！非常感谢你的回答！但是我还不清楚为什么需要实现Comparable接口并重写compareTo方法！ - pkenil96

从错误信息来看，似乎您正在使用优先队列。如果您使用此类，请使用Comparable或Comparator来比较两个元素。 - gati sahu

是的，但是如果我不使用比较器，那么使用它的必要性在哪里呢？我只是将对象存储在队列中，这有什么影响吗？ - pkenil96

你能举个“在优先队列中使用比较器”的例子吗？ - alhelal

Answer 2

您正在尝试将Pair实例添加到PriorityQueue中，因此您的Pair类必须是Comparable。一个合理的实现方式是强制F和S本身就是Comparable，然后按第一个元素和第二个元素进行比较：

class Pair<F extends Comparable<F>, S extends Comparable<S>>
    implements Comparable<Pair<F, S>> {

    // All the code you already have is fine

    @Override
    public int compareTo(Pair<F, S> o) {
        int retVal = getFirst().compareTo(o.getFirst());
        if (retVal != 0) {
            return retVal;
        }
        return getSecond().compareTo(o.getSecond());
    }
}

- Mureinik

---

好的，但我仍然有一个疑问。我的方法没有在任何地方进行比较，那么为什么我需要比较o.first和o.second呢？ - pkenil96

PriorityQueue按照元素的自然顺序（即排序）对其进行排序。为了实现这一点，元素必须是可比较的。 - Mureinik

Answer 3

您的声明：

Queue <Pair<Node,Integer>> q = new Queue<>();

无法编译，因为Queue是一个接口，无法实例化。我怀疑你使用了一个PriorityQueue。

你真的需要一个优先队列吗？还是一个简单的LinkedList也可以适合你的算法？

更新：

顺便说一下，如果使用LinkedList，输出结果将会是：

1 2 3 4 7 9

- Maurice Perry