ne peut pas convertir en java.lang.Comparable

Question

Bien que cette question a déjà été posée, mais j'ai un doute spécifique à l'implémentation.

Je suis en train d'imprimer la vue de dessus de l'arbre binaire et qui suit est le code complet pour elle:

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

Il compile bien, mais une exception est soulevée à l'exécution. Maintenant, je reçois des l'exception suivante et je suis incapable de comprendre ce que le problème est:

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

C'est parce que paire n'applique pas Comparable. Soit mettre en œuvre:

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

Ou utilisez dans votre file d'attente Comparator prioritaire

Answer 2

Vous essayez d'ajouter Pair cas à un PriorityQueue, de sorte que votre classe Pair doit être Comparable. Une mise en œuvre raisonnable pourrait être de forcer F et S être Comparable sur leur droite, puis comparer le premier élément, puis le second:

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