当前位置：网站首页>一起学习集合框架之 TreeSet

一起学习集合框架之 TreeSet

2022-08-08 10:44:00 【51CTO】

什么是 TreeSet

TreeSet 是一个具有唯一元素的二叉树的集合，又被翻译为树集。Java 中的 TreeSet 类是 Java 集合框架的一部分，从 Java 6 开始，它实现了 NavigableSet 接口（这个接口增加了几个查找元素以及反向遍历的便利方法），从而扩展了 SortedSet 集合。

一起学习集合框架之 TreeSet_java

TreeSet 类与散列类十分相似，不过，它比普通的集合有所改进，树集是一个有序集合（sorted collection），该数据结构的元素按自然顺序排序。

SortedSet 接口提供了保持元素排序的功能。
Navigableset 接口提供了可以通过 SortedSet 检索的功能。例如，找到该元素大于或小于给定元素，找到排序集中的第一个和最后一个元素。

接口 API

一起学习集合框架之 TreeSet_git_02

我们来看看 TreeSet 的接口：

TreeSet()

       
       public TreeSet() {
       
    this(new TreeMap<>());
       
}
      
1.
2.
3.

TreeSet(Comparator<? super E> comparator)

       
       public TreeSet(Comparator<? super E> comparator) {
       
    this(new TreeMap<>(comparator));
       
}
      
1.
2.
3.

TreeSet(Collection<? extends E> c)

       
           public TreeSet(Collection<? extends E> c) {
       
        this();
       
        addAll(c);
       
    }
      
1.
2.
3.
4.

TreeSet(SortedSet<E> s)

       
           public TreeSet(SortedSet<E> s) {
       
        this(s.comparator());
       
        addAll(s);
       
    }
      
1.
2.
3.
4.

其他方法

其他方法，可以读者自行研究，如下：

一起学习集合框架之 TreeSet_自定义_03

因为实现了 SortedSet 接口，因此具有：

Comparator<? super E> comparator() 、
E first()
E last()

又实现了 NavigableSet<E> 接口：

E higher(E value) 和 E lower(E value) ：返回大于 value 的最小元素和小于 value 的最大元素，如果没有则返回 null
E celling(E value)和 E floor(E value) ：返回大于等于 value 的最小元素或小于等于 value 的最大元素，如果没有则返回 null
E pollFirst() 和 E pullLast()：删除并返回这个集合中的最大元素或最小元素，这个集合为空时返回 null
Iterator<E> descendingIterator()：返回一个按照递减顺序遍历集合中元素的迭代器

简单的 TreeSet 例子

我们可以以任意顺序将元素插入到集合中，在对集合进行遍历时，会返回排序好的值。例如：

       
       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);
       
    }
       
  }
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.

运行结果：

       
       ABC
       
Hello, world!
       
Learning TreeSet
       
Yuzhou1su
       
宇宙之一粟
      
1.
2.
3.
4.
5.

正如 TreeSet 类名一般，排序是通过树数据结构完成的（实现的是红黑树），如果要使用树集，必须能够比较元素，即这些元素必须实现 Comparable 接口，或者构造集必须提供一个 Comparator。

自定义比较器的 TreeSet

树集中默认是升序，让我们来自定义一个降序的比较器：

       
       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);
       
  }
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.

运算结果：

       
       Descending order:[2035, 2022, 99, 20, 1]
      
1.

下面来看一下 TreeSet 如何创建、往其中插入元素、如何搜索和字符串化操作。如何集合为空，则 TreeSet 只允许一个空值。TreeSet 的添加、删除和查找包含的函数的算法复杂度为 log(n)。

插入节点

       
       func (treeset *TreeSet) InsertTreeNode(treeNodes ...TreeNode) {
       
}
      
1.
2.

参考链接：

《Java 核心技术卷 1 》j（原书第 11 版）：9.3.4 树集，Page 388-389
https://pkg.go.dev/gitee.com/mirrors/gods.git/sets/treeset
https://github.com/emirpasic/gods/blob/master/sets/treeset/treeset.go

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/yuzhou1su/5553439