==知识点==
1.泛型
2.Set集合
3.TreeSet
4.数据结构-二叉树
5.数据结构-平衡二叉树
==用到的单词==
1.element[ˈelɪmənt]
要素 元素（软)
2.key[kiː]
计算机或打字机的) 键;
3.type[taɪp]
类型;
4.value[ˈvæljuː]
值
5.genericity
泛型
6.comparable[ˈkɒmpərəbl]
可比较的;
7.compare[kəmˈpeə(r)]
比较
8.comparator[kəmˈpɜrətər]
比较器
==重难点梳理==
==超详细讲义及源代码==
1.泛型
1.1泛型概述【了解】(视频01) （5‘’）
1.为什么要使用泛型(泛型的好处)
它提供了编译时类型安全检测机制,把运行时期的问题提前到了编译期间
避免了强制类型转换
package com.itheima.genericitysummarize;
import java.util.ArrayList;
import java.util.Iterator;
/**
* 不写泛型的弊端
*/
public class GenericitySummarize {
public static void main(String[] args) {
ArrayList list = new ArrayList();
list.add("aaa");
list.add3("bbb");
list.add("ccc");
list.add(123);
Iterator it = list.iterator();
while(it.hasNext()){
String next = (String) it.next();
int len = next.length();
System.out.println(len);
}
}
}
1.2泛型类的使用【重点】（视频02）
1.泛型用在什么地方(泛型可以使用的地方)
2.什么是泛型类（ArrayList<E>）
如果一个类的后面有<E> ，表示这个类是一个泛型类
public class ArrayList<E>
3.如何使用泛型类
创建泛型类对象时,必须要给这个泛型确定具体的数据类型
ArrayList<String> list=new ArrayList<>();
1.3 泛型-自定义泛型类(了解)（视频03）
1.如何定义泛型(泛型的定义格式)
-
<类型>: 指定一种类型的格式.
尖括号里面可以任意书写,一般只写一个字母.
例如: <E> <T><Q><M>
-
<类型1,类型2…>: 指定多种类型的格式,多种类型之间用逗号隔开.
例如: <E,T> <K,V><Q,M>
2.如何定义泛型类(泛型类格式)
定义格式
修饰符 class 类名<类型> { }
范例:
public class Generic<T> {},此处的T可以推荐使用常见的T,E,K,V等形式参数来表示泛型
示例代码
package com.itheima.genericityclass;
//就是一个泛型类
public class Box<E> {
private E element;
public E getElement() {
return element;
}
public void setElement(E element) {
this.element = element;
}
}
测试类
package com.itheima.genericityclass;
/**
* 自定义泛型类
*/
public class MyGenericityClass {
public static void main(String[] args) {
Box<String> box1 = new Box<>();
box1.setElement("给小丽的土味情话");
String element1 = box1.getElement();
System.out.println(element1);
Box<Integer> box2 = new Box<>();
box2.setElement(19);
Integer element2 = box2.getElement();
System.out.println(element2);
}
}
1.3泛型-泛型方法的使用【难点】(视频04)
1.什么是泛型方法
方法定义中在返回类型之前有泛型定义的方法，就是一个泛型方法
泛型方法的格式
public <T> T[] toArray•(T[] a){}
测试类
package com.itheima.genericitymethod;
import java.util.ArrayList;
import java.util.Arrays;
/**
* 使用Java中的泛型方法
*/
public class GenericityMethod1 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("给小花同学的土味情话");
list.add("给小丽同学的土味情话");
list.add("给小路同学的土味情话");
//将list集合转成一个数组并返回
//如果是空参的,那么返回的数组类型为Object类型的.
Object[] objects = list.toArray();
System.out.println(Arrays.toString(objects));
String[] strings = list.toArray(new String[list.size()]);
System.out.println(Arrays.toString(strings));
}
}
1.4 自定义泛型方法【了解】（视频05）
1.定义格式
修饰符 <类型> 返回值类型 方法名(类型 变量名) { }
范例: public <T> void show(){}
示例代码:
package com.itheima.genericitymethod;
import java.util.ArrayList;
/**
* 自定义泛型方法
* 定义一个泛型方法，传递一个集合和四个元素，将元素添加到集合中并返回
*/
public class GenericityMethod2 {
public static void main(String[] args) {
ArrayList<String> list1 = addElement(new ArrayList<String>(), "a", "b", "c", "d");
System.out.println(list1);
ArrayList<Integer> list2 = addElement(new ArrayList<Integer>(), 1, 2, 3, 4);
System.out.println(list2);
}
public static <T> ArrayList<T> addElement(ArrayList<T> list , T t1 ,T t2 ,T t3 ,T t4){
list.add(t1);
list.add(t2);
list.add(t3);
list.add(t4);
return list;
}
}
1.5泛型接口【难点】(视频06)
-
定义格式
修饰符 interface 接口名<类型> { } -
示例代码
package com.itheima.genericityinterface;
public class GenericityInterface {
public static void main(String[] args) {
GenericityImpl1<String> genericity = new GenericityImpl1<>();
genericity.method("小丽给我的土味情话");
GenericityImpl2 genericityImpl2 = new GenericityImpl2();
genericityImpl2.method(19);
}
}
interface Genericity<E>{
public abstract void method(E e);
}
class GenericityImpl2 implements Genericity<Integer>{
@Override
public void method(Integer integer) {
System.out.println(integer);
}
}
class GenericityImpl1<E> implements Genericity<E>{
@Override
public void method(E e) {
System.out.println(e);
}
}
1.5类型通配符【记忆】(视频07)
1.类型通配符的格式
<?>
2.泛型通配符的使用
1.类型通配符: <?>
ArrayList<?>: 表示元素类型未知的ArrayList,它的元素可以匹配任何的类型,但是并不能把元素添加到ArrayList中了,获取出来的也是父类类型
2.类型通配符上限: <? extends 类型>
ArrayList <? extends Number>: 它表示的类型是Number或者其子类型
3.类型通配符下限: <? super 类型>
ArrayListList <? super Number>: 它表示的类型是Number或者其父类型
public class Genericbobing{
public static void main(String[] args) {
ArrayList<Integer> list1 = new ArrayList<>();
ArrayList<String> list2 = new ArrayList<>();
ArrayList<Number> list3 = new ArrayList<>();
ArrayList<Object> list4 = new ArrayList<>();
printList(list1);
printList(list2);
method1(list1);
method1(list2);
method1(list3);
method1(list4);
method2(list1);
method2(list2);
method3(list3);
method4(list4);
}
// 泛型通配符: 此时的泛型?,可以是任意类型
public static void printList(ArrayList<?> list){}
// 泛型的上限: 此时的泛型?,必须是Number类型或者Number类型的子类
public static void method1(ArrayList<? extends Number> list){}
// 泛型的下限: 此时的泛型?,必须是Number类型或者Number类型的父类
public static void method2(ArrayList<? super Number> list){}
}
小结
1.为什么要使用泛型
使用泛型的目的就是为了类型安全，将类型问题从运行时提到编译时进行处理
2.什么是泛型
参数化类型，在使用用时，需要给具体的数据类型
3.怎么使用？
在创建声明或创建时给泛型类型指定具体的类型
4.用在哪里？
泛型类、泛型方法、泛型接口
5.泛型通配符
? 、? extends 父类或接口 （下限） ? super 父类或接口 （上限）
6.多态遇到泛型会怎么样?(扩展不需要讲)
ArrayList<Animal> alist= ArrayList<Dog> 对象？
ArrayList<Animal> alist=List<Animal>对象?
List<Animal> llist= ArrayList<Dog> 对象?
List<Animal> llist=ArrayList<Animal> 对象?
public static print(ArrayList<Animal> list) 是可否可以传ArrayList<Dog>对象?
2.Set集合
2.1Set概述【了解】(视频08)
2.2Set集合的基本使用【重点】（视频09）
1.Set集合的特点
不可以存储重复元素
存取顺序不一致
没有索引
2.Set集合的使用
package com.itheima.myset;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
/**
* Set集合的基本使用
*/
public class MySet1 {
public static void main(String[] args) {
Set<String> set = new TreeSet<>();
set.add("ccc");
set.add("aaa");
set.add("aaa");
set.add("bbb");
// for (int i = 0; i < set.size(); i++) {
// //Set集合是没有索引的，所以不能使用通过索引获取元素的方法
// }
Iterator<String> it = set.iterator();
while (it.hasNext()){
String s = it.next();
System.out.println(s);
}
System.out.println("-----------------------------------");
for (String s : set) {
System.out.println(s);
}
}
}
3.TreeSet集合
3.1TreeSet-基本使用【重点】（视频10）
1.TreeSet的特点
不可以存储重复元素
没有索引
可以将元素按照规则进行排序
2.TreeSet的使用
package com.itheima.mytreeset;
import java.util.TreeSet;
/**
* TreeSet集合来存储Integer类型
*/
public class MyTreeSet1 {
public static void main(String[] args) {
TreeSet<Integer> ts = new TreeSet<>();
ts.add(5);//自动装箱
ts.add(3);
ts.add(4);
ts.add(1);
ts.add(2);
System.out.println(ts);
}
}
存储Student对象
package com.itheima.mytreeset;
import java.util.TreeSet;
/**
* TreeSet集合来存储Student类型
*/
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);
System.out.println(ts);
}
}
Student对象
package com.itheima.mytreeset;
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 +
'}';
}
}
Exception in thread "main" java.lang.ClassCastException: class com.itheima.mytreeset.Student cannot be cast to class java.lang.Comparable (com.itheima.mytreeset.Student is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
at java.base/java.util.TreeMap.compare(TreeMap.java:1291)
at java.base/java.util.TreeMap.put(TreeMap.java:536)
at java.base/java.util.TreeSet.add(TreeSet.java:255)
at com.itheima.mytreeset.MyTreeSet2.main(MyTreeSet2.java:18)
3.3自然排序Comparable的使用【重点】(视频11)
案例需求
存储学生对象并遍历，创建TreeSet集合使用无参构造方法
要求：按照年龄从小到大排序
提示:
//o - 要比较的对象
//将此对象与指定的对象进行比较以进行排序。 返回一个负整数，零或正整数，因为该对象小于，等于或大于指定对象
public int compareTo(T o);
实现步骤
-
使用空参构造创建TreeSet集合
用TreeSet集合存储自定义对象，无参构造方法使用的是自然排序对元素进行排序的
-
自定义的Student类实现Comparable接口
自然排序，就是让元素所属的类实现Comparable接口，重写compareTo(T o)方法
-
重写接口中的compareTo方法
重写方法时，一定要注意排序规则必须按照要求的主要条件和次要条件来写
代码实现
学生类
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 +
'}';
}
/***
* 比较两个对象的大小
* @param o 表示集合中的元素
* @return 如果是正值，表示要存入的当前对象大，放右边
* 如果是负值，表示要存入的当前对象小，入左边
* 如果返回0, 表示两个对象相等，不存
*/
@Override
public int compareTo(Student o) {
//按照对象的年龄进行排序
//主要判断条件
int result = this.age - o.age;//年龄小的放前面，年龄大的放后面，从小到大排
return result;
}
}
测试类
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);
}
}
}
3.4 自然排序练习(视频12)【重点】
案例需求
存储学生对象并遍历，创建TreeSet集合使用无参构造方法
要求：按照年龄从小到大排序，如果年龄相同，将按姓名的首字母来进行排序
package com.itheima.mytreeset;
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 +
'}';
}
/***
* 比较两个对象的大小
* @param o 表示集合中的元素
* @return 如果是正值，表示要存入的当前对象大，放右边
* 如果是负值，表示要存入的当前对象小，入左边
* 如果返回0, 表示两个对象相等，不存
*/
@Override
public int compareTo(Student o) {
//按照对象的年龄进行排序
//主要判断条件
int result = this.age - o.age;
//次要判断条件
//如果result==0的结果为真，result=this.name.compareTo(o.getName())
//如果result==0的结果为假 result=result;
result = result == 0 ? this.name.compareTo(o.getName()) : result;
//返回result的结果
return result;
}
}
测试类
package com.itheima.mytreeset; import java.util.TreeSet; /**
* TreeSet集合来存储Student类型
*/
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); System.out.println(ts);
}
}
3.5比较器排序Comparator的使用【重点】(视频13)
-
案例需求
存储老师对象并遍历，创建TreeSet集合使用带参构造方法
要求：按照年龄从小到大排序，年龄相同时，按照姓名的字母顺序排序
提示
int compare(T o1,T o2)
比较其两个参数的顺序。 返回负整数，零或正整数，因为第一个参数小于，等于或大于第二个参数
-
实现步骤
用TreeSet集合存储自定义对象，带参构造方法使用的是比较器排序对元素进行排序的
比较器排序，就是让集合构造方法接收Comparator的实现类对象，重写compare(T o1,T o2)方法
重写方法时，一定要注意排序规则必须按照要求的主要条件和次要条件来写
-
代码实现
老师类
public class Teacher {
private String name;
private int age; public Teacher() {
} public Teacher(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 "Teacher{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}测试类
package com.itheima.mytreeset; import java.util.Comparator;
import java.util.TreeSet; public class MyTreeSet4 {
public static void main(String[] args) {
TreeSet<Teacher> ts = new TreeSet<>(
new Comparator<Teacher>() {
/***
* 比较两个对象的大小
* @param o1 表示要存入的元素
* @param o2 表示已经存入到集合中的元素
* @return 如果是正值，表示要存入的当前对象大，放右边
* 如果是负值，表示要存入的当前对象小，入左边
* 如果返回0, 表示两个对象相等，不存
*/
@Override
public int compare(Teacher o1, Teacher o2) {
//o1表示现在要存入的那个元素
//o2表示已经存入到集合中的元素 //主要条件
int result = o1.getAge() - o2.getAge();
//次要条件
result = result == 0 ? o1.getName().compareTo(o2.getName()) : result;
return result;
}
});
Teacher t1 = new Teacher("zhangsan",23);
Teacher t2 = new Teacher("lisi",22);
Teacher t3 = new Teacher("wangwu",24);
Teacher t4 = new Teacher("zhaoliu",24); ts.add(t1);
ts.add(t2);
ts.add(t3);
ts.add(t4); System.out.println(ts);
}
}
3.5两种比较方式总结【了解】（视频14）
1.不同点
1.用到的接口不同
自然排序: 自定义类实现Comparable接口,重写compareTo方法,根据返回值进行排序
比较器排序: 创建TreeSet对象的时候传递Comparator的实现类对象,重写compare方法,根据返回值进行排序
2.使用场景不同
自然排序能满足大部分情况
当存储的元素类型中的比较规则 ，不满足需要，但是没法重写compareTo方法时可以使用(例如:改变包装类Integer的比较规则，让其从大到小)比较器排序
2.相同点
返回值的规则:
如果返回值为负数，表示当前存入的元素是较小值，存左边
如果返回值为0，表示当前存入的元素跟集合中元素重复了，不存
如果返回值为正数，表示当前存入的元素是较大值，存右边
package com.itheima.mytreeset; import java.util.Comparator;
import java.util.TreeSet; public class MyTreeSet5 {
public static void main(String[] args) {
// TreeSet<String> ts = new TreeSet<>(new Comparator<String>() {
// @Override
// public int compare(String o1, String o2) {
// int result = o1.length() - o2.length();
// result = result == 0 ? o1.compareTo(o2) : result;
// return result;
// }
// }); TreeSet<String> ts = new TreeSet<>(
(String o1, String o2) -> {
int result = o1.length() - o2.length();
result = result == 0 ? o1.compareTo(o2) : result;
return result;
}
); ts.add("c");
ts.add("ab");
ts.add("df");
ts.add("qwer"); System.out.println(ts);
}
}
4.数据结构
4.1二叉树【了解】(视频15)
1.二叉树中的专业名司(共5个)
1.节点
2.度
3.什么是二叉树
4.什么是二叉树的树高
二叉树的层高就是二叉树的树高
5.二叉树中的其它专业名词
4.2二叉查找树【了解】（视频16）
(共三点)
1.什么是二叉查找树
2.节点到二叉树再到二叉查找树的演进
3.二叉查找树结构图
4.3 数据结构-二叉查找树添加节点（了解）(视频17)
1.添加规则
小的存左边
大的存右边
一样的不存
4.4平衡二叉树【了解】(视频18)
-
什么是平衡叉树
4.5 平衡二叉树-左旋 （视频19）【了解】
1.平衡二叉树旋转触发的时机
当添加一个节点之后,该树不再是一颗平衡二叉树
2.左旋
就是将根节点的右侧往左拉,原先的右子节点变成新的父节点,并把多余的左子节点出让,给已经降级的根节点当右子节点
4.6 平衡二叉树-右旋 (视频20) 【了解】
-
就是将根节点的左侧往右拉,左子节点变成了新的父节点,并把多余的右子节点出让,给已经降级根节点当左子节点
4.7 平衡二叉树-小结(了解) (视频21)
（共3点）
1.二叉查找树和平衡二叉树
平衡二叉树和二叉查找树对比结构图
2.左旋
3.右旋
4.8 平衡二叉树-左左和左右（视频22）【了解】
-
左左
左左: 当根节点左子树的左子树有节点插入,导致二叉树不平衡
-
如何旋转: 直接对整体进行右旋即可
-
左右
左右: 当根节点左子树的右子树有节点插入,导致二叉树不平衡
如何旋转: 先在左子树对应的节点位置进行左旋,在对整体进行右旋
4.9 平衡二叉树-右右和右左 (视频23) 【了解】
-
右右
右右: 当根节点右子树的右子树有节点插入,导致二叉树不平衡
-
如何旋转: 直接对整体进行左旋即可
-
右左
右左:当根节点右子树的左子树有节点插入,导致二叉树不平衡
-
如何旋转: 先在右子树对应的节点位置进行右旋,在对整体进行左旋
4.10 小结(视频24) 【了解】
==扩展练习==
编程题【Set接口】
题目1
已知数组信息如下:
{2.2,5.5,6.6,2.2,8.8,1.1,2.2,8.8,5.5,2.2,6.6}
请使用代码找出上面数组中的所有的数据,要求重复的数据只能保留一份;
要求:
使用HashSet集合实现;
效果:
参考答案:
public static void main(String[] args) {
double[] arr = {2.2,5.5,6.6,2.2,8.8,1.1,2.2,8.8,5.5,2.2,6.6};
HashSet<Double> set = new HashSet<>();
for (double v : arr) {
set.add(v);
}
System.out.println("去除重复的元素后,结果是:"+set);
}
题目2
随机生成8个不重复的10至20之间的随机数并保存Set集合中,然后打印出集合中所有的数据;
要求:
使用TreeSet集合实现;
效果:
(由于是随机的,所以每次运行结果都不一样是正常的!!!)
参考答案:
public static void main(String[] args) {
TreeSet<Integer> set = new TreeSet<>();
Random r = new Random();
int count =1;
while (set.size()<8){
int i = r.nextInt(20 - 10 + 1) + 10;
System.out.println("第"+count++ +"次生成的随机数是:"+i);
set.add(i);
}
System.out.println("集合中保存的8个不重复的随机数是:"+set);
}
题目3
键盘输入3本书按照价格从低到高排序后输出,如果价格相同则按照书名的自然顺序排序;
要求:
1:书以对象形式存在,包含书名和价格(int类型)两个属性;
2:要求即使直接打印书对象的时候,也能看到书的名称和价格,而不是书对象的地址值;
3:分别使用自然排序和比较器排序实现效果;
效果:
参考答案:
测试类:
package day8.No_3.test2;
import java.text.Collator;
import java.util.Comparator;
import java.util.Locale;
import java.util.Scanner;
import java.util.TreeSet;
public class Demo {
public static void main(String[] args) {
TreeSet<Book> ts = new TreeSet<>(new Comparator<Book>() {
@Override
public int compare(Book o1, Book o2) {
int i = o1.getPrice() - o2.getPrice();
Collator instance = Collator.getInstance(Locale.CHINESE);
i=i==0?instance.compare(o1.getName(),o2.getName()):i;
return i;
}
});
Scanner sc = new Scanner(System.in);
int count = 1;
L:while (true) {
sc = new Scanner(System.in);
System.out.println("请输入第" + count + "本书名:");
String name = sc.next();
int jiage;
while (true){
sc = new Scanner(System.in);
System.out.println("请输入价格:");
try {
jiage = sc.nextInt();
break;
} catch (Exception e) {
System.out.println("必须为整数!");
continue;
}
}
Book book = new Book(name, jiage);
ts.add(book);
System.out.println("第" + count + "本书添加成功,输入1继续,其他退出");
count++;
int i = 0;
try {
i = sc.nextInt();
} catch (Exception e) {
}
if (i != 1) {
break L;
}
}
System.out.println("你一共添加" + ts.size() + "本书:");
for (Book t : ts) {
System.out.println(t);
}
}
}
类文件:
package day8.No_3.test2;
import java.text.Collator;
import java.util.Locale;
public class Book {
private String name;
private int price;
public Book() {
}
public Book(String name, int price) {
this.name = name;
this.price = price;
}
@Override
public String toString() {
return "Book{" +
"name='" + name + '\'' +
", price=" + price +
'}';
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getPrice() {
return price;
}
public void setPrice(int price) {
this.price = price;
}
}