【Set的实现类【TreeSet、HashSet】、数据结构-树】

• 1.Set集合类的体系结构
• 2. Set集合概述和特点
• • 2.1 TreeSet集合概述和特点
  • 2.2 以自定义Student类作为TreeSet的泛型存储数据的错误代码演示
  • 2.3 自然排序
  • 2.3.自定义排序
• 3.两种比较方式小结：自然排序、自定义排序
• 4.数据结构-树
• • 4.1二叉树
  • 4.2二叉查找树
  • 4.3平衡二叉树
  • 4.4红黑树

Set集合的特点

1. 可以去除重复
2. 没有索引，存取顺序不一致
3. 没有带索引的方法所以不能使用for循环遍历元素，也不能通过索引来获取元素和删除元素。可以使用迭代器来遍历元素，增强for循环也可以。

1.不包含重复元素的集合
2.没有带索引的方法
3.可以将元素按照规则进行排序
注意！想要使用TreeSet需要指定排序的规则，要不然玩不了

Student模板类

package day07jiuye;

public class Student {
    private String name;
    private int age;

    public Student() {
    }

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + ''' +
                ", age=" + age +
                '}';
    }
}

TreeSet的测试类

package day07jiuye;

import java.util.Iterator;
import java.util.TreeSet;

public class TreeSetDemo1 {
    public static void main(String[] args) {
        TreeSet treeSet = new TreeSet<>();
        treeSet.add(new Student("小明",23));
        treeSet.add(new Student("xiaowang",25));
        treeSet.add(new Student("老王",22));
        treeSet.add(new Student("老ji",22));

        Iterator it = treeSet.iterator();
        while (it.hasNext()){
            Student next = it.next();
            System.out.println(next);
        }


    }
}

这就是没有指定排序规则使用TreeSet的情况会报错：

那该怎么办呢？
指定规则有两种：
1.自然排序：在这里就是需要Student类实现Comparable接口，然后重写该接口中的public int compareTo(Object o)方法

自然排序的代码演示：

String 的compareTo()方法是比较字符串中每个字符的Ascll码的大小，返回的字符Ascll码值的差值

自定义排序代码：
Student3模板类

package day07jiuye;

public class Student3 {
    private String name;
    private int age;

    public Student3() {
    }

    public Student3(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Student3{" +
                "name='" + name + ''' +
                ", age=" + age +
                '}';
    }
}

测试类TreeSetDemo3 ：

package day07jiuye;


import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetDemo3 {
    public static void main(String[] args) {
        //使用有参构造实现Comparator接口【使用匿名内部类创建Comparator接口的实现类对象传递给有参构造，此处使用了多态的概念】，定义排序规则
        TreeSet treeSet = new TreeSet<>(new Comparator() {
            @Override
            public int compare(Student3 t1, Student3 t2) {
                int result = t1.getAge() - t2.getAge();
                if (result == 0) {
                    result = t1.getName().compareTo(t2.getName());
                }
                return result;
            }
        });
        treeSet.add(new Student3("小明",23));
        treeSet.add(new Student3("xiaowang",25));
        treeSet.add(new Student3("老王",22));
        treeSet.add(new Student3("老ji",22));
        for (Student3 student3 : treeSet) {
            System.out.println(student3);
        }



    }
}

自然排序：自定义类实现Comparable接口，重写compareTo​方法，根据返回值进行排序。

比较器排序：创建TreeSet对象的时候传递Comparator的实现类对象，重写compare方法，根据返回值进行排序。

==为什么是自定义类呢才需要实现Comparable接口呢？==是因为象Integer等包装类都是已经实现了Comparable接口的，所以当TreeSet的泛型是包装类的时候，可以直接使用自然排序规则，但是如果是自己定义的类，那就二选一：

1.自然排序：自定义类实现Comparable接口，重写compareTo​方法，根据返回值进行排序。

2.比较器排序：创建TreeSet对象的时候传递Comparator的实现类对象，重写compare方法，根据返回值进行排序。

第二种比较器排序存在的意义:在使用的时候，默认使用自然排序，当自然排序不满足现在的需求时，使用比较器排序

两种方式中，关于返回值的规则：
如果返回值为负数，表示当前存入的元素是较小值，存左边
如果返回值为0，表示当前存入的元素跟集合中元素重复了，不存
如果返回值为正数，表示当前存入的元素是较大值，存右边

有了平衡二叉树为什么还要红黑树呢？