1 使用上看

• TreeSet要求，每一个元素要实现Comparable接口。
• TreeMap要求键实现Comparable接口。
• Collections.sort()有两种重载方式：
  (1)元素实现Comparable接口。
  (2)向sort()方法中传入一个Comparator实现类。

1. TreeSet
   TreeSet要求存放的对象所属的类必须实现Comparable接口，该接口提供了比较元素的compareTo()方法，当插入元素时会回调该方法比较元素的大小。

2. TreeMap
   TreeMap要求存放的键值对映射的键必须实现Comparable接口，从而根据键对元素进行排序。

3. Collections.sort（）
   工具类的sort方法有两种重载的形式，第一种要求传入的待排序容器中存放的对象必须实现Comparable接口以实现元素的比较；第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator接口的子类型（需要重写compare方法实现元素的比较），相当于一个临时定义的排序规则，其实就是通过接口注入比较元素大小的算法，也是对回调模式的应用（Java中对函数式编程的支持）。

import sun.reflect.generics.tree.Tree;

import java.util.*;

public class JavaTest {
    public static void main(String[] args) {
        Student student1 = new Student("zhang2",10);
        Student student2 = new Student("zhang1",20);
        Student student3 = new Student("zhang3",30);

        /*TreeSet要求，每一个元素要实现Comparable接口。*/
        Set<Student> treeSet = new TreeSet<Student>();
        treeSet.add(student1);
        treeSet.add(student2);
        treeSet.add(student3);

        for (Object o : treeSet) {
            Student stu = (Student) o;
            System.out.println(stu.getName() + " : " + stu.getAge());
        }
        System.out.println();

        /*TreeMap要求键实现Comparable接口*/
        Map map = new TreeMap();
        map.put(student1,2);
        map.put(student2,3);
        map.put(student3,1);

        Set set = map.keySet();
        for (Object o : set) {
            Student stu = (Student) o;
            System.out.println(map.get(stu));
        }

        List<Student> list = new ArrayList<Student>();
        list.add(student1);
        list.add(student2);
        list.add(student3);

        /**
         * Collections.sort()有两种重载方式：
         *  (1)元素实现Comparable接口。
         *  (2)向sort()方法中传入一个Comparator实现类。
         */
        //Student实现了Comparable接口
        Collections.sort(list);
        for (Student student : list) {
            System.out.println(student.getName() + " : " + student.getAge());
        }

        List<Student> list2 = new ArrayList<Student>();
        list2.add(student1);
        list2.add(student2);
        list2.add(student3);

        Collections.sort(list2, new Comparator<Student>() {
            public int compare(Student o1, Student o2) {
                return o1.getAge() - o2.getAge();
            }
        });

        for (Student student : list2) {
            System.out.println(student.getName() + " : " + student.getAge());
        }
    }
}

class Student implements Comparable<Student>{
    private String name;
    private Integer age;

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

    public int compareTo(Student stu) {
        return this.name.compareTo(stu.getName());
    }

    public String getName() {
        return name;
    }

    public Integer getAge() {
        return age;
    }
}

2 原理

参考文献：treeSet的底层实现
TreeMap 的实现就是红黑树数据结构，也就说是一棵自平衡的排序二叉树，这样就可以保证当需要快速检索指定节点。

TreeSet 和 TreeMap 的关系

为了让大家了解 TreeMap 和 TreeSet 之间的关系，下面先看 TreeSet 类的部分源代码：

 public class TreeSet<E> extends AbstractSet<E> 
    implements NavigableSet<E>, Cloneable, java.io.Serializable 
 { 
    // 使用 NavigableMap 的 key 来保存 Set 集合的元素
    private transient NavigableMap<E,Object> m; 
    // 使用一个 PRESENT 作为 Map 集合的所有 value。
    private static final Object PRESENT = new Object(); 
    // 包访问权限的构造器，以指定的 NavigableMap 对象创建 Set 集合
    TreeSet(NavigableMap<E,Object> m) 
    { 
        this.m = m; 
    } 
    public TreeSet()                                      // ①
    { 
        // 以自然排序方式创建一个新的 TreeMap，
        // 根据该 TreeSet 创建一个 TreeSet，
        // 使用该 TreeMap 的 key 来保存 Set 集合的元素
        this(new TreeMap<E,Object>()); 
    } 
    public TreeSet(Comparator<? super E> comparator)     // ②
    { 
        // 以定制排序方式创建一个新的 TreeMap，
        // 根据该 TreeSet 创建一个 TreeSet，
        // 使用该 TreeMap 的 key 来保存 Set 集合的元素
        this(new TreeMap<E,Object>(comparator)); 
    } 
    public TreeSet(Collection<? extends E> c) 
    { 
        // 调用①号构造器创建一个 TreeSet，底层以 TreeMap 保存集合元素
        this(); 
        // 向 TreeSet 中添加 Collection 集合 c 里的所有元素
        addAll(c); 
    } 
    public TreeSet(SortedSet<E> s) 
    { 
        // 调用②号构造器创建一个 TreeSet，底层以 TreeMap 保存集合元素
        this(s.comparator()); 
        // 向 TreeSet 中添加 SortedSet 集合 s 里的所有元素
        addAll(s); 
    } 
    //TreeSet 的其他方法都只是直接调用 TreeMap 的方法来提供实现
    ... 
    public boolean addAll(Collection<? extends E> c) 
    { 
        if (m.size() == 0 && c.size() > 0 && 
            c instanceof SortedSet && 
            m instanceof TreeMap) 
        { 
            // 把 c 集合强制转换为 SortedSet 集合
            SortedSet<? extends E> set = (SortedSet<? extends E>) c; 
            // 把 m 集合强制转换为 TreeMap 集合
            TreeMap<E,Object> map = (TreeMap<E, Object>) m; 
            Comparator<? super E> cc = (Comparator<? super E>) set.comparator(); 
            Comparator<? super E> mc = map.comparator(); 
            // 如果 cc 和 mc 两个 Comparator 相等
            if (cc == mc || (cc != null && cc.equals(mc))) 
            { 
                // 把 Collection 中所有元素添加成 TreeMap 集合的 key 
                map.addAllForTreeSet(set, PRESENT); 
                return true; 
            } 
        } 
        // 直接调用父类的 addAll() 方法来实现
        return super.addAll(c); 
    } 
    ... 
 } 

从上面代码可以看出，TreeSet 的 ① 号、② 号构造器的都是新建一个 TreeMap 作为实际存储 Set 元素的容器，而另外 2 个构造器则分别依赖于 ① 号和 ② 号构造器，由此可见，TreeSet 底层实际使用的存储容器就是 TreeMap。

与 HashSet 完全类似的是，TreeSet 里绝大部分方法都是直接调用 TreeMap 的方法来实现的，这一点读者可以自行参阅 TreeSet 的源代码，此处就不再给出了。

对于 TreeMap 而言，它采用一种被称为“红黑树”的排序二叉树来保存 Map 中每个 Entry —— 每个 Entry 都被当成“红黑树”的一个节点对待。