当前位置：首页 > article >正文

JAVA基础-树和Set集合

article 2024/10/27 16:04:58

文章目录

1.数据结构（树）
- 1.1 二叉树
- 1.2 二叉查找树
- 1.3 二叉树的遍历
- 1.4 平衡二叉树
- 1.5 红黑树
2.Set集合
- - 2.1Set集合概述和特点
  - 2.2Set集合的使用【应用】
3. HashSet集合
- - 3.1 HashSet底层原理
  - 3.2哈希表结构【理解】
  - 3.3HashSet集合的基本应用
  - 3.4HashSet集合存储学生对象并遍历
  - 3.5 LinkedHashSet集合
4.TreeSet集合
- 4.1TreeSet集合三种遍历
- 4.2 Treeset集合的排序方式
- - 4.2.1默认排序规则（基本数据类型）
  - 4.2.2自然排序Comparable的使用
  - 4.2.3 比较器排序Comparator的使用
  - 4.2.4 TreeSet对象排序练习题
  - 4.2.5两种比较方式总结
五个集合的使用场景

1.数据结构（树）

1.1 二叉树

二叉树的特点
- 二叉树中,任意一个节点的度要小于等于2
  - 节点: 在树结构中,每一个元素称之为节点
  - 度: 每一个节点的子节点数量称之为度
二叉树结构图

1.2 二叉查找树

二叉查找树的特点
- 二叉查找树,又称二叉排序树或者二叉搜索树
- 每一个节点上最多有两个子节点
- 左子树上所有节点的值都小于根节点的值
- 右子树上所有节点的值都大于根节点的值
二叉查找树结构图
二叉查找树和二叉树对比结构图
二叉查找树添加节点规则
- 小的存左边
- 大的存右边
- 一样的不存

1.3 二叉树的遍历

前序遍历

从根结点开始，然后按照当前结点，左子结点，右子结点的顺序遍历

在这里插入图片描述

遍历结果是：

20、18、16、19、23、22、24

中序遍历

从最左边的子节点开始，然后按照左子结点，当前结点，右子结点的顺序遍历

遍历结果是：

16、18、19、20、22、23、24

后序遍历

从最左边的子节点开始，然后按照左子结点，右子结点，当前结点的顺序遍历

遍历结果：

16、19、18、22、24、23、20

层序遍历

从根节点开始一层一层的遍历

20、18、23、16、19、22、24

1.4 平衡二叉树

1.4.1 查找二叉树的弊端

在这里插入图片描述

1.4.2 平衡二叉树的规则：二叉树任意节点的左右两个子树的高度差不超过1

平衡二叉树的平衡是靠二叉树的旋转机制来保证的

1.4.3 平衡二叉树旋转

旋转触发时机
- 当添加一个节点之后,该树不再是一颗平衡二叉树
左旋

确定支点:从添加的节点开始，不断的往父节点找不平衡的节点

举例1：

在这里插入图片描述

举例2：

在这里插入图片描述

右旋

举例1：

举例2:

在这里插入图片描述

平衡二叉树和二叉查找树对比结构图
平衡二叉树旋转的四种情况
- 左左
  - 左左: 当根节点左子树的左子树有节点插入,导致二叉树不平衡
  - 如何旋转: 直接对整体进行右旋即可
- 左右
  - 左右: 当根节点左子树的右子树有节点插入,导致二叉树不平衡
  - 如何旋转: 先在左子树对应的节点位置进行左旋,在对整体进行右旋
- 右右
  - 右右: 当根节点右子树的右子树有节点插入,导致二叉树不平衡
  - 如何旋转: 直接对整体进行左旋即可
- 右左
  - 右左:当根节点右子树的左子树有节点插入,导致二叉树不平衡
  - 如何旋转: 先在右子树对应的节点位置进行右旋,在对整体进行左旋

1.5 红黑树

它是一种特殊的二叉查找树，红黑树的每一个节点上都有存储位表示节点的颜色

每一个节点可以是红或者黑;红黑树不是高度平衡的，它的平衡是通过"红黑规则"进行实现的
在这里插入图片描述

红黑树的红黑规则有哪些
1. 每一个节点或是红色的,或者是黑色的
2. 根节点必须是黑色
3. 如果一个节点没有子节Z点或者父节点,则该节点相应的指针属性值为Nil,这些Nil视为叶节点,每个叶节点(Nil)是黑色的
4. 如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)
5. 对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点
红黑树添加节点的默认颜色
- 添加节点时,默认为红色,效率高
红黑树添加节点后如何保持红黑规则
- 根节点位置
  - 直接变为黑色
