TreeSet集合

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

图1 二叉树的存储结构

在图1所示的二叉树中，同一层的元素，左边的元素总是小于右边的元素。为了使初学者更好的理解TreeSet集合中二叉树存放元素的原理，接下来就分析一下二叉树中元素的存储过程。当二叉树中存入新元素时，新元素首先会与第1个元素（最顶层元素）进行比较，如果小于第1个元素就执行左边的分支，继续和该分支的子元素进行比较；如果大于第1个元素就执行右边的分支，继续和该分支的子元素进行比较。如此往复，直到与最后一个元素进行比较时，如果新元素小于最后一个元素就将其放在最后一个元素的左子树上，如果大于最后一个元素就将其放在最后一个元素的右子树上。

上面通过文字描述的方式对二叉树的存储原理进行了讲解，接下来通过一个具体的图例来演示二叉树的存储过程。假设向集合中存入8个元素，依次为13、8、17、17、1、11、15、25，如果以二叉树的方式来存储，在集合中的存储结构会形成一个树状结构，如图2所示。

图2 二叉树

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

针对TreeSet集合存储元素的特殊性，TreeSet在继承Set接口的基础上实现了一些特有的方法，如表1所示。

表1 TreeSet集合的特有方法

了解了TreeSet集合存储元素的原理和一些常用元素操作方法后，接下来通过一个案例来演示TreeSet集合中常用方法的使用，如文件1所示。

文件1 Example11.java

 1    import java.util.TreeSet;
 2    public class Example11 {
 3        public static void main(String[] args) {
 4            // 创建TreeSet集合
 5             TreeSet ts = new TreeSet();     
 6            // 1、向TreeSet集合中添加元素
 7            ts.add(3);
 8            ts.add(9);
 9            ts.add(1);
 10            ts.add(21);
 11            System.out.println("创建的TreeSet集合为："+ts);
 12            // 2、获取首尾元素
 13            System.out.println("TreeSet集合首元素为："+ts.first());
 14            System.out.println("TreeSet集合尾部元素为："+ts.last());
 15            // 3、比较并获取元素
 16            System.out.println("集合中小于或等于9的最大的一个元素为："
 17                                   +ts.floor(9)); 
 18            System.out.println("集合中大于10的最小的一个元素为："+ts.higher(10));
 19            System.out.println("集合中大于100的最小的一个元素为："
 20                                   +ts.higher(100));
 21            // 4、删除元素
 22            Object first = ts.pollFirst();
 23            System.out.println("删除的第一个元素是："+first);
 24            System.out.println("删除第一个元素后TreeSet集合变为："+ts);
 25        }
 26    }

运行结果如图3所示。

图3 运行结果

从图3可以看出，使用TreeSet集合的方法正确完成了集合元素的操作。另外从输出结果也可以看出，向TreeSet集合添加元素时，不论元素的添加顺序如何，这些元素都能够按照一定的顺序进行排列，其原因是每次向TreeSet集合中存入一个元素时，就会将该元素与其他元素进行比较，最后将它插入到有序的对象序列中。集合中的元素在进行比较时，都会调用compareTo()方法，该方法是Comparable接口中定义的，因此要想对集合中的元素进行排序，就必须实现Comparable接口。Java中大部分的类都实现了Comparable接口，并默认实现了接口中的CompareTo()方法，如Integer、Double和String等。

在实际开发中，除了会向TreeSet集合中存储一些Java中默认的类型数据外，还会存储一些用户自定义的类型数据，如Student类型数据、Teacher类型数据等。由于这些自定义类型的数据没有实现Comparable接口，因此也就无法直接在TreeSet集合中进行排序操作。为了解决这个问题，Java提供了两种TreeSet的排序规则，分别为：自然排序和定制排序。在默认情况下，TreeSet集合都是采用自然排序，接下来将对这两种排序规则进行详细讲解。

1．自然排序

自然排序要求向TreeSet集合中存储的元素所在类必须实现Comparable接口，并重写compareTo()方法，然后TreeSet集合就会对该类型元素使用compareTo()方法进行比较，并默认进行升序排序。

