1、TreeSet集合底层实际上是一个TreeMap;TreeMap集合底层是一个二叉树
2、放到TreeSet集合中的元素,等同于放到TreeMap集合key部分了。
3、TreeSet集合存储元素特点:无序不可重复的,但是存储的元素可以自动按照大小顺序排序
称为:可排序集合。
无序指的是存进去的顺序和取出来的顺序不同,并且没有下标
TreeSet源码存元素:实际上是调用的TreeMap的put方法
public TreeSet() { this(new TreeMap<E,Object>()); } public boolean add(E e) { return m.put(e, PRESENT)==null; }
TreeMap中存元素:
public V put(K key, V value) { Entry<K,V> t = root; if (t == null) { compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null); size = 1; modCount++; return null; } int cmp; Entry<K,V> parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator; if (cpr != null) { do { parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } else { if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } Entry<K,V> e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e); size++; modCount++; return null; }
TreeMap取元素:
public V get(Object key) { Entry<K,V> p = getEntry(key); return (p==null ? null : p.value); } final Entry<K,V> getEntry(Object key) { // Offload comparator-based version for sake of performance if (comparator != null) return getEntryUsingComparator(key); if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; Entry<K,V> p = root; while (p != null) { int cmp = k.compareTo(p.key); if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p; } return null; }
测试如下:
public static void main(String[] args) { TreeSet<String> set = new TreeSet<>(); set.add("A"); set.add("D"); set.add("F"); set.add("B"); set.add("G"); set.add("E"); set.add("C"); for (String str: set) { System.out.println(str); /* A B C D E F G */ } // 创建一个TreeSet集合 TreeSet<String> ts = new TreeSet<>(); // 添加String ts.add("zhangsan"); ts.add("lisi"); ts.add("wangwu"); ts.add("zhangsi"); ts.add("wangliu"); // 遍历 for(String s : ts){ // 按照字典顺序,升序! System.out.println(s); /* lisi wangliu wangwu zhangsan zhangsi */ } TreeSet<Integer> ts2 = new TreeSet<>(); ts2.add(100); ts2.add(200); ts2.add(900); ts2.add(800); ts2.add(600); ts2.add(10); for(Integer elt : ts2){ // 升序! System.out.println(elt); /* 10 100 200 600 800 900 */ }
1、TreeSet中有两种排序,一个是自然排序,一个是重写compareTo()方法自定义排序。
自然排序可以参考Integer,String等类中的实现。其顺序也是我们常见的“1,2,3,4”,“a,b,c,d”。
2、重写compareTo()方法自定义排序
(1)对自定义的类型来说,TreeSet无法排序, 因为没有指定 自定义类型对象之间的比较规则
程序运行的时候出现异常:
java.lang.ClassCastException: class com.collection.XX cannot be cast to class
java.lang.Comparable 出现这个异常的原因是: 自定义类型对象没有实现java.lang.Comparable接口
如下:
public class TreeSetCustom { public static void main(String[] args) { TreeSet<TreeSetPerson> set = new TreeSet<>(); TreeSetPerson p1 = new TreeSetPerson(28); TreeSetPerson p2 = new TreeSetPerson(12); TreeSetPerson p3 = new TreeSetPerson(24); TreeSetPerson p4 = new TreeSetPerson(16); set.add(p1); set.add(p2); set.add(p3); set.add(p4); for (TreeSetPerson person:set) { System.out.println(person); } } } class TreeSetPerson { private int age; public TreeSetPerson(){ } public TreeSetPerson(int age){ this.age = age; } @Override public String toString(){ return "TreeSetPerson[age="+ this.age + "]"; } }
3、TreeSet集合中元素可排序包括两种方式:
(1)放在集合中的元素实现java.lang.Comparable接口
(2)在构造TreeSet或者TreeMap集合的时候给传一个比较器对象Comparator
TreeSet提供了四种构造器
TreeSet() TreeSet(Collection< ? extends E> c) TreeSet(Comparator< ? super E> comparator) TreeSet(SortedSet< E > s)
(1)实现java.lang.Comparable接口
/** compareTo方法的返回值: 返回0表示相同,value会覆盖 返回>0,会继续在右子树上找 返回<0,会继续在左子树上找 */ public class TreeSetCustom1 { public static void main(String[] args) { TreeSet<TreeSetPeople> peopleSet = new TreeSet<>(); //先按照年龄升序,如果年龄一样的再按照姓名升序 TreeSetPeople p1 = new TreeSetPeople(20,"张三"); TreeSetPeople p2 = new TreeSetPeople(12,"李四"); TreeSetPeople p3 = new TreeSetPeople(24,"王二"); // 按照字典顺序,升序! TreeSetPeople p4 = new TreeSetPeople(18,"赵四");//zhaosi TreeSetPeople p5 = new TreeSetPeople(18,"刘三");//liusan TreeSetPeople p6 = new TreeSetPeople(16,"钱一"); peopleSet.add(p1); peopleSet.add(p2); peopleSet.add(p3); peopleSet.add(p4); peopleSet.add(p5); peopleSet.add(p6); for(TreeSetPeople people:peopleSet){ System.out.println(people); } } } /** 放在TreeSet集合中的元素需要实现java.lang.Comparable接口。 实现compareTo方法 * */ class TreeSetPeople implements Comparable<TreeSetPeople>{ private int age; private String name; public TreeSetPeople(){ } public TreeSetPeople(int age,String name){ this.age = age; this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } public String getName() { return name; } public void setName(String name) { this.name = name; } @Override public String toString(){ return "TreeSetPeople[age=" + this.age + "," + "name=" + this.name + "]"; } /** * 需要在这个方法中编写排序规则,按照什么进行比较 * k.compareTo(t.key) * 拿着参数k和集合中的每一个k进行比较 * */ @Override public int compareTo(TreeSetPeople o) { if (this.age == o.age){ return this.name.compareTo(o.name); }else { return this.age - o.age; } } }
(2)比较器对象Comparator
public class TreeSetComparatorTest { public static void main(String[] args) { // TreeSet<Child> childTreeSets = new TreeSet<>(new ChildComparator()); TreeSet<Child> childTreeSets = new TreeSet<>(new Comparator<Child>() { @Override public int compare(Child o1, Child o2) { return o1.getAge() - o2.getAge(); } }); Child c1 = new Child(10); Child c2 = new Child(6); Child c3 = new Child(2); Child c4 = new Child(8); childTreeSets.add(c1); childTreeSets.add(c2); childTreeSets.add(c3); childTreeSets.add(c4); for (Child c : childTreeSets){ System.out.println(c); } } } class Child{ private int age; public Child(int age){ this.age = age; } @Override public String toString(){ return "Child[age=" + this.age + "]"; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } } class ChildComparator implements Comparator<Child>{ @Override public int compare(Child o1, Child o2) { return o1.getAge() - o2.getAge(); } }
4、Comparable 和 Comparator选择
当比较规则不会发生改变时(比较规则只有1个的时候),可实现Comparable接口
如果比较规则有多个,并且需要多个比较规则之间频繁切换,可使用Comparator接口
1、Teet/TreeMap是自平衡二叉树(AVL),遵循左小右大原则存放
存放是要依靠左小右大原则,存放时,要进行比较
2、遍历二叉树三种方式
(1)前序遍历:根左右
(2)中序遍历:左根右
(3)后序遍历:左右根
注:
前中后说的是“根” 的位置
根在前面是前序;根在中间是中序;根在后面是后序
3、 TreeSet集合/TreeMap集合采用的是:中序遍历方式(左根右)
Iterator迭代器采用的是中序遍历方式
存放的过程就是排序的过程,取出来就是自动按照大小顺序排列的
如下数据:
5 2 8 1 4 7 9 3
在二叉树中表示如下:
进行中序遍历方式(左跟右) 遍历取出,会得到
1 2 3 4 5(根) 7 8 9
如果想深入的研究二叉树数据结构可查阅数据结构相关书籍