©2020-2024 ioDraw All rights reserved,
Privacy Policy
<>TreeSet详解
<>TreeSet的基本操作
放到TreeSet集合中的元素: 无序不可重复，但是可以按照元素的大小顺序自动排序
// 集合的创建 TreeSet<Integer> ts = new TreeSet<>(); // 添加元素 ts.add(1); ts.add(100);
ts.add(10); ts.add(0); ts.add(15); //迭代器遍历 Iterator<Integer> it = ts.iterator()
; while(it.hasNext()){ Integer next = it.next(); System.out.println(next); }
//增强for循环遍历 for (Integer i: ts) { System.out.println(i); }
运行结果:
0 1 10 15 100
* TreeSet集合底层实际上是一个TreeMap，而TreeMap集合底层是一个二叉树，也将TreeSet集合中的元素称为可排序组合
应用场景之一: 在页面展示用户信息的时候按照生日升序或者降序
数据库中有很多数据: userid name birth ----------------------- 1 zs 1980-11-11 2 ls 1980
-10-11 3 ww 1981-11-11 4 zl 2001-12-23 编写程序从数据库当中取出数据，在页面展示用户信息的时候按照生日升序或者降序。
这个时候可以使用TreeSet集合，因为TreeSet集合放进去，拿出来是有序的
<>TreeSet集合，对自定义类型不能进行排序！！！
example:
public class TreeSetTest03 { public static void main(String[] args) { Person
p1 = new Person(32); Person p2 = new Person(20); Person p3 = new Person(25);
TreeSet<Person> ts = new TreeSet<>(); ts.add(p1); ts.add(p2); ts.add(p3); for
(Person x: ts) { System.out.println(x); } } } class Person{ int age; public
Person(int age){ this.age = age; } // 重写toString方法 @Override public String
toString() { return "Person{" + "age=" + age + '}'; } }
运行结果:
Exception in thread "main" java.lang.ClassCastException: com.lxz.review1.Person
cannot be castto java.lang.Comparable at java.util.TreeMap.compare(TreeMap.java
:1294) at java.util.TreeMap.put(TreeMap.java:538) at java.util.TreeSet.add(
TreeSet.java:255) at com.lxz.review1.TreeSetTest03.main(TreeSetTest03.java:23)
程序运行结果抛出了一个异常:Person cannot be cast to
java.lang.Comparable.程序无法进行排序是因为没有指定自定义类型Person对象之间的比较规则，谁大谁小没有说明！
<>在TreeSet中实现自定义类型的排序有两种方法
* 方式一:放在TreeSet集合中的元素需要实现java.lang.Comparable接口 public class TreeSetTest04 {
public static void main(String[] args) { Person1 p1 = new Person1(32); Person1
p2 = new Person1(20); Person1 p3 = new Person1(25); TreeSet<Person1> ts = new
TreeSet<>(); ts.add(p1); ts.add(p2); ts.add(p3); for (Person1 x: ts) {
System.out.println(x); } } } /** * 放在TreeSet集合中的元素需要实现java.lang.Comparable接口 *
并且实现compareTo方法。equals可以不写 */ class Person1 implements Comparable<Person1>{ int
age; public Person1(int age){ this.age = age; } // 重写toString方法 @Override
public String toString() { return "Person1{" + "age=" + age + '}'; } /** *
需要在这个比较的方法中编写比较的逻辑或者比较的规则，按照什么进行比较 * 拿着参数k和集合中的每一个key进行比较，返回值可能是大于0 小于0 或者等于0 *
比较规则最终还是由程序员指定的； 例如按照年龄升序，或者按照年龄降序。 * @param o * @return */ @Override public
int compareTo(Person1 o) { // c1.compareTo(c2) return this.age-o.age; // >0 =0
<0 都有可能 } }
* 方式二:在构造器TreeSet或者TreeMap集合的时候给它传一个比较器对象 public class TreeSetTest06 { public
static void main(String[] args) { // 此时创建TreeSet集合的时候,需要使用这个比较器。 //
TreeSet<WuGui> wuGui = new TreeSet<>(); // 这样不行,没有通过构造方法传递一个比较器进去。 //
给构造方法传递一个比较器 TreeSet<WuGui> wuGui = new TreeSet<>(new WuGuiComparator()); //
底层源码可知其中一个构造方法的参数为比较器 // 大家可以使用匿名内部类的方式 wuGui.add(new WuGui(100));
wuGui.add(new WuGui(10)); wuGui.add(new WuGui(1000)); for (WuGui wugui: wuGui)
{ System.out.println(wugui); } } } class WuGui { int age; public WuGui(int age)
{ this.age = age; } @Override public String toString() { return "WuGui{" +
"age=" + age + '}'; } } // 单独再这里编写一个比较器 // 比较器实现java.util.Comparator接口
(Comparable是java.lang包下的。Comparator是java.util包下的。) class WuGuiComparator
implements Comparator<WuGui>{ @Override public int compare(WuGui o1, WuGui o2)
{ // 指定比较规则 // 按照年龄排序 return o1.age-o2.age; } }
note:
* 比较规则经常变换: Comparator 接口的设计符合OCP原则(可切换)
* 比较规则较固定: Comparable
example: 先按照年龄升序排序，如果年龄一样再按照姓名升序排序(采用实现Comparable接口的方法)
public class TreeSetTest05 { public static void main(String[] args) {
TreeSet<Vip> vips = new TreeSet<>(); vips.add(new Vip("zhangsi",20));
vips.add(new Vip("zhangsan",20)); vips.add(new Vip("liuxiangzheng",18)); for
(Vip vip: vips) { System.out.println(vip); } } } class Vip implements
Comparable<Vip>{ String name; int age; public Vip(String name,int age){
this.name = name; this.age = age; } @Override public String toString() { return
"Vip{" + "name='" + name + '\'' + ", age=" + age + '}'; } @Override public int
compareTo(Vip o) { if(this.age==o.age){ // 年龄一样按照姓名升序来 // note： this.name
是字符串,String实现了compareTo方法，故直接调用即可 return this.name.compareTo(o.name); }else{ //
年龄不一样 return this.age-o.age; } } }
总结:
*
对于自定义的类型，想要在TreeSet中实现排序，必须实现Comparable接口或者编写Comparator比较器,制定其比较规则！JDK自己提供的数据类型不用程序员实现Comparable接口或者编写Comparator比较器是因为它的底层源码都实现了Comparable接口，具有了比较规则，故可以排序！
* Comparable接口中重写的CompareTo方法的返回值很重要: 返回0表示相同，value会覆盖 返回>0，会继续在右子树上找 返回<0
，会继续在左子树上找
* TreeSet底层原理:
*
TreeSet/TreeMap底层都采用的是自平衡二叉树(TreeSet底层是TreeMap): 遵循左小右大的原则存放，存放的过程也就是排序的过程
*
遍历二叉树的三种方式: (note:左永远在右的左边)
* 前序遍历: 根左右
* 中序遍历:左根右 (满足自平衡二叉树的存放方式，中序遍历取出数据的时候就为自动排序好的数据)
* 后序遍历:左右根
*
TreeSet/TreeMap集合采用的是：中序遍历
*
二叉树的遍历均可以看成是递归的过程，也就是将一个树不断的划分成左子树、根、右子树的过程，直到不能再划分成一个子树