上海网站建站建设,五金网站制作,域名服务商网站,做外贸的社交网站有哪些目录
数据结构
二叉树
二叉查找树
平衡二叉树
红黑树
Set系列集合
HashSet集合
LinkedHashSet集合
TreeSet集合 前言#xff1a;学习JAVA的第十四天#xff08;基础#xff09;-CSDN博客 数据结构 二叉树 元素#xff1a;结点学习JAVA的第十四天基础-CSDN博客 数据结构 二叉树 元素结点节点 度每个节点的子节点数量 二叉树度2 树高树的总层数 根节点最顶部的节点 左子结点左下方的节点 右子节点右下方的节点 二叉查找树
特点 每个节点最多有2个子节点 任意节点左子树上的值小于当前节点 任意节点右子树上的值大于当前节点
添加节点 小的存左边、大的存右边、一样的不存
遍历方式 ①前序遍历 ②中序遍历 ③ 后序遍历 ④ 层序遍历
前序遍历 从根节点开始按照当前节点、左子节点、右子节点的顺序遍历
中序遍历 从最左边的子节点开始按照左子节点、当前节点、右子节点的顺序遍历
后序遍历 从最左边的子节点开始按照左子节点、、右子节点、当前节点的顺序遍历
层序遍历 从根节点开始一层一层遍历 平衡二叉树 规则 任意节点的左右子树高度差不超过1
旋转机制 当添加一个节点时该树不是一个平衡二叉树
左旋 确认支点从添加的节点开始不断的从父节点中找出不平衡的节点 步骤不平衡节点作为支点。将支点左旋降级变成左子节点。晋升原来的右子节点
右旋 确认支点从添加的节点开始不断的从父节点中找出不平衡的节点 步骤不平衡节点作为支点。将支点右旋降级变成右子节点。晋升原来的左子节点 红黑树
特征 红黑树是一种自平衡的二叉树 每个节点可以是红或黑红黑树不是高度平衡的它的平衡是通过“红黑规则”实现
红黑规则 ①每个节点是红色或者是黑色的 ②根节点必须是黑色的 ③如果一个节点没有子节点或者父节点则该节点的指针属性值为Nil这些Nil会视为叶节点每个叶节点是黑色的
④如果某一个节点是红色那么它的子节点必须是黑色(不能出现两个红色节点相连)
⑤对每一个节点从该节点到其所有后代叶节点的简单路径.上,均包含相同数目的黑色节点
添加节点 默认是红色效率高 Set系列集合 特点 无序存取顺序不一致 不重复可以用来去重 无索引 不能用索引遍历元素
Set实现类
HashSet无序、不重复、无索引LinkedHashSet有序、不重复、无索引TreeSet可排序、不重复、无索引
Set集合遍历测试类 public static void main(String[] args) {//创建Set集合对象 利用多态SetString s new HashSet();//添加元素s.add(aaa);s.add(bbb);s.add(ccc);//打印集合System.out.print(s);//[aaa, ccc, bbb]//创建迭代器对象IteratorString 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 ConsumerString() {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);//创建集合的对象LinkedHashSetStudent 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{nameccc, age18}, Student{namebbb, age15}, Student{nameaaa, age12}, Student{nameddd, age42}]} TreeSet集合 特点可排序默认情况按照从小到大排列、无索引、不重复
实现TreeSet集合底层是基于红黑树的数据结构进行排序的
测试类 public static void main(String[] args) {//创建TreeSet集合对象TreeSetInteger 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]//迭代器遍历IteratorInteger 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 ConsumerInteger() {Overridepublic void accept(Integer integer) {System.out.print(integer);//12348}});//Lambda表达式简化ts.forEach(integer - System.out.print(integer));//12348}
