1.类图

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable {}

TreeSet继承了抽象类AbstractSet，实现了NavigableSet、Cloneable、Serializable接口

• NavigableSet：导航方法，treeMap实现的接口
• Cloneable：可以克隆
• Serializable：可以被序列化

与HashSet类似，TreeSet底层是通过TreeMap实现的。底层是红黑树，加入了排序功能，升序遍历。

2.成员变量

//存放元素的集合
private transient NavigableMap<E,Object> m;
//PRESENT就是上面NavigableMap中的Object，类似于hashSet的作用
private static final Object PRESENT = new Object();

3. 构造方法

    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }
    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }
    TreeSet(NavigableMap<E,Object> m) {
        // 通过多态的形式生成了一个TreeMap并赋值给了m。
        // NavigableMap<E,Object> m = new TreeMap<E,Object>()
        this.m = m;
    }

底层就是new一个TreeMap来实现的，我们还可以定义自己的比较器和排序器。

4.方法

4.1 继承于AbstractCollection的方法

类似于hashSet，增删改的方法全部来自于AbstractCollection，底层实现调用了treeMap的方法。

    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
    public boolean contains(Object o) {
        return m.containsKey(o);
    }
    public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
    }
    public void clear() {
        m.clear();
    }
    public int size() {
        return m.size();
    }
    public boolean isEmpty() {
        return m.isEmpty();
    }
    public Iterator<E> iterator() {
        return m.navigableKeySet().iterator();
    }

4.2 实现NavigableSet的方法

这所有的方法底层基本上也都调用了treeMap的方法

• 返回子set

  //底层其实就是通过TreeMap的subMap()实现的
  public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                        E toElement,   boolean toInclusive) {
   return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                        toElement,   toInclusive));
  }

• 返回set的头部与尾部

  // 返回Set的头部，范围是：从头部到toElement。
  // inclusive：是否包含toElement的标志
  public NavigableSet<E> headSet(E toElement, boolean inclusive) {
    return new TreeSet<E>(m.headMap(toElement, inclusive));
  }
  // 返回Set的尾部，范围是：从fromElement到结尾。
  public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
    return new TreeSet<E>(m.tailMap(fromElement, inclusive));
  }

• 返回特定元素

  // 返回Set的第一个元素
  public E first() { return m.firstKey(); }
  // 返回Set的最后一个元素
  public E last() { return m.lastKey(); }
  // 返回Set中小于e的最大元素
  public E lower(E e) { return m.lowerKey(e); }
  // 返回Set中小于/等于e的最大元素
  public E floor(E e) { return m.floorKey(e);}
  // 返回Set中大于/等于e的最小元素
  public E ceiling(E e) { return m.ceilingKey(e);}
  // 返回Set中大于e的最小元素
  public E higher(E e) { return m.higherKey(e);}

• 返回特定元素并移除

  // 获取第一个元素，并将该元素从TreeMap中删除。
  public E pollFirst() {
    Map.Entry<E,?> e = m.pollFirstEntry();
    return (e == null)? null : e.getKey();
  }
  // 获取最后一个元素，并将该元素从TreeMap中删除。
  public E pollLast() {
    Map.Entry<E,?> e = m.pollLastEntry();
    return (e == null)? null : e.getKey();
  }