接下来，就以自定义的Teacher类为例，来演示TreeSet集合中自然排序的使用，如文件2所示。

文件2 Example12.java

 1    import java.util.TreeSet;
 2    // 定义Teacher类实现Comparable接口
 3    class Teacher implements Comparable { 
 4        String name;
 5        int age;
 6        public Teacher(String name, int age) {
 7            this.name = name;
 8            this.age = age;
 9        }
 10        public String toString() {            
 11            return name + ":" + age;
 12        }
 13        //重写Comparable接口的compareTo()方法
 14        public int compareTo(Object obj){
 15            Teacher s = (Teacher) obj;    
 16             // 定义比较方式，先比较年龄age，再比较名称name     
 17            if(this.age -s.age > 0) {        
 18                    return 1;
 19            }
 20            if(this.age -s.age == 0) {        
 21                return this.name.compareTo(s.name);    
 22            }
 23            return -1;
 24        }
 25    }
 26    public class Example12 {
 27        public static void main(String[] args) {
 28            TreeSet ts = new TreeSet();               
 29            ts.add(new Teacher("Jack",19));           
 30            ts.add(new Teacher("Rose",18));
 31            ts.add(new Teacher("Tom", 19));
 32            ts.add(new Teacher("Rose",18));
 33            System.out.println(ts);
 34       }
 35    }

运行结果如图4所示。

图4 运行结果

文件2中，Teacher类实现了Comparable接口，并重写了compareTo()方法。在compareTo()方法中，首先先针对age值进行比较，根据比较结果返回-1和1，当age相同时，再对name进行比较。因此，从运行结果可以看出，教师Teacher对象首先按照年龄升序排序，年龄相同时会按照姓名进行升序排序，并且TreeSet集合会将重复的元素去掉。

2．定制排序

有时候，用户自定义的类型数据所在的类没有实现Comparable接口或者对于实现了Comparable接口的类而不想按照定义的compareTo()方法进行排序。例如，希望存储在TreeSet集合中的字符串可以按照长度而不是英文字母的顺序来进行排序，这时，可以通过在创建TreeSet集合时就自定义一个比较器来对元素进行定制排序。接下来通过一个案例来实现TreeSet集合中字符串按照长度进行定制排序，如文件3所示。

文件3 Example13.java

 1    import java.util.Comparator;
 2    import java.util.TreeSet;
 3    // 定义比较器实现Comparator接口
 4    class MyComparator implements Comparator {  
 5        public int compare(Object obj1, Object obj2) {  // 定制排序方式
 6            String s1 = (String) obj1;
 7            String s2 = (String) obj2;
 8            int temp = s1.length() - s2.length();
 9            return temp;
 10        }
 11    }
 12    public class Example13 {
 13        public static void main(String[] args) {
 14            // 1、创建集合时，传入Comparator接口实现定制排序规则
 15            TreeSet ts = new TreeSet(new MyComparator());
 16            ts.add("Jack");
 17            ts.add("Helena");
 18            ts.add("Eve");
 19            System.out.println(ts);
 20            // 2、创建集合时，使用Lambda表达式定制排序规则
 21            TreeSet ts2 = new TreeSet((obj1, obj2) -> {
 22                String s1 = (String) obj1;
 23                String s2 = (String) obj2;
 24                return s1.length() - s2.length();
 25            });
 26            ts2.add("Jack");
 27            ts2.add("Helena");
 28            ts2.add("Eve");
 29            System.out.println(ts2);
 30        }
 31    }

运行结果如图5所示。

图5 运行结果

文件3中，使用了TreeSet集合的public TreeSet(Comparator<? super E> comparator)有参构造方法，分别传入Comparable接口实现类MyComparator以及Lambda表达式两种参数方式创建了定制序规则的TreeSet集合，当向集合中添加元素时，TreeSet集合就会按照定制的排序规则进行比较，从而使存入TreeSet集合中的字符串按照长度进行排序。

注意：

在使用TreeSet集合存储数据时，TreeSet集合会对存入元素进行比较排序，所以为了保证程序的正常运行，一定要保证存入TreeSet集合中的元素是同一种数据类型。