TreeSet 是一个具有唯一元素的二叉树的集合,又被翻译为 树集。Java 中的 TreeSet 类是 Java 集合框架的一部分,从 Java 6 开始,它实现了 NavigableSet
接口(这个接口增加了几个查找元素以及反向遍历的便利方法),从而扩展了 SortedSet
集合。
TreeSet 类与散列类十分相似,不过,它比普通的集合有所改进,树集是一个有序集合(sorted collection),该数据结构的元素按自然顺序排序。
SortedSet
接口提供了保持元素排序的功能。Navigableset
接口提供了可以通过 SortedSet
检索的功能。例如,找到该元素大于或小于给定元素,找到排序集中的第一个和最后一个元素。我们来看看 TreeSet 的接口:
- public TreeSet() {
- this(new TreeMap<>());
- }
-
- public TreeSet(Comparator super E> comparator) {
- this(new TreeMap<>(comparator));
- }
-
- public TreeSet(Collection extends E> c) {
- this();
- addAll(c);
- }
-
- public TreeSet(SortedSet
s) { - this(s.comparator());
- addAll(s);
- }
-
其他方法,可以读者自行研究,如下:
因为实现了 SortedSet
接口,因此具有:
Comparator super E> comparator()
、E first()
E last()
又实现了 NavigableSet
接口:
E higher(E value)
和 E lower(E value)
:返回大于 value 的最小元素和小于 value 的最大元素,如果没有则返回 nullE celling(E value)
和 E floor(E value)
:返回大于等于 value 的最小元素或小于等于 value 的最大元素,如果没有 则返回 nullE pollFirst()
和 E pullLast()
:删除并返回这个集合中的最大元素或最小元素,这个集合为空时返回 nullIterator descendingIterator()
:返回一个按照递减顺序遍历集合中元素的迭代器我们可以以任意顺序将元素插入到集合中,在对集合进行遍历时,会返回排序好的值。例如:
- import java.util.TreeSet;
-
- public class TreeSetExample {
-
- public static void main(String[] args) {
- // 定义一个 String 类型的树集
- TreeSet<String> treeset = new TreeSet<String>();
-
- // 添加元素
- treeset.add("Learning TreeSet");
- treeset.add("Hello, world!");
- treeset.add("ABC");
- treeset.add("Yuzhou1su");
- treeset.add("宇宙之一粟");
-
- for (String ts : treeset) {
- System.out.println(ts);
- }
-
- }
-
- }
-
运行结果:
- ABC
- Hello, world!
- Learning TreeSet
- Yuzhou1su
正如 TreeSet 类名一般,排序是通过树数据结构完成的(实现的是红黑树),如果要使用树集,必须能够比较元素,即这些元素必须实现 Comparable 接口,或者构造集必须提供一个 Comparator。
树集中默认是升序,让我们来自定义一个降序的比较器:
- package com.yuzhou1su.TreeSetExample;
-
- import java.util.TreeSet;
- import java.util.Comparator;
- import java.util.SortedSet;
-
- public class TreeSetDescendingOrderExample {
-
- public static void main(String[] args) {
-
- SortedSet<Integer> nums = new TreeSet<>(Comparator.reverseOrder());
-
- nums.add(1);
- nums.add(99);
- nums.add(20);
- nums.add(2022);
- nums.add(2035);
-
- System.out.println("Descending order:" + nums);
- }
-
- }
-
运算结果:
- Descending order:[2035, 2022, 99, 20, 1]
-
下面来看一下 TreeSet 如何创建、往其中插入元素、如何搜索和字符串化操作。如何集合为空,则 TreeSet 只允许一个空值。TreeSet 的添加、删除和查找包含的函数的算法复杂度为 log(n)
。
- func (treeset *TreeSet) InsertTreeNode(treeNodes ...TreeNode) {
- }