学习JAVA的第十五天（基础）
目录
数据结构
二叉树
二叉查找树
平衡二叉树
红黑树
Set系列集合
HashSet集合
LinkedHashSet集合
TreeSet集合
前言：学习JAVA的第十四天（基础）-CSDN博客
数据结构
二叉树
元素：结点（节点）
度：每个节点的子节点数量
二叉树：度<=2
树高：树的总层数
根节点：最顶部的节点
左子结点：左下方的节点
右子节点：右下方的节点
二叉查找树
特点：
每个节点最多有2个子节点
任意节点左子树上的值小于当前节点
任意节点右子树上的值大于当前节点
添加节点：
小的存左边、大的存右边、一样的不存
遍历方式：
①前序遍历
②中序遍历
③ 后序遍历
④ 层序遍历
前序遍历
从根节点开始，按照当前节点、左子节点、右子节点的顺序遍历
中序遍历
从最左边的子节点开始，按照左子节点、当前节点、右子节点的顺序遍历
后序遍历
从最左边的子节点开始，按照左子节点、、右子节点、当前节点的顺序遍历
层序遍历
从根节点开始，一层一层遍历
平衡二叉树
规则： 任意节点的左右子树高度差不超过1
旋转机制
当添加一个节点时，该树不是一个平衡二叉树
左旋
确认支点：从添加的节点开始，不断的从父节点中找出不平衡的节点
步骤：不平衡节点作为支点。将支点左旋降级，变成左子节点。晋升原来的右子节点
右旋
确认支点：从添加的节点开始，不断的从父节点中找出不平衡的节点
步骤：不平衡节点作为支点。将支点右旋降级，变成右子节点。晋升原来的左子节点
红黑树
特征：
红黑树是一种自平衡的二叉树
每个节点可以是红或黑，红黑树不是高度平衡的，它的平衡是通过“红黑规则”实现
红黑规则：
①每个节点是红色或者是黑色的
②根节点必须是黑色的
③如果一个节点没有子节点或者父节点，则该节点的指针属性值为Nil，这些Nil会视为叶节点，每个叶节点是黑色的
④如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连)
⑤对每一个节点，从该节点到其所有后代叶节点的简单路径.上,均包含相同数目的黑色节点
添加节点：
默认是红色（效率高）
Set系列集合
特点：
无序：存取顺序不一致
不重复：可以用来去重
无索引： 不能用索引遍历元素
Set实现类：
- HashSet：无序、不重复、无索引
- LinkedHashSet：有序、不重复、无索引
- TreeSet：可排序、不重复、无索引
Set集合遍历测试类
public static void main(String[] args) {//创建Set集合对象 利用多态Set<String> s = new HashSet<>();//添加元素s.add("aaa");s.add("bbb");s.add("ccc");//打印集合System.out.print(s);//[aaa, ccc, bbb]//创建迭代器对象Iterator<String> it = s.iterator();while (it.hasNext()){System.out.print(it.next());//aaacccbbb}//增强for遍历for(String str : s) {System.out.print(str);//aaacccbbb}System.out.println();//利用Lambda表示式遍历s.forEach(new Consumer<String>() {@Overridepublic void accept(String str) {System.out.print(str);}});//简化Lambda表达式s.forEach(str -> System.out.print(str));//aaacccbbb}HashSet集合
解释：底层是用哈希表存储数据的
哈希表：
JDK8之前：数组+链表
JDK8开始：数组+链表+红黑树
哈希值：对象的整数表现形式
- 根据hashCode方法算出来的int类型整数
- 该方法定义在Object中，所有对象都可以调用，默认使用地址值计算哈希值
- 一般情况下，会重写hashCode方法，利用对象内部的属性值计算哈希值
测试类
public static void main(String[] args) {//创建对象Student s1 = new Student("zhj",32);Student s2 = new Student("zhj",32);//哈希值System.out.println(s1.hashCode());//2133927002System.out.println(s2.hashCode());//1836019240}LinkedHashSet集合
原理：底层数据结构依然是哈希表，只是每个元素又多了双链表的机制记录存储数据的顺序
测试类
public static void main(String[] args) {//创建对象Student s1 = new Student("aaa",12);Student s2 = new Student("bbb",15);Student s3 = new Student("ccc",18);Student s4 = new Student("ddd",42);//创建集合的对象LinkedHashSet<Student> lhs = new LinkedHashSet<>();System.out.println(lhs.add(s3));//trueSystem.out.println(lhs.add(s2));//trueSystem.out.println(lhs.add(s1));//trueSystem.out.println(lhs.add(s4));//trueSystem.out.println(lhs);//[Student{name='ccc', age=18}, Student{name='bbb', age=15}, Student{name='aaa', age=12}, Student{name='ddd', age=42}]}TreeSet集合
特点：可排序（默认情况按照从小到大排列）、无索引、不重复
实现：TreeSet集合底层是基于红黑树的数据结构进行排序的
测试类：
public static void main(String[] args) {//创建TreeSet集合对象TreeSet<Integer> ts = new TreeSet<>();//添加元素ts.add(4);ts.add(8);ts.add(1);ts.add(3);ts.add(2);//打印数据System.out.println(ts);//[1, 2, 3, 4, 8]//迭代器遍历Iterator<Integer> it = ts.iterator();while(it.hasNext()){System.out.print(it.next());//12348}//增强for遍历for (Integer t : ts) {System.out.print(t);//12348}//实现类ts.forEach(new Consumer<Integer>() {@Overridepublic void accept(Integer integer) {System.out.print(integer);//12348}});//Lambda表达式简化ts.forEach(integer -> System.out.print(integer));//12348}