TreeSet集合-Java程序设计教程

1. TreeSet 集合类的概念

TreeSet 集合类是一个有序集合，它的元素按照升序排序，默认是自然顺序排列，也就是说TreeSet 中的对象元素需要实现Comparable 接口。TreeSet 与HashSet 类一样没有get()方法来获取列表中的元素，所以也只能通过迭代器方法来获取。

由于TreeMap 需要排序，所以需要一个Comparator 为键值进行大小比较，当然也是用Comparator 定位的Comparator 可以在创建TreeMap 时指定，这时排序时使用Comparator.compare。如果创建时没有指定Comparator，那么就会使用key.compareTo()方法，这就要求key必须实现Comparable 接口。TreeSet 是Set 接口的另一个实现类，它内部采用平衡二叉树来存储元素，以保证TreeSet 集合中没有重复的元素，并且可以对元素进行排序。

二叉树就是每个节点最多有两个子节点的有序树，每个节点及其子节点组成的树称为子树，左侧的节点称为“左子树”，右侧的节点称为“右子树”，其中左子树上的元素小于它的根节点，而右子树上的元素大于它的根节点。TreeSet 集合的二叉树存储结构如图7.5 所示。

图7.5　TreeSet 集合的二叉树存储结构

同一层的元素可分为1 个根节点元素和2 个子节点元素，左边的元素总是小于右边的元素。

存储原理：

① TreeSet 集合没有元素时，新增的第1 个元素会在二叉树最顶层。

② 接着新增元素时，首先会与根节点元素比较。

③ 如果小于根节点元素就与左边的分支比较。

④ 如果大于根节点元素就与右边的分支比较。

⑤ 依此类推。

向TreeSet 添加元素举例：向TreeSet 中依次添加13、8、17、17、1、11、15、25 元素。

存储过程：

① 将元素13 个放在二叉树的最顶端。

② 之后存入的元素与13 比较，如果小于13，就将该元素放左子树上；如果大于13，就将该元素放在右子树上。

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

④ 依此类推。

最后生成结果如图7.6 所示。

图7.6　TreeSet 最终生成结果

2. TreeSet 集合类的方法

TreeSet 集合类的常用方法如表7-4 所示。

表7-4　TreeSet 集合的常用方法。(www.xing528.com)

TreeSet 是依靠TreeMap 来实现的。TreeSet 是一个有序集合，它的元素按照升序排列，默认是按照自然顺序排列，也就是说TreeSet 中的对象元素需要实现Comparable 接口。

TreeSet 类中跟HashSet 类一样也没有get()方法来获取列表中的元素，所以也只能通过迭代器的方法来获取，请查看文件7-14。

【例7.14】TreeSet 类中通过迭代器的方法来获取，如文件7-14 所示。

文件7-14　Example14.java

执行结果

3. 元素排序

向 TreeSet 集合添加元素时，都会调用 compareTo()方法进行比较排序。该方法是Comparable 接口中定义的，因此要想对集合中的元素进行排序，就必须实现Comparable 接口。Java 中大部分的类都实现了Comparable 接口，并默认实现了接口中的compareTo()方法，如Integer、Double 和String 等。

（1）自然排序：要求存储的元素类必须实现Comparable 接口，并重写compareTo()方法。

（2）定制排序：要求自定义一个比较器，该比较器必须实现Comparator 接口，并重写compare()方法，然后将该比较器作为参数传入集合的有参构造。

两种排序的主要区别：

① 自然排序：

● 元素类本身实现Comparable 接口。

● 依赖compareTo()方法的实现。

● 实现Comparable 接口排序规则比较单一，不利于后续改进。

② 定制排序：

● 适合元素类本身未实现Comparable 接口，无法进行比较。

● 适合元素类实现的Comparable 接口排序规则无法满足用户需求。

● 会额外定义一个实现Comparator 接口的比较器。