不能转换为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) 

Answer 1

这是因为对没有实现可比。无论是实现它：

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

或在你的优先级队列

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()); 
    } 
}