Java集合系列（10）--TreeSet

2019-11-08 02:23:15

字体：大中小

来源：转载

供稿：网友

前面，我们学习了HashSet，现在我们来学习TreeSet。首先我们对TreeSet有个整体认识；然后学习它的源码，最后通过代码示例学会使用它。

一、TreeSet的基本概述

TreeSet是基于TreeMap（红黑树）实现的，它继承于AbstractSet抽象类，实现了NavigableSet<E>、Cloneable、java.io.Serializable接口。

TreeSet继承于AbstractSet，即是一个Set集合，具有Set的属性和方法； TreeSet实现了NavigableSet接口，意味着支持一系列最优的搜索方法； TreeSet实现了Cloneable接口，意味着可以被克隆，得到副本； TreeSet中的元素支持两种排序方式：自然排序或者根据TreeSet创建时提供的Comparator进行排序。这取决于具体所使用的构造器； TreeSet为基本操作（add、remove、和contains）的时间复杂度都为log（n），并且 TreeSet也是非同步的，即是非线程安全的； TreeSet的Iterator返回的迭代器也是基于Fail-Fast机制。 面试易考点：

关注点	结论
结合底层实现的数据结构	是有TreeMap实现，红黑树
集合中元素是否允许为空	key、value值都不允许为空
是否允许数据重复	Key值不允许重复，value值允许重复
是否有序	有序
是否线程安全	非线程安全（是非同步）

二、TreeSet的数据结构

1>TreeSet与Collection的关系

由图中可以得到： a、TreeSet继承于AbstractSet，并且实现了NavigableSet接口； b、TreeSet是通过TreeMap实现的，是一个有序的、没有重复元素的set集合。 2>TreeSet的构造函数默认构造函数。使用该构造函数，TreeSet中的元素按照自然排序进行排列。 TreeSet()

// 不带参数的构造函数。创建一个空的TreeMap public TreeSet() { this(new TreeMap<E,Object>()); }