- 非根节点位置
  - 父节点为黑色
    - 不需要任何操作,默认红色即可
  - 父节点为红色
    - 叔叔节点为红色
      1. 将"父节点"设为黑色,将"叔叔节点"设为黑色
      2. 将"祖父节点"设为红色
      3. 如果"祖父节点"为根节点,则将根节点再次变成黑色
    - 叔叔节点为黑色
      1. 将"父节点"设为黑色
      2. 将"祖父节点"设为红色
      3. 以"祖父节点"为支点进行旋转

2.Set集合

在这里插入图片描述

2.1Set集合概述和特点

无序：存取顺序不一致
无重复：可以去除重复
没有索引,不能使用普通for循环遍历，也不能通过索引来获取元素

Collection是单列集合的祖宗接口，它的功能是全部单列集合都可以继承使用的。

Collection集合常用方法

方法名	说明
boolean add(E e)	添加元素
boolean remove(Object o)	从集合中移除指定的元素
boolean removeIf(Object o)	根据条件进行移除
void clear()	清空集合中的元素
boolean contains(Object o)	判断集合中是否存在指定的元素
boolean isEmpty()	判断集合是否为空
int size()	集合的长度，也就是集合中元素的个数

2.2Set集合的使用【应用】

存储字符串并遍历（不能用索引）

利用Set系列的集合，添加字符串，并使用多种方式遍历。

迭代器
增强for
Lambda表达式

        //1.创建一个Set集合的对象
        Set<String> s = new HashSet<>();

        //2,添加元素
        //如果当前元素是第一次添加，那么可以添加成功，返回true
        //如果当前元素是第二次添加，那么添加失败，返回false
        s.add("张三");
        s.add("张三");
        s.add("李四");
        s.add("王五");

        //3.打印集合
        //无序
        System.out.println(s);//[李四, 张三, 王五]

        //迭代器遍历
       Iterator<String> it = s.iterator();
        while (it.hasNext()){
            String str = it.next();
            System.out.println(str);
        }

        //增强for
        for (String str : s) {
            System.out.println(str);
        }

        // Lambda表达式
        s.forEach( str->System.out.println(str));

3. HashSet集合

3.1 HashSet底层原理

HashSet集合底层采取哈希表存储数据
哈希表是一种对于增删改查数据性能都较好的结构
哈希表的组成
- JDK8之前:数组+链表
  JDK8开始:数组+链表+红黑树
- 哈希值：对象的整数表现形式,是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值
  - 根据hashcode方法算出来的int类型的整数；
  - 该方法定义在0bject类，所有对象都可以调用，默认使用地址值进行计算；
  - 一般情况下,会重写hashCode方法，利用对象内部的属性值计算哈希值；
- 对象的哈希值的特点
  - 如果没有重写hashcode方法，不同对象计算出的哈希值是不同的
  - 如果已经重写hashcode方法，不同的对象只要属性值相同，计算出的哈希值就是一样的
  - 在小部分情况下，不同的属性值或者不同的地址值，计算出来的哈希值也有可能一样（哈希碰撞)
哈希值的代码示例：

        //1.创建对象
        Student s1 = new Student("zhangsan",23);
        Student s2 = new Student("zhangsan",23);

        //2.如果没有重写hashCode方法，不同对象计算出的哈希值是不同的
        //  如果已经重写hashcode方法，不同的对象只要属性值相同，计算出的哈希值就是一样的
        System.out.println(s1.hashCode());//-1461067292
        System.out.println(s2.hashCode());//-1461067292


        //在小部分情况下，不同的属性值或者不同的地址值计算出来的哈希值也有可能一样。
        //哈希碰撞
        System.out.println("abc".hashCode());//96354
        System.out.println("acD".hashCode());//96354

3.2哈希表结构【理解】

JDK1.8以前

数组 + 链表
JDK1.8以后
- 节点个数少于等于8个
  
  数组 + 链表
- 节点个数多于8个
  
  数组 + 红黑树

3.3HashSet集合的基本应用

存储字符串并遍历

public class HashSetDemo {
    public static void main(String[] args) {
        //创建集合对象
        HashSet<String> set = new HashSet<String>();

        //添加元素
        set.add("hello");
        set.add("world");
        set.add("java");
        //不包含重复元素的集合
        set.add("world");
        //遍历
        for(String s : set) {
            System.out.println(s);
        }
    }
}

