Java中TreeMap和TreeSet的相似之处-猿码集

1. 概述

在Java中，TreeMap和TreeSet都是基于树数据结构实现的集合类。它们在实现过程中有很多相似之处，本文将着重介绍这些相似之处。

2. 底层数据结构

2.1 TreeMap

TreeMap内部使用一棵红黑树来存储键值对，这棵红黑树是一棵自平衡的二叉查找树。 TreeMap根据键的自然顺序进行排序，或者在构造Map时提供一个Comparator对象来对键进行排序。


public class TreeMap extends AbstractMap
    implements NavigableMap, Cloneable, java.io.Serializable {
    // 红黑树的根节点
    private transient Entry root;
    // 构造方法
    public TreeMap() {
        comparator = null;
    }
}

2.2 TreeSet

TreeSet内部使用一棵红黑树来存储元素，这棵红黑树是一棵自平衡的二叉查找树。 TreeSet根据元素的自然顺序进行排序，或者在构造Set时提供一个Comparator对象来对元素进行排序。


public class TreeSet extends AbstractSet
    implements NavigableSet, Cloneable, java.io.Serializable {
    // 红黑树的根节点
    private transient NavigableMap m;
    // 构造方法
    public TreeSet() {
        this(new TreeMap());
    }
}

3. 基本操作

3.1 添加元素

TreeMap和TreeSet都提供了add()方法来向集合中添加元素。在添加元素时，集合会根据元素的自然顺序或提供的Comparator对象对元素进行排序，然后将元素插入到正确的位置。


TreeMap treeMap = new TreeMap<>();
treeMap.put(1, "张三");
treeMap.put(2, "李四");
TreeSet treeSet = new TreeSet<>();
treeSet.add("张三");
treeSet.add("李四");

3.2 删除元素

TreeMap和TreeSet都提供了remove()方法来从集合中删除元素。在删除元素时，集合会根据元素的自然顺序或提供的Comparator对象找到元素所在的位置，并将其删除。


treeMap.remove(1);
treeSet.remove("张三");

3.3 查找元素

TreeMap和TreeSet都提供了contains()方法来判断集合中是否包含某个元素。在查找元素时，集合会根据元素的自然顺序或提供的Comparator对象找到元素所在的位置。


boolean contains = treeMap.containsValue("李四");
contains = treeSet.contains("李四");

4. 遍历集合

4.1 迭代器

TreeMap和TreeSet都提供了iterator()方法来获取集合的迭代器，可以用迭代器遍历集合中的元素。在遍历元素时，集合会根据元素的自然顺序或提供的Comparator对象确定遍历的顺序。


Iterator iterator = treeMap.keySet().iterator();
while (iterator.hasNext()) {
    Integer key = iterator.next();
    String value = treeMap.get(key);
}
Iterator iterator = treeSet.iterator();
while (iterator.hasNext()) {
    String value = iterator.next();
}

4.2 前序遍历

TreeMap和TreeSet都提供了descendingMap()方法来获取集合的反序视图。使用反序视图可以实现前序遍历，遍历一棵二叉查找树的顺序为根节点、左子树、右子树，前序遍历也符合这个顺序。


Map descendingMap = treeMap.descendingMap();
for (Map.Entry entry : descendingMap.entrySet()) {
    Integer key = entry.getKey();
    String value = entry.getValue();
}
NavigableSet descendingSet = treeSet.descendingSet();
for (String value : descendingSet) {
}

5. 总结

TreeMap和TreeSet都是基于树数据结构实现的集合类，它们在底层数据结构、基本操作和遍历集合等方面有很多相似之处。学习和掌握它们的相似之处，对于理解集合框架中树形集合的原理和使用有很大帮助。

Java中TreeMap和TreeSet的相似之处