TreeSet集合实现自动排序的要求 平衡二叉树 Collections工具类
Map集合的key和Set集合存储元素的特点相同（无序，不可重复），Map集合的key，就是一个Set集合，往Set集合中放数据，实际上放到Map集合的key部分
1. Hashtable类的子类是Properties
- 了解Hashtable类：实现Map接口，底层采取了哈希表这种数据结构，是线程安全的，使用较少。Hashtable类的子类是Properties：底层采取了哈希表这种数据结构，表示一个持久的属性集，存储元素时，也是采取key和value的形式，属性列表中每个键及其对应值都是一个字符串。
- HashMap集合的key和value允许null 而Hashtable集合的key和value都不允许是null ; HashMap集合的默认初始化容量是16, 扩容之后的容量是原容量的2倍，(HashSet与HashMap集合以上相同)而Hashtable集合的初始化容量是11，扩容之后的容量是原容量的2倍再加1
package 集合练习;
import java.util.Properties;
public class Tree1 {
public static void main(String[] args) {
//创建一个Properties对象
Properties p = new Properties();
//Properties的key和value都是String
//掌握两个方法：存 和 取
p.setProperty("1", "diyi"); //底层调用是Map中的put(k,v)方法
p.setProperty("2", "dier");
p.setProperty("3", "disan");
//通过key来获取value /* public String getProperty(String key) */
System.out.println(p.getProperty("1"));
System.out.println(p.getProperty("2"));
System.out.println(p.getProperty("3"));
}
/*diyi
dier
disan
*/
}
2. TreeSet集合对放在其中的元素实现可自动排序的条件：实现comparable接口，并且实现接口中的compareTo方法，定义的比较规则写在此方法中
- SortedSet接口：由于继承了Set接口，其特点有无序不可重复，没有下标，但放在SortedSet集合中的 元素可以自动排序 ，我们成为可排序集合
- SortedSet接口的实现类的 TreeSet类：底层采取了二叉树这种数据结构， 实际上TreeSet集合在new的时候，底层是new了一个TreeMap集合，向TreeSet集合存储元素，实际上是存储到TreeMap集合中的key部分了
- SortedMap接口：由于SortedMap集合是Map接口的子接口，key都是无序不可重复的，同时，放在SortedMap集合key部分的元素会自动按照大小顺序排序，成为可排序的集合
- SortedMap接口的实现类有TreeMap类：底层采取了二叉树这种数据结构，key部分的元素自然会自动按照大小顺序排序。
1. String类和Integer类都已经实现了comparable接口
package 集合练习;
import java.util.TreeSet;
public class Tree1 {
public static void main(String[] args) {
//创建一个TreeSet集合
TreeSet tree = new TreeSet<>();
//添加元素
tree.add("aiki");
tree.add("wigi");
tree.add("dika");
tree.add("aike");
//遍历
for(String i :tree) {
System.out.println(i);/*对于String,对于出现的第一个不同字符按照在字典中的顺序比较，剩下的字符不参与比较*/
}
//创建一个TreeSet集合
TreeSet tree1 = new TreeSet<>();
tree1.add(1);
tree1.add(4);
tree1.add(0);
//遍历
for(Integer i:tree1) {
System.out.println(i);
}
}
/*
aike
aiki
dika
wigi
0
1
4
*/
}
2. 对于自定义的类，要实现TreeSet集合中元素的排序，要实现comparable接口，并自定义比较规则
package 集合练习;
import java.util.TreeSet;
public class Tree1 {
public static void main(String[] args) {
Student1 s1 = new Student1(10);
Student1 s2 = new Student1(50);
Student1 s3 = new Student1(30);
Student1 s4 = new Student1(90);
//创建一个TreeSet集合
TreeSet tree = new TreeSet<>();
//添加元素
tree.add(s1);
tree.add(s2);
tree.add(s3);
tree.add(s4);
//遍历
for(Student1 i :tree) {
System.out.println(i); //直接输出引用，会调用toString 方法
}
}
/*
Student1 [age=10]
Student1 [age=30]
Student1 [age=50]
Student1 [age=90]
*/
}
//自定义类
class Student1 implements Comparable {
int age;
public Student1(int age) {
super();
this.age = age;
}
//实现comparable接口中的方法compareTo
//c1.compareTo(c2) this指的是c1 方法的参数就是c2 返回值可能是 >0 <0 =0
@Override
public int compareTo(Student1 o) {
return this.age-o.age;
}
//重写toString 方法
@Override
public String toString() {
return "Student1 [age=" + age + "]";
}
}
/*对于自定义的类，若没有实现comparable接口，并自定义比较规则，就会出现异常：
* java.lang.ClassCastException*/
若要求：先按照年龄升序，如果年龄一样的在按照姓名升序：
/*
* @Override
public int compareTo(Student1 o) {
if(this.age == o.age){
return this.name.comepareTo(o.name);//因为姓名是String类型，直接比
}
else{
return this.age-o.age;
}
}*/
3. 平衡二叉树
1. 回顾：
- 二叉树每个结点至多只有两个子树（即每个结点的度不大于2）
- 遍历二叉树：按照先左后右，分
先（根）序遍历：根左右
中（根）序遍历：左根右
后（根）序遍历：左右根 - 二叉排序树：（左小右大）
若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值
若它的右子树不空，则左子树上所有结点的值均大于它的根节点的值
它的左右子树也是二叉排序树
中序遍历一棵二叉排序树可以得到有序递增的结点序列 - 平衡二叉树，是一种特殊的二叉排序树
左右子树的深度之差的绝对值不超过1，若将二叉树上结点的平衡因子定义为该结点左子树和右子树深度之差，则平衡二叉树上所有结点的平衡因子只可能是-1,0和1
树的深度/高度：树中结点的最大层次
层次：结点的层次从根节点开始定义起，根为第一层
2. TreeSet/TreeMap是平衡二叉树，遵循左小右大原则存放，对集合遍历采取：左根右的中序遍历
所以，上方往TreeSet集合中存放元素时，底层是平衡二叉树，会调用compareTo方法，存放的过程就是排序的过程，取出来就是中序遍历的有序递增
对于compareTo的返回值：
返回0,表示相同，value会覆盖
返回<0,会继续在左子树上找
返回>0, 会继续在右子树上找
只不过对于String类和Integer类可以直接比较，但自己定义类，要在compareTo方法中写明比较规则
4.TreeSet集合/TreeMap集合中的key部分 中元素可排序的第二种方式：在构造TeeSet/TreeMap集合时传一个比较器对象; 单独编写一个比较器类/匿名内部类，实现Comparator接口，并实现其中的方法compare，在其中自定义比较规则；
package 集合练习;
import java.util.Comparator;
import java.util.TreeSet;
public class Tree1 {
public static void main(String[] args) {
Student1 s1 = new Student1(10);
Student1 s2 = new Student1(50);
Student1 s3 = new Student1(30);
Student1 s4 = new Student1(90);
//创建一个TreeSet集合,需要使用这个比较器，使用有参构造，传一个比较器实例传进去
TreeSet tree = new TreeSet<>(new StuComparator());
/*也可以采用匿名内部类的方式,使用有参构造，直接new Comparator<泛型>() 接口传进去
TreeSet tree = new TreeSet<>(new Comparator(){
@Override
public int compare(Student1 o1, Student1 o2) {
return o1.age-o2.age;
}});
*/
//添加元素
tree.add(s1);
tree.add(s2);
tree.add(s3);
tree.add(s4);
//遍历
for(Student1 i :tree) {
System.out.println(i); //直接输出引用，会调用toString 方法
}
}
/*
Student1 [age=10]
Student1 [age=30]
Student1 [age=50]
Student1 [age=90]
*/
}
//自定义类
class Student1 {
int age;
public Student1(int age) {
super();
this.age = age;
}
//重写toString 方法
@Override
public String toString() {
return "Student1 [age=" + age + "]";
}
}
//单独编写一个比较器,是个类
//比较器实现java.util.Comparator接口(Comparable是java.lang包下的，Comparator是java.util包下的)
//要实现Comparator接口中的compare方法，指定比较规则
class StuComparator implements Comparator{
@Override
public int compare(Student1 o1, Student1 o2) {
return o1.age-o2.age;
}
}
comparable接口和Comparator接口如何选择？
当比较规则不会发生改变的时候，或者当比较规则只有一个的时候，建议实现 comparable接口。像String类和Integer类比较规则固定，所以都实现此接口
反之，
当比较规则频繁发生改变的时候，或者当比较规则有多个的时候，建议实现 Comparator接口。
5.Collections集合工具类
package 集合练习;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Collection {
public static void main(String[] args) {
//ArrayList集合不是线程安全的
List list = new ArrayList<>();
list.add("ade");
list.add("abe");
list.add("abf");
list.add("ax");
//1.变成线程安全的
Collections.synchronizedList(list);//参数时List集合
//2.排序
Collections.sort(list);//参数时List集合(但前提是：需要保证List集合中的元素（所对应的类型）实现了Comparable接口,当然，也有另一种方法：sort(List集合，比较器对象))
for(String i:list) {
System.out.println(i);
}
/*
abe
abf
ade
ax*/
//那对Set集合如何排序呢？因为Collections.sort(参数是List集合)
Set set = new HashSet<>();
set.add("abc");
set.add("axc");
set.add("bbc");
//将Set集合转为List集合：
List list2 = new ArrayList<>(set);
Collections.sort(list2);
for(String i:list2) {
System.out.println(i);
}
/*
abc
axc
bbc
*/
}
}