TreeSet详解

大家好，欢迎来到IT知识分享网。

TreeSet详解

TreeSet的基本操作

放到TreeSet集合中的元素: 无序不可重复，但是可以按照元素的大小顺序自动排序

 // 集合的创建 TreeSet<Integer> ts = new TreeSet<>(); // 添加元素 ts.add(1); ts.add(100); ts.add(10); ts.add(0); ts.add(15); //迭代器遍历 Iterator<Integer> it = ts.iterator(); while(it.hasNext()){ 
    Integer next = it.next(); System.out.println(next); } //增强for循环遍历 for (Integer i: ts) { 
    System.out.println(i); } 

运行结果:

0 1 10 15 100 

1. TreeSet集合底层实际上是一个TreeMap，而TreeMap集合底层是一个二叉树，也将TreeSet集合中的元素称为可排序组合

应用场景之一: 在页面展示用户信息的时候按照生日升序或者降序

 数据库中有很多数据: userid name birth ----------------------- 1 zs 1980-11-11 2 ls 1980-10-11 3 ww 1981-11-11 4 zl 2001-12-23 编写程序从数据库当中取出数据，在页面展示用户信息的时候按照生日升序或者降序。 这个时候可以使用TreeSet集合，因为TreeSet集合放进去，拿出来是有序的 

TreeSet集合，对自定义类型不能进行排序！！！

example:

public class TreeSetTest03 { public static void main(String[] args) { Person p1 = new Person(32); Person p2 = new Person(20); Person p3 = new Person(25); TreeSet<Person> ts = new TreeSet<>(); ts.add(p1); ts.add(p2); ts.add(p3); for (Person x: ts) { System.out.println(x); } } } class Person{ int age; public Person(int age){ this.age = age; } // 重写toString方法 @Override public String toString() { return "Person{" + "age=" + age + '}'; } } 

运行结果:

Exception in thread "main" java.lang.ClassCastException: com.lxz.review1.Person cannot be cast to java.lang.Comparable at java.util.TreeMap.compare(TreeMap.java:1294) at java.util.TreeMap.put(TreeMap.java:538) at java.util.TreeSet.add(TreeSet.java:255) at com.lxz.review1.TreeSetTest03.main(TreeSetTest03.java:23) 

程序运行结果抛出了一个异常:Person cannot be cast to java.lang.Comparable.程序无法进行排序是因为没有指定自定义类型Person对象之间的比较规则，谁大谁小没有说明！

在TreeSet中实现自定义类型的排序有两种方法

1. 方式一:放在TreeSet集合中的元素需要实现java.lang.Comparable接口

public class TreeSetTest04 { public static void main(String[] args) { Person1 p1 = new Person1(32); Person1 p2 = new Person1(20); Person1 p3 = new Person1(25); TreeSet<Person1> ts = new TreeSet<>(); ts.add(p1); ts.add(p2); ts.add(p3); for (Person1 x: ts) { System.out.println(x); } } } / * 放在TreeSet集合中的元素需要实现java.lang.Comparable接口 * 并且实现compareTo方法。equals可以不写 */ class Person1 implements Comparable<Person1>{ int age; public Person1(int age){ this.age = age; } // 重写toString方法 @Override public String toString() { return "Person1{" + "age=" + age + '}'; } / * 需要在这个比较的方法中编写比较的逻辑或者比较的规则，按照什么进行比较 * 拿着参数k和集合中的每一个key进行比较，返回值可能是大于0 小于0 或者等于0 * 比较规则最终还是由程序员指定的； 例如按照年龄升序，或者按照年龄降序。 * @param o * @return */ @Override public int compareTo(Person1 o) { // c1.compareTo(c2) return this.age-o.age; // >0 =0 <0 都有可能 } } 

2. 方式二:在构造器TreeSet或者TreeMap集合的时候给它传一个比较器对象

public class TreeSetTest06 { public static void main(String[] args) { // 此时创建TreeSet集合的时候,需要使用这个比较器。 // TreeSet<WuGui> wuGui = new TreeSet<>(); // 这样不行,没有通过构造方法传递一个比较器进去。 // 给构造方法传递一个比较器 TreeSet<WuGui> wuGui = new TreeSet<>(new WuGuiComparator()); // 底层源码可知其中一个构造方法的参数为比较器 // 大家可以使用匿名内部类的方式 wuGui.add(new WuGui(100)); wuGui.add(new WuGui(10)); wuGui.add(new WuGui(1000)); for (WuGui wugui: wuGui) { System.out.println(wugui); } } } class WuGui { int age; public WuGui(int age) { this.age = age; } @Override public String toString() { return "WuGui{" + "age=" + age + '}'; } } // 单独再这里编写一个比较器 // 比较器实现java.util.Comparator接口 (Comparable是java.lang包下的。Comparator是java.util包下的。) class WuGuiComparator implements Comparator<WuGui>{ @Override public int compare(WuGui o1, WuGui o2) { // 指定比较规则 // 按照年龄排序 return o1.age-o2.age; } } 

note:

1. 比较规则经常变换: Comparator 接口的设计符合OCP原则(可切换)
2. 比较规则较固定: Comparable

example: 先按照年龄升序排序，如果年龄一样再按照姓名升序排序(采用实现Comparable接口的方法)

public class TreeSetTest05 { public static void main(String[] args) { TreeSet<Vip> vips = new TreeSet<>(); vips.add(new Vip("zhangsi",20)); vips.add(new Vip("zhangsan",20)); vips.add(new Vip("liuxiangzheng",18)); for (Vip vip: vips) { System.out.println(vip); } } } class Vip implements Comparable<Vip>{ String name; int age; public Vip(String name,int age){ this.name = name; this.age = age; } @Override public String toString() { return "Vip{" + "name='" + name + '\'' + ", age=" + age + '}'; } @Override public int compareTo(Vip o) { if(this.age==o.age){ // 年龄一样按照姓名升序来 // note： this.name 是字符串,String实现了compareTo方法，故直接调用即可 return this.name.compareTo(o.name); }else{ // 年龄不一样 return this.age-o.age; } } } 

总结:

1. 对于自定义的类型，想要在TreeSet中实现排序，必须实现Comparable接口或者编写Comparator比较器,制定其比较规则！JDK自己提供的数据类型不用程序员实现Comparable接口或者编写Comparator比较器是因为它的底层源码都实现了Comparable接口，具有了比较规则，故可以排序！
2. Comparable接口中重写的CompareTo方法的返回值很重要:

返回0表示相同，value会覆盖 返回>0，会继续在右子树上找 返回<0，会继续在左子树上找 

3. TreeSet底层原理:

• TreeSet/TreeMap底层都采用的是自平衡二叉树(TreeSet底层是TreeMap): 遵循左小右大的原则存放，存放的过程也就是排序的过程
• 遍历二叉树的三种方式: (note:左永远在右的左边)
  • 前序遍历: 根左右
  • 中序遍历:左根右 (满足自平衡二叉树的存放方式，中序遍历取出数据的时候就为自动排序好的数据)
  • 后序遍历:左右根
• TreeSet/TreeMap集合采用的是：中序遍历
• 二叉树的遍历均可以看成是递归的过程，也就是将一个树不断的划分成左子树、根、右子树的过程，直到不能再划分成一个子树