TreeSet的基本特点

TreeSet是Set接口的另一个实现类。它内部采用平衡二叉树来存储元素。

这种结构有两个特点：一是可以保证TreeSet集合中没有重复的元素，二是可以对元素进行排序。

所谓二叉树，就是每个节点最多有两个子节点的有序树。每个节点及其子节点组成的树称为子树。

通常左侧的子节点称为“左子树”，右侧的节点称为“右子树”。其中左子树上的元素小于它的根结点，而右子树上的元素大于它的根结点。

二叉树中元素的存储结构如图1所示。

图1 二叉树的存储结构

二叉树中元素的存储过程

在图1所示的二叉树中，同一层的元素，左边的元素总是小于右边的元素。

为了使初学者更好的理解TreeSet集合中二叉树存放元素的原理，接下来分析一下二叉树中元素的存储过程。

当二叉树中存入新元素时，新元素首先会与第1个元素（最顶层元素）进行比较。

• 如果小于第1个元素，就执行左边的分支，并继续和该分支的子元素进行比较；

• 如果大于第1个元素，就执行右边的分支，并继续和该分支的子元素进行比较。

如此往复，直到与最后一个元素进行比较时：

• 如果新元素小于最后一个元素，就将其放在最后一个元素的左子树上；

• 如果大于最后一个元素，就将其放在最后一个元素的右子树上。

TreeSet元素存储示例

上面通过文字描述的方式对二叉树的存储原理进行了讲解。接下来通过一个具体的图例来演示二叉树的存储过程。

假设向集合中存入8个元素，依次为13、8、17、17、1、11、15、25。

如果以二叉树的方式来存储，在集合中的存储结构会形成一个树状结构，如图2所示。

图2 二叉树

从图2可以看出，在向TreeSet集合依次存入元素时，首先将第1个存入的元素放在二叉树的最顶端。

之后存入的元素与第一个元素比较：

• 如果小于第一个元素，就将该元素放左子树上；

• 如果大于第1个元素，就将该元素放在右子树上。

依次类推，按照左子树元素小于右子树元素的顺序进行排序。

当二叉树中已经存入一个17的元素时，再向集合中存入一个为17的元素时，TreeSet会将重复的元素去掉。

TreeSet集合的特有方法

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

表1 TreeSet集合的特有方法

TreeSet常用方法示例

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

文件1 Example11.ja va

 1    import ja va.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接口。

Ja va中大部分的类都实现了Comparable接口，并默认实现了接口中的CompareTo()方法，如Integer、Double和String等。

TreeSet的两种排序方式

到了实际开发阶段，TreeSet里装的往往不只是Ja va自带的那些基础类型数据，也经常会放入业务里自己定义的对象，比如Student、Teacher这类类型。

问题就出在这里：这类自定义对象如果没有实现Comparable接口，TreeSet就没法直接对它们完成排序。

那该怎么办？Ja va其实早就给出了两套方案，分别是自然排序和定制排序。

默认情况下，TreeSet采用的是自然排序。

1．自然排序

自然排序要求向TreeSet集合中存储的元素所在类必须实现Comparable接口，并重写compareTo()方法。

然后TreeSet集合就会对该类型元素使用compareTo()方法进行比较，并默认进行升序排序。

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

文件2 Example12.ja va

 1    import ja va.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.ja va

 1    import ja va.util.Comparator;
 2    import ja va.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 comparator)有参构造方法。

分别传入Comparable接口实现类MyComparator以及Lambda表达式两种参数方式创建了定制序规则的TreeSet集合。

当向集合中添加元素时，TreeSet集合就会按照定制的排序规则进行比较，从而使存入TreeSet集合中的字符串按照长度进行排序。

使用TreeSet时的注意事项

注意：

在使用TreeSet集合存储数据时，TreeSet集合会对存入元素进行比较排序。

所以为了保证程序的正常运行，一定要保证存入TreeSet集合中的元素是同一种数据类型。