学习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}