0

我目前正在为一个班级构建一棵霍夫曼树。在查看了我的可用选项后，我决定采用优先队列方法。但是，当我尝试运行以下代码时，我在 TreeNode 上（在第一 pq.offer 行）上得到一个 ClassCastException。

public static TreeNode<CharFreq> buildTree(ArrayList<TreeNode<CharFreq>> trees) throws IOException {

   PriorityQueue<TreeNode<CharFreq>> pq = new PriorityQueue<TreeNode<CharFreq>>();

   for (int i = 0; i < trees.size(); i++) {
     if (trees.get(i).getItem().getFreq() > 0) {
       pq.offer(new TreeNode<CharFreq>(new CharFreq(trees.get(i).getItem().getChar(), trees.get(i).getItem().getFreq())));
     }
   }  

   while (pq.size() > 1) {    
       TreeNode<CharFreq> leftNode = pq.poll();
       TreeNode<CharFreq> rightNode = pq.poll();
       TreeNode<CharFreq> parentNode = new TreeNode<CharFreq>(new CharFreq('\u0000', ((leftNode.getItem().getFreq()) + (rightNode.getItem().getFreq()))), leftNode, rightNode);
   }  

   return pq.poll();

}

我知道它不是一个可比较的类，但是 CharFreq 是，我的问题是我是否能够修复我的代码，从而避免这个转换问题？

4

2 回答 2

1

您可以创建自定义比较器：Comparator<TreeNode<CharFreq>>并在创建 PriorityQueue 时使用它：

http://docs.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html#PriorityQueue(int , java.util.Comparator)

创建一个具有指定初始容量的 PriorityQueue，根据指定的比较器对其元素进行排序

使用匿名类的概念，你可以有这样的代码：

public static TreeNode<CharFreq> buildTree(ArrayList<TreeNode<CharFreq>> trees)
    throws IOException {
    Comparator<TreeNode<CharFreq>> comparator = new Comparator<TreeNode<CharFreq>>() {

        //basic implementation, you must use your own!
        public int compare(TreeNode<CharFreq> node1, TreeNode<CharFreq> node2) {
            return node1.data.compareTo(node2.data);
        }
    };
    PriorityQueue<TreeNode<CharFreq>> pq = new PriorityQueue<TreeNode<CharFreq>>(10, comparator);
    //the rest of your code...
}

请注意，使用这种方式意味着您必须在Comparator<TreeNode<YourClass>>每次需要创建PriorityQueue<TreeNode<YourClass>>.

于 2012-10-10T07:17:32.623 回答
0

优先级队列使用 a Comparator（在构造函数中提供）或直接将对象转换为Comparable.

为避免 ClassCastException，您应该提供一个Comparatorof TreeNode。这样队列将使用比较器而不是强制转换。

PriorityQueue<TreeNode<CharFreq>> pq = new PriorityQueue<TreeNode<CharFreq>>(initialCapacity, comparator);
于 2012-10-10T07:11:16.180 回答