如何用比较器实现树图？

Question

我在这个问题中遇到的错误已经解决并写在下面的答案部分。

问题是 TreeMap 的以下定义引发了编译器错误，我想知道原因。

Comparator<Student> comparator=new Comparator<Student>() {

            @Override
            public int compare(Student o1, Student o2) {
                // TODO Auto-generated method stub
                if(o1.roll<=o2.roll)
                    return -1;
                else return 1;
            }
        };
        TreeMap<Integer, Student> map=new TreeMap<>(comparator);

我不明白这个 Treemap 实现错误的原因。谁能给我解释一下这里发生了什么？

Answer 1

compare() 需要处理三种情况：小于、大于和等于。当它们相等时，您需要 return 0。

if (o1.roll == o2.roll) {
    return 0;
}
else if (o1.roll < o2.roll) {
    return -1;
}
else {
    return 1;
}

Integer.compare(int x, int y) 可以为您完成这一切：

public int compare(Student o1, Student o2) {
    return Integer.compare(o1.roll, o2.roll);
}

在 Java 8 中，您可以在一行中创建整个比较器：

Map<Integer, Student> map = new TreeMap<>(Comparator.comparingInt(s -> s.roll));

Answer 2

TL;DR: TreeMap<Integer, Student> 的比较器需要比较 Integers，而不是 Students。

A TreeMap<Integer, Student> 从整数（“键”）映射到学生对象（“值”）并保持映射按整数排序。因此构造函数不接受 Comparator<Student> 作为参数。

根据TreeMap<K,V>的文档，以比较器为参数的构造函数声明为

    TreeMap(Comparator<? super K> comparator)

这意味着比较器必须在 K 类型、键的类型或 K 的某些超类型上工作。在你的例子中，K 是 Integer.

既然Integerclass已经定义了一个排序，也就是所谓的自然排序，我建议你根本不需要比较器：

    TreeMap<Integer, Student> map = new TreeMap<>();

如果您想按 roll 编号存储学生，只需像这样插入：

        Student me = new Student();
        map.put(me.roll, me);

副作用是地图按 roll 排序。

PS 中的信息也正确，一个比较器需要处理三种情况。推荐Comparator.comparingInt(s -> s.roll)或Comparator.comparingInt(Student::getRoll)（如果class有这样的getter），不仅是为了简洁，更因为它更不容易出错。

如何用比较器实现树图？

how to implement Treemap with comparator?

java

treemap

comparator