JAVA基础-树和Set集合
文章目录
- 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
- 节点: 在树结构中,每一个元素称之为节点
- 度: 每一个节点的子节点数量称之为度
- 二叉树中,任意一个节点的度要小于等于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 红黑树
它是一种特殊的二叉查找树,红黑树的每一个节点上都有存储位表示节点的颜色
每一个节点可以是红或者黑;红黑树不是高度平衡的,它的平衡是通过"红黑规则"进行实现的
-
红黑树的红黑规则有哪些
-
每一个节点或是红色的,或者是黑色的
-
根节点必须是黑色
-
如果一个节点没有子节Z点或者父节点,则该节点相应的指针属性值为Nil,这些Nil视为叶节点,每个叶节点(Nil)是黑色的
-
如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)
-
对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点
-
-
红黑树添加节点的默认颜色
-
添加节点时,默认为红色,效率高
-
-
红黑树添加节点后如何保持红黑规则
- 根节点位置
- 直接变为黑色
- 非根节点位置
- 父节点为黑色
- 不需要任何操作,默认红色即可
- 父节点为红色
- 叔叔节点为红色
- 将"父节点"设为黑色,将"叔叔节点"设为黑色
- 将"祖父节点"设为红色
- 如果"祖父节点"为根节点,则将根节点再次变成黑色
- 叔叔节点为黑色
- 将"父节点"设为黑色
- 将"祖父节点"设为红色
- 以"祖父节点"为支点进行旋转
- 叔叔节点为红色
- 父节点为黑色
- 根节点位置
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方法,不同的对象只要属性值相同,计算出的哈希值就是一样的
- 在小部分情况下,不同的属性值或者不同的地址值,计算出来的哈希值也有可能一样(哈希碰撞)
哈希值的代码示例:
- JDK8之前:数组+链表
//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);
}