编程那点事编程那点事

专注编程入门及提高
探究程序员职业规划之道!

Java的TreeSet集合

TreeSet是Set接口的另一个实现类,它内部采用自平衡的排序二叉树来存储元素,这样的结构可以保证TreeSet集合中没有重复的元素,并且可以对元素进行排序。所谓二叉树就是说每个节点最多有两个子节点的有序树,每个节点及其子节点组成的树称为子树,通常左侧的子节点称为“左子树”,右侧的子节点称为“右子树”,二叉树中元素的存储结构如图所示。

二叉树中元素的存储结构

在实际应用中,二叉树分为很多种,如排序二叉树、平衡二叉树等。TreeSet集合内部使用的是自平衡的排序二叉树,它的特点是存储的元素会按照大小排序,并能去除重复元素。例如向一个二叉树中存入8个元素,依次为13、8、17、17、1、11、15、25,如果以排序二叉树的方式来存储,在集合中的存储结构会形成一个树状结构,如图所示。

树状结构

从图可以看出,在向TreeSet集合依次存入元素时,首先将第1个存入的元素放在二叉树的最顶端,之后存入的元素与第一个元素比较,如果小于第一个元素就将该元素放在左子树上,如果大于第1个元素,就将该元素放在右子树上,依此类推,按照左子树元素小于右子树元素的顺序进行排序。当二叉树中已经存入一个17的元素时,再向集合中存入一个为17的元素时,TreeSet会将把重复的元素去掉。

了解了二叉树存放元素的原理,接下来通过一个案例来演示TreeSet对元素的排序效果,如例所示。

import java.util.Iterator;
import java.util.TreeSet;
public class Example {
    public static void main(String[] args) {
        TreeSet ts = new TreeSet(); // 创建TreeSet 集合
        ts.add("Jack"); // 向TreeSet 集合中添加元素
        ts.add("Helena");
        ts.add("Helena");
        ts.add("Eve");
        Iterator it = ts.iterator(); // 获取Iterator 对象
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

运行结果:

Eve
Helena
Jack

从图可以看出,通过迭代器Iterator迭代出的字符串元素按照字母表的顺序打印了出来,这些元素之所以能够排序是因为每次向TreeSet集合中存入一个元素时,就会将该元素与其他元素进行比较,最后将它插入到有序的对象序列中。集合中的元素在进行比较时,都会调用compareTo()方法,该方法是Comparable接口中定义的,因此要想对集合中的元素进行排序,就必须实现Comparable接口。JDK 中大部分的类都实现Comparable接口,拥有了接口中的CompareTo()方法,如Integer、Double和String等。

在TreeSet集合中存放Student类型对象时,如果Student类没有实现Comparable接口,则Student类型的对象将不能进行比较,这时,TreeSet集合就不知道按照什么排序规则对Student对象进行排序,最终导致程序报错。因此,为了在TreeSet集合中存放Student对象,必须使Student类实现Comparable接口,如例所示。

import java.util.Iterator;
import java.util.TreeSet;
class Student implements Comparable { // 定义Student 类实现Comparable 接口
    String name;
    int age;
    public Student(String name, int age) {// 创建构造方法
        this.name = name;
        this.age = age;
    }
    public String toString() { // 重写Object 类的toString()方法,返回描述信息
        return name + ":" + age;
    }
    public int compareTo(Object obj) { // 重写Comparable 接口的compareTo 方法
        Student s = (Student) obj; // 将比较对象强转为Student 类型
        if (this.age - s.age > 0) { // 定义比较方式
            return 1;
        }
        if (this.age - s.age == 0) {
            return this.name.compareTo(s.name); // 将比较结果返回
        }
        return -1;
    }
}
public class Example {
    public static void main(String[] args) {
        TreeSet ts = new TreeSet(); // 创建TreeSet 集合
        ts.add(new Student("Jack", 19)); // 向集合中添加元素
        ts.add(new Student("Rose", 18));
        ts.add(new Student("Tom", 19));
        ts.add(new Student("Rose", 18));
        Iterator it = ts.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

运行结果:

Rose:18
Jack:19
Tom:19

例中,Student 类实现了Comparable 接口中的compareTo()方法。在compareTo()方法中,首先先针对age值进行比较,根据比较结果返回-1和1,当age相同时,再对name进行比较。因此,从运行结果可以看出,学生首先按照年龄排序,年龄相同时会按照姓名排序。

有时候,定义的类没有实现Comparable接口或者实现了Comparable接口而不想按照定义的compareTo()方法进行排序。例如,希望字符串可以按照长度来进行排序,这时,可以通过自定义比较器的方式对TreeSet集合中的元素排序,即实现Comparator接口,在创建TreeSet集合时指定比较器。接下来通过一个案例来实现TreeSet集合中字符串按照长度进行排序,如例所示。

import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;
class MyComparator implements Comparator { // 定义比较器实现Comparator 接口
    public int compare(Object obj1, Object obj2) { // 实现比较方法
        String s1 = (String) obj1;
        String s2 = (String) obj2;
        int temp = s1.length() - s2.length();
        return temp;
    }
}
public class Example {
    public static void main(String[] args) {
        TreeSet ts = new TreeSet(new MyComparator()); // 创建TreeSet 对象时传入自定义比较器
        ts.add("Jack"); // 向该Set 对象中添加字符串
        ts.add("Helena");
        ts.add("Eve");
        Iterator it = ts.iterator(); // 获取Iterator 对象
        // 通过while 循环,逐渐将集合中的元素打印出来
        while (it.hasNext()) {
            // 如果Iterator 有元素进行迭代,则获取元素并进行打印
            Object obj = it.next();
            System.out.println(obj);
        }
    }
}

运行结果:

Eve
Jack
Helena

例中,定义了一个MyComparator类实现了Comparator接口,在compare()方法中实现元素的比较,这就相当于定义了一个比较器。在创建TreeSet集合时,将MyComparator比较器对象传入,当向集合中添加元素时,比较器对象的compare()方法就会被自动调用,从而使存入TreeSet集合中的字符串按照长度进行排序。

未经允许不得转载: 技术文章 » Java编程 » Java的TreeSet集合

专注编程入门及提高,探究程序员职业规划之道!