创建的TreeSet包含collection TreeSet(Collection

// 创建TreeSet，并将集合c中的全部元素都添加到TreeSet中 public TreeSet(Collection<? extends E> c) { this(); // 将集合c中的元素全部添加到TreeSet中 addAll(c); }

指定TreeSet的比较器 TreeSet(Comparator

// 带比较器的构造函数。 public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<E,Object>(comparator)); }

创建的TreeSet包含set TreeSet(SortedSet set)

// 创建TreeSet，并将s中的全部元素都添加到TreeSet中 public TreeSet(SortedSet<E> s) { this(s.comparator()); addAll(s); }

三、TreeSet主要API

1>add()

// 添加e到TreeSet中 public boolean add(E e) { return m.put(e, PRESENT)==null; }

2>remove()

// 删除TreeSet中的对象o public boolean remove(Object o) { return m.remove(o)==PRESENT; }

3>clear()

// 清空TreeSet public void clear() { m.clear(); }

4>SortSet()

// 返回子Set。范围是：从fromElement(包括)到toElement(不包括)。 public SortedSet<E> subSet(E fromElement, E toElement) { return subSet(fromElement, true, toElement, false); } // 返回Set的头部，范围是：从头部到toElement(不包括)。 public SortedSet<E> headSet(E toElement) { return headSet(toElement, false); } // 返回Set的尾部，范围是：从fromElement到结尾(不包括)。 public SortedSet<E> tailSet(E fromElement) { return tailSet(fromElement, true); }

5>contains()

// 返回TreeSet是否包含对象(o) public boolean contains(Object o) { return m.containsKey(o); }由上述代码可以知道，这个排序是针对于Set集合中的Key值的；TreeSet实际是通过TreeMap实现的，当中的元素有两种排序方式。使用不带参数的构造函数，则TreeSet的使用自然比较器；若用户需要使用自定义的比较器，则需要使用带比较器的参数。

四、TreeSet的遍历方式

1>Iterator顺序遍历

TreeSet set= new TreeSet（）；Iterator iter = set.iterator();while(iter.hasNext()){System.out.println(iter);}

2>for-each遍历HashSet

// 假设set是TreeSet对象，并且set中元素是String类型String[] arr = (String[])set.toArray(new String[0]);for (String str:arr) System.out.printf("for each : %s/n", str);

TreeSet不支持快速随机遍历，只能通过迭代遍历。

五、TreeSet代码示例

package Test;import java.util.Iterator;import java.util.TreeSet;/** * Created by LKL on 2017/2/19. */public class TestTreeSet { public static void main(String[] args) { testTreeSetAPIs(); } // 测试TreeSet的api public static void testTreeSetAPIs() { String val; // 新建TreeSet TreeSet tSet = new TreeSet(); // 将元素添加到TreeSet中 tSet.add("aaa"); // Set中不允许重复元素，所以只会保存一个“aaa” tSet.add("aaa"); tSet.add("bbb"); tSet.add("eee"); tSet.add("ddd"); tSet.add("ccc"); System.out.println("TreeSet:"+tSet); // 打印TreeSet的实际大小 System.out.printf("size : %d/n", tSet.size()); // 导航方法 // floor(小于、等于) System.out.printf("floor bbb: %s/n", tSet.floor("bbb")); // lower(小于) System.out.printf("lower bbb: %s/n", tSet.lower("bbb")); // ceiling(大于、等于) System.out.printf("ceiling bbb: %s/n", tSet.ceiling("bbb")); System.out.printf("ceiling eee: %s/n", tSet.ceiling("eee")); // ceiling(大于) System.out.printf("higher bbb: %s/n", tSet.higher("bbb")); // subSet() System.out.printf("subSet(aaa, true, ccc, true): %s/n", tSet.subSet("aaa", true, "ccc", true)); System.out.printf("subSet(aaa, true, ccc, false): %s/n", tSet.subSet("aaa", true, "ccc", false)); System.out.printf("subSet(aaa, false, ccc, true): %s/n", tSet.subSet("aaa", false, "ccc", true)); System.out.printf("subSet(aaa, false, ccc, false): %s/n", tSet.subSet("aaa", false, "ccc", false)); // headSet() System.out.printf("headSet(ccc, true): %s/n", tSet.headSet("ccc", true)); System.out.printf("headSet(ccc, false): %s/n", tSet.headSet("ccc", false)); // tailSet() System.out.printf("tailSet(ccc, true): %s/n", tSet.tailSet("ccc", true)); System.out.printf("tailSet(ccc, false): %s/n", tSet.tailSet("ccc", false)); // 删除“ccc” tSet.remove("ccc"); // 将Set转换为数组 String[] arr = (String[])tSet.toArray(new String[0]); for (String str:arr) System.out.printf("for each : %s/n", str); // 打印TreeSet System.out.printf("TreeSet:%s/n", tSet); // 遍历TreeSet for(Iterator iter = tSet.iterator(); iter.hasNext(); ) { System.out.printf("iter : %s/n", iter.next()); } // 删除并返回第一个元素 val = (String)tSet.pollFirst(); System.out.printf("pollFirst=%s, set=%s/n", val, tSet); // 删除并返回最后一个元素 val = (String)tSet.pollLast(); System.out.printf("pollLast=%s, set=%s/n", val, tSet); // 清空HashSet tSet.clear(); // 输出HashSet是否为空 System.out.printf("%s/n", tSet.isEmpty()?"set is empty":"set is not empty"); }}

运行上述代码结果如下：

TreeSet:[aaa, bbb, ccc, ddd, eee]size : 5floor bbb: bbblower bbb: aaaceiling bbb: bbbceiling eee: eeehigher bbb: cccsubSet(aaa, true, ccc, true): [aaa, bbb, ccc]subSet(aaa, true, ccc, false): [aaa, bbb]subSet(aaa, false, ccc, true): [bbb, ccc]subSet(aaa, false, ccc, false): [bbb]headSet(ccc, true): [aaa, bbb, ccc]headSet(ccc, false): [aaa, bbb]tailSet(ccc, true): [ccc, ddd, eee]tailSet(ccc, false): [ddd, eee]for each : aaafor each : bbbfor each : dddfor each : eeeTreeSet:[aaa, bbb, ddd, eee]iter : aaaiter : bbbiter : ddditer : eeepollFirst=aaa, set=[bbb, ddd, eee]pollLast=eee, set=[bbb, ddd]set is empty

文章只是作为自己的学习笔记，借鉴了网上的许多案例，如果觉得阔以的话，希望多交流，在此谢过…

上一篇：2016年蓝桥杯A组java第七题

下一篇：java数组逆序用for循环，for循环的初始化语句定义了两个变量