3.4HashSet集合存储学生对象并遍历

案例需求
- 创建一个存储学生对象的集合，存储多个学生对象，使用程序实现在控制台遍历该集合
- 要求：学生对象的成员变量值相同，我们就认为是同一个对象

代码实现

学生类

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 boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.age && Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

测试类

public class HashSetDemo02 {
    public static void main(String[] args) {
        //创建HashSet集合对象
        HashSet<Student> hs = new HashSet<Student>();

        //创建学生对象
        Student s1 = new Student("林青霞", 30);
        Student s2 = new Student("张曼玉", 35);
        Student s3 = new Student("王祖贤", 33);

        Student s4 = new Student("王祖贤", 33);

        //把学生添加到集合
        hs.add(s1);//true
        hs.add(s2);//true
        hs.add(s3);//true
        hs.add(s4);//false

        //遍历集合(增强for)
        for (Student s : hs) {
            System.out.println(s.getName() + "," + s.getAge());
        }
    }
}

总结

HashSet集合存储自定义类型元素,要想实现元素的唯一,要求必须重写hashCode方法和equals方法

如果不是自定义的类型元素就不需要重写

3.5 LinkedHashSet集合

在这里插入图片描述

    public static void main(String[] args) {
        //1.创建4个学生对象
        Student s1 = new Student("zhangsan",23);
        Student s2 = new Student("lisi",24);
        Student s3 = new Student("wangwu",25);
        Student s4 = new Student("zhangsan",23);


        //2.创建集合的对象
        LinkedHashSet<Student> lhs = new LinkedHashSet<>();


        //3.添加元素
        System.out.println(lhs.add(s1));//true
        System.out.println(lhs.add(s2));//true
        System.out.println(lhs.add(s3));//true
        System.out.println(lhs.add(s4));//false

        //4.打印集合
        System.out.println(lhs);
        //[Student{name = zhangsan, age = 23}, Student{name = lisi, age = 24}, Student{name = wangwu, age = 25}]
    }

在这里插入图片描述

4.TreeSet集合

不可以存储重复元素
没有索引
可以将元素按照规则进行排序
底层是红黑树

4.1TreeSet集合三种遍历

存储Integer类型的整数并遍历

        //1.创建TreeSet集合对象
        TreeSet<Integer> ts = new TreeSet<>();

        //2.添加元素
        ts.add(4);
        ts.add(5);
        ts.add(1);
        ts.add(3);
        ts.add(2);

        //3.打印集合
        //System.out.println(ts);

        //4.遍历集合（三种遍历）
        //迭代器
        Iterator<Integer> it = ts.iterator();
        while(it.hasNext()){
            int i = it.next();
            System.out.println(i);
        }

        System.out.println("--------------------------");
        //增强for
        for (int t : ts) {
            System.out.println(t);
        }
        System.out.println("--------------------------");
        //lambda
        ts.forEach( i-> System.out.println(i));

4.2 Treeset集合的排序方式

4.2.1默认排序规则（基本数据类型）

对于数值类型:Integer，Double，默认按照从小到大的顺序进行排序。
对于字符、字符串类型:按照字符在ASCII码表中的数字升序进行排序

4.2.2自然排序Comparable的使用

案例需求
- 存储学生对象并遍历
- 要求：按照年龄排序
实现方法：

需要使用TreeSet的空参构造，就是使用默认的自然排序

Student实现Comparable接口，重写里面的抽象方法，再指定比较规则

代码实现

学生类

public class Student implements Comparable<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 +
                '}';
    }

    @Override
    //this：表示当前要添加的元素
    //o：表示已经在红黑树存在的元素

    //返回值：
    //负数：表示当前要添加的元素是小的，存左边
    //正数：表示当前要添加的元素是大的，存右边
    //0 :表示当前要添加的元素已经存在，舍弃
    public int compareTo(Student o) {
        System.out.println("--------------");
        System.out.println("this:" + this);
        System.out.println("o:" + o);
        //指定排序的规则
        //只看年龄，我想要按照年龄的升序进行排列
        return this.getAge() - o.getAge();
    }
    }
}

测试类

public class MyTreeSet2 {
    public static void main(String[] args) {
        //创建集合对象
        TreeSet<Student> ts = new TreeSet<>();
	    //创建学生对象
        Student s1 = new Student("zhangsan",28);
        Student s2 = new Student("lisi",27);
        Student s3 = new Student("wangwu",29);
        Student s4 = new Student("zhaoliu",28);
        Student s5 = new Student("qianqi",30);
		//把学生添加到集合
        ts.add(s1);
        ts.add(s2);
        ts.add(s3);
        ts.add(s4);
        ts.add(s5);
		//遍历集合
        for (Student student : ts) {
            System.out.println(student);
        }
    }
}

