一起学习集合框架之 TreeSet

客官°小女子只卖身不卖艺 2023-09-27 12:44 70阅读 0赞

### 什么是 TreeSet ###

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

![f4d75ba4a2baf2e17853b948e57117d5.png][]

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

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

### 接口 API ###

![d3601fa1a757ae1197f48a22529356ff.png][]

我们来看看 TreeSet 的接口：

#### TreeSet() ####

public TreeSet() {
            this(new TreeMap<>());
    }

#### TreeSet(Comparator<? super E> comparator) ####

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

#### TreeSet(Collection<? extends E> c) ####

public TreeSet(Collection<? extends E> c) {
            this();
            addAll(c);
        }

#### TreeSet(SortedSet s) ####

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

#### 其他方法 ####

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

![9519a0cdf316ef96e13183f6f164874c.png][]

因为实现了 `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);
            }
    
        }
    
    }

运行结果：

ABC
    Hello, world!
    Learning TreeSet
    Yuzhou1su

正如 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);
        }
    
    }

运算结果：

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

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

### 插入节点 ###

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

[f4d75ba4a2baf2e17853b948e57117d5.png]: https://img-blog.csdnimg.cn/img_convert/f4d75ba4a2baf2e17853b948e57117d5.png
[d3601fa1a757ae1197f48a22529356ff.png]: https://img-blog.csdnimg.cn/img_convert/d3601fa1a757ae1197f48a22529356ff.png
[9519a0cdf316ef96e13183f6f164874c.png]: https://img-blog.csdnimg.cn/img_convert/9519a0cdf316ef96e13183f6f164874c.png