TreeSet简介

TreeSet 是红黑树的数据结构，默认对元素进行自然排序。

• TreeSet 是一个有序的集合，它的作用是提供有序的 Set 集合。它继承于 AbstractSet 抽象类，实现了 NavigableSet&ltE>, Cloneable, java.io.Serializable 接口
• TreeSet 继承于 AbstractSet，所以它是一个 Set 集合，具有 Set 的属性和方法
• TreeSet 实现了 NavigableSet 接口，意味着它支持一系列的导航方法。比如查找与指定目标最匹配项
• TreeSet 实现了 Cloneable 接口，意味着它能被克隆
• TreeSet 实现了 java.io.Serializable 接口，意味着它支持序列化
• TreeSet 是基于 TreeMap 实现的。TreeSet 中的元素支持 2 种排序方式：自然排序或者根据创建 TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法
• TreeSet 为基本操作（add、remove 和 contains）提供受保证的 log(n) 时间开销。另外，TreeSet 是非同步的。它的 iterator 方法返回的迭代器是 fail-fast 的

特点：

• 元素有序，这里的顺序不是指存储和取出的顺序，而是按照一定的规则进行排序，具体排序方式取决于构造方法

  • TreeSet()：根据其元素的自然非序进行排序

  • TreeSet(Comparator comparator)：根据指定的比较器进行排序

• 没有带索引的方法，所以不能使用普通 for 循环遍历

• 由于是 Set 集合，所以不包含重复元素的集合

TreeSet自然顺序

即类要实现 Comparable 接口，并重写 compareTo() 方法，TreeSet 对象调用 add() 方法时，会将存入的对象提升为 Comparable 类型，然后调用对象中的 compareTo() 方法进行比较，根据比较的返回值进行存储。

因为 TreeSet 底层是二叉树，当 compareTo 方法返回 0 时，不存储；当 compareTo 方法返回正数时，存入二叉树的右子树；当 compareTo 方法返回负数时，存入二叉树的左子树。如果一个类没有实现 Comparable 接口就将该类对象存入 TreeSet 集合，会发生类型转换异常。

TreeSet自定义排序

方式一：元素自身具备比较性

元素自身具备比较性，需要元素实现 Comparable 接口，重写 compareTo 方法，也就是让元素自身具备比较性，这种方式叫做元素的自然排序也叫做默认排序。

让元素自身具备比较性

也就是元素需要实现 Comparable 接口，覆盖 compareTo 方法。

案例：创建 Student 类，有姓名，年龄。存入集合后，先根据年龄大小，再根据姓名来进行排序插入集合中

public class Student implements Comparable<Student> {
    public String name;
    public int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Student o) {
        int i = this.age - o.age;
        int n = i == 0 ? this.name.compareTo(o.name) : i;
        return n;
    }
}

重写 compareTo() 方法，返回值有三种情况

1. 返回值为 0：不插入集合
2. 返回值为 1：往后插入集合
3. 返回值为 -1：往前插入集合

public class Demo {
    public static void main(String[] args) {
        Student s1 = new Student("xishi",25);
        Student s2 = new Student("yangyuhuan",29);
        Student s3 = new Student("diaochan",28);
        Student s4 = new Student("wangzhaojun",30);
        Student s5 = new Student("libai",30);
        Student s6 = new Student("libai",30);

        TreeSet<Student> ts = new TreeSet<>();

        ts.add(s1);
        ts.add(s2);
        ts.add(s3);
        ts.add(s4);
        ts.add(s5);
        ts.add(s6);

        for(Student s : ts){
            System.out.println(s.name+"---"+s.age);
        }

    }
}

让容器自身具备比较性，自定义比较器。

需求：当元素自身不具备比较性，或者元素自身具备的比较性不是所需的。

那么这时只能让容器自身具备。

定义一个类实现 Comparator 接口，覆盖 compare 方法。

并将该接口的子类对象作为参数传递给 TreeSet 集合的构造函数。

当 Comparable 比较方式，及 Comparator 比较方式同时存在，以 Comparator 比较方式为主。

public class Demo5 {
	public static void main(String[] args) {
		TreeSet ts = new TreeSet(new MyComparator());
		ts.add(new Book("think in java", 100));
		ts.add(new Book("java 核心技术", 75));
		ts.add(new Book("现代操作系统", 50));
		ts.add(new Book("java就业教程", 35));
		ts.add(new Book("think in java", 100));
		ts.add(new Book("ccc in java", 100));
 
		System.out.println(ts); 
	}
}
 
class MyComparator implements Comparator {
 
	public int compare(Object o1, Object o2) {
		Book b1 = (Book) o1;
		Book b2 = (Book) o2;
		System.out.println(b1+ " comparator "+b2);
		if (b1.getPrice() > b2.getPrice()) {
			return 1;
		}
		if (b1.getPrice() < b2.getPrice()) {
			return -1;
		}
		return b1.getName().compareTo(b2.getName());
	}
}
 
class Book {
	private String name;
	private double price;
 
	public Book() {
 
	}
 
	public String getName() {
		return name;
	}
 
	public void setName(String name) {
		this.name = name;
	}
 
	public double getPrice() {
		return price;
	}
 
	public void setPrice(double price) {
		this.price = price;
	}
 
	public Book(String name, double price) {
 
		this.name = name;
		this.price = price;
	}
 
	@Override
	public String toString() {
		return "Book [name=" + name + ", price=" + price + "]";
	}
 
}