TreeSet
数据结构：底层是二叉树
代码实现：
public class TreeSetDemo {
public static void main(String[] args) {
TreeSet<Integer> ts = new TreeSet<Integer>() ;
// 添加元素
// 存储下列元素:  20 , 18 , 23 , 22 , 17 , 24, 19 , 18 , 24
ts.add(20) ;
ts.add(18) ;
ts.add(23) ;
ts.add(22) ;
ts.add(17) ;
ts.add(24) ;
ts.add(19) ;
ts.add(18) ;
ts.add(24) ;
// 遍历
for(Integer i : ts){
System.out.println(i);
}
}
}
运行结果：17,18,19,20,22,23,24
二叉树原理分析图：

TreeSet特点：元素唯一，并且可以元素进行排序。
排序方式：
1、自然排序
2、使用比较器排序
而到底使用哪种排序方法，这取决于构造方法（可通过API查阅，构造方法和应用方法）

自然排序：要求对应的元素必须实现Comparable接口，重写其中的compareTo方法
唯一性：是判断方法的返回值是否为0，如果为0，则认为元素相同，不进行添加
代码实现：
第一种方法
public class Student implements Comparable<Student>{//实现Comparable接口
@Override
public int compareTo(Student o) {//重写compareTo方法
// TODO Auto-generated method stub
int num = this.age - o.age;
int num2 = (num == 0)? this.name.compareTo(o.name) : num ;
return num2;
}
private String name;
private int age;
public Student() {
super();
// TODO Auto-generated constructor stub
}
public Student(String name, int age) {
super();
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
}
import java.util.TreeSet;
public class TreeSetDemo {
public static void main(String[] args) {
TreeSet<Student> t = new TreeSet<Student>();
Student s1 = new Student("小张",25);
Student s2 = new Student("小王",23);
Student s3 = new Student("小李",24);
t.add(s1);
t.add(s2);
t.add(s3);
for(Student s : t){
System.out.println(s.getName()+"----"+s.getAge());
}
}
}
运行结果：
小王----23
小李----24
小张----25
解释：学生类实现了Comparable接口，重写了compareTo方法。对对象的年龄进行排序
第二种方法：
/*
* 存储自定义对象
* 按照姓名的长度进行排序
主要条件是姓名的长度
然后是姓名
然后是年龄
* */
import java.util.Comparator;
import java.util.TreeSet;
public class TreeSetDemo {
public static void main(String[] args) {
TreeSet<Student> t = new TreeSet<Student>(new Comparator<Student>(){
@Override
public int compare(Student o1, Student o2) {
// TODO Auto-generated method stub
int num = o1.getName().length() - o2.getName().length();
int num2 = (num == 0)? o1.getName().compareTo(o2.getName()) : num;
int num3 = (num2 == 0)?o1.getAge() - o2.getAge() : num2;
return num3;
}
});
Student s1 = new Student("xiaoming",25);
Student s2 = new Student("xiahong",27);
Student s3 = new Student("xiaozhang",21);
Student s4 = new Student("xiaoli",25);
Student s5 = new Student("xibai",23);
Student s6 = new Student("xiaoli",25);
Student s7 = new Student("xiaoming",25);
Student s8 = new Student("xiaoming",29);
t.add(s1);
t.add(s2);
t.add(s3);
t.add(s4);
t.add(s5);
t.add(s6);
t.add(s7);
t.add(s8);
for(Student s : t){
System.out.println(s.getName()+"----"+s.getAge());
}
}
运行结果：
xibai----23
xiaoli----25
xiahong----27
xiaoming----25
xiaoming----29
xiaozhang----21
解释：完成了需求，首先对名字的长度排序，然后是名字，然后是年龄，用比较器方式。

上面是TreeSet的两种比较方式，虽然有原理图，但可能大家还是不知道为什么TreeSet会进行排序，下面我们来看一下原码，和刚才的HashSet有一些相同之处
public interface Collection {...}//Collection接口
public interface Set extends Collection {...}  //Set接口继承了Collection接口
public TreeSet implements Set { //TreeSet类实现了Set接口
private transient NavigableMap<E,Object> m;//成员类

private static final Object PRESENT = new Object();//成员静态类
//方法之一，传递参数是NavigableMap<E,Object> m类型，
TreeSet(NavigableMap<E,Object> m) {//NavigableMap<E,Object> m也是一个接口，TreeMap是其子接口
        this.m = m;
    }
//无参构造方法，创建一个TreeMap对象
public TreeSet() {
        this(new TreeMap<E,Object>());
    }
//有参构造方法，创建一个比较器的TreeMap
public TreeSet(Comparator<? super E> comparator) {//
        this(new TreeMap<>(comparator));
    }
//从这一行开始分析，向和集中添加元素，本质上是调用m.put方法。
public boolean add(E e) {//m实质上是NavigableMap<E,Object> m = new TreeMap（）
        return m.put(e, PRESENT)==null;//以动态的形式创建的对象，并调用其方法
    }
}
public class TreeMap {
private final Comparator<? super K> comparator;
//构造方法
public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator; //传递您自己定义的比较器，按照您的比较方式
    }
//构造方法
public TreeMap() {
        comparator = null;
    }
//put方法，向Map中添加key和vaule，其中key实质就是我们要传递的元素，vaule在此处您可以忽略。
public V put(K key, V value) {

        Entry<K,V> t = root; //root代表树根
        
        // 创建树根，如果不存在就创建一个
        if (t == null) {
            compare(key, key);


            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        
        int cmp;
        Entry<K,V> parent;
        //从此处开始，是最为重点，最为核心的代码，才是比较器的实质
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);  //通过比较方法比较，返回结果
                if (cmp < 0) //如果返回值为负数，则放在树节点的左边
                    t = t.left;
                else if (cmp > 0) //如果返回值为整数，则放在树节点的右边
                    t = t.right;
                else
                    return t.setValue(value);  //如果返回时0，则说明相等，不添加此元素
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();  //如果是空节点，报异常
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }
}
解释：首先创建树根节点，然后依次向内添加元素，将添加的元素和节点元素比较，看返回值，按照我们制定的比较规则，判断返回值，如果返回值为负数，则放在节点的左边，如果返回值为正数，则放在节点的右边。依次添加，依次比较，向下发展，直至元素添加完毕。

顶一下！！！