4.2.3 比较器排序Comparator的使用

案例需求：存入四个字符串， “c”, “ab”, “df”, “qwer”；按照长度排序，如果一样长则按照首字母排序（与默认的字符串规则不以言就需要重写比较器）

代码实现

    public static void main(String[] args) {

        //1.创建集合
        //o1:表示当前要添加的元素
        //o2：表示已经在红黑树存在的元素
        //返回值规则跟之前是一样的
        TreeSet<String> ts=new TreeSet<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                // 按照长度排序
                int i = o1.length() - o2.length();
                //如果一样长则按照首字母排序
                i = i == 0 ? o1.compareTo(o2) : i;
                return i;
            }
        });

//        TreeSet<String> ts = new TreeSet<>((o1, o2)->{
//                // 按照长度排序
//                int i = o1.length() - o2.length();
//                //如果一样长则按照首字母排序
//                i = i == 0 ? o1.compareTo(o2) : i;
//                return i;
//        });
;

        //2.添加元素
        ts.add("c");
        ts.add("ab");
        ts.add("df");
        ts.add("qwer");


        //3.打印集合
        System.out.println(ts);


    }

4.2.4 TreeSet对象排序练习题

需求：创建5个学生对象
属性：(姓名,年龄，语文成绩,数学成绩,英语成绩),
按照总分从高到低输出到控制台
如果总分一样，按照语文成绩排
如果语文一样，按照数学成绩排
如果数学成绩一样，按照英语成绩排
如果英文成绩一样，按照年龄排
如果年龄一样，按照姓名的字母顺序排
如果都一样，认为是同一个学生，不存。

第一种：默认排序/自然排序
第二种：比较器排序

代码示例：

学生类：

public class Student2 implements Comparable<Student2> {
    //姓名
    private String name;
    //年龄
    private int age;
    //语文成绩
    private int chinese;
    //数学成绩
    private int math;
    //英语成绩
    private int english;

//getter和setter

    public String toString() {
        return "Student2{name = " + name + ", age = " + age + ", chinese = " + chinese + ", math = " + math + ", english = " + english + "}";
    }

   /* 按照总分从高到低输出到控制台
    如果总分一样，按照语文成绩排
    如果语文一样，按照数学成绩排
    如果数学成绩一样，按照英语成绩排
    如果英文成绩一样，按照年龄排
    如果年龄一样，按照姓名的字母顺序排
    如果都一样，认为是同一个学生，不存。*/
    @Override
    public int compareTo(Student2 o) {
        int sum1 = this.getChinese() + this.getMath() + this.getEnglish();
        int sum2 = o.getChinese() + o.getMath() + o.getEnglish();

        //比较两者的总分
        int i = sum1 - sum2;
        //如果总分一样，就按照语文成绩排序
        i = i == 0 ? this.getChinese() - o.getChinese() : i;
        //如果语文成绩一样，就按照数学成绩排序
        i = i == 0 ? this.getMath() - o.getMath() : i;
        //如果数学成绩一样，按照英语成绩排序（可以省略不写）
        i = i == 0 ? this.getEnglish() - o.getEnglish() : i;
        //如果英文成绩一样，按照年龄排序
        i = i == 0 ? this.getAge() - o.getAge() : i;
        //如果年龄一样，按照姓名的字母顺序排序
        i = i == 0 ? this.getName().compareTo(o.getName()) : i;
        return i;
    }
}

测试类

    public static void main(String[] args) {

        //1.创建学生对象
        Student2 s1 = new Student2("zhangsan",23,90,99,50);
        Student2 s2 = new Student2("lisi",24,90,98,50);
        Student2 s3 = new Student2("wangwu",25,95,100,30);
        Student2 s4 = new Student2("zhaoliu",26,60,99,70);
        Student2 s5 = new Student2("qianqi",26,70,80,70);

        //2.创建集合
        TreeSet<Student2> ts = new TreeSet<>();

        //3.添加元素
        ts.add(s1);
        ts.add(s2);
        ts.add(s3);
        ts.add(s4);
        ts.add(s5);

        //4.打印集合
        //System.out.println(ts);
        for (Student2 t : ts) {
            System.out.println(t);
        }