TreeSet详解

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);
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

运行结果:

0
1
10
15
100
1
2
3
4
5

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集合放进去，拿出来是有序的
1
2
3
4
5
6
7
8
9

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 +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

运行结果:

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)
1
2
3
4
5

程序运行结果抛出了一个异常: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 都有可能
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

总结:

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

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

3. TreeSet底层原理:

• TreeSet/TreeMap底层都采用的是自平衡二叉树(TreeSet底层是TreeMap): 遵循左小右大的原则存放，存放的过程也就是排序的过程

• 遍历二叉树的三种方式: (note:左永远在右的左边)

  • 前序遍历: 根左右
  • 中序遍历:左根右 (满足自平衡二叉树的存放方式，中序遍历取出数据的时候就为自动排序好的数据)
  • 后序遍历:左右根

• TreeSet/TreeMap集合采用的是：中序遍历

• 二叉树的遍历均可以看成是递归的过程，也就是将一个树不断的划分成左子树、根、右子树的过程，直到不能再划分成一个子树