java学习day6--数据结构（树）+Set

polopd

649人浏览 · 2026-01-31 14:37:10

polopd · 2026-01-31 14:37:10 发布

二叉查找树

任意节点左子树上的值都小于当前节点。

任意节点右子树上的值都大于当前节点

并且这是一个二叉树（任意节点的度<=2）。

二叉查找树添加节点的规则：小的存左边，大的存右边，一样就不存。

二叉树的遍历方式

1.前序遍历

从根节点开始，按照当前节点，左子节点，右子节点的顺序遍历

2.中序遍历（最重要，最为常用）

从最左边子节点开始，按照左子节点，当前节点，右子节点的顺序遍历

3.后序遍历

从最左边子节点开始，按照左子节点，右子节点，当前节点的顺序遍历

4.层序遍历

从根节点开始，一层一层遍历

平衡二叉树

针对二叉查找树可能出现左子树和右子树长度相差过大的情况

新增了一个规则：任意节点的左右子树高度差不超过1。

平衡二叉树如何实现平衡：

当添加一个数据，让原先的平衡二叉树不再平衡，会触发左旋（右旋）机制，使二叉树恢复平衡。

1.旋转时需要确定支点，从添加的结点开始，不断往父节点找，找到第一个不平衡的节点作为支点

2.把支点左旋降级，把支点变成左子节点，原来的右子节点晋升为父节点，支点的左子节点给降级的根节点当右子节点。

平衡二叉树需要旋转的四种情况。

1.左左：根节点左子树的左子树有节点插入，导致二叉树不平衡。进行一次右旋解决

2.左右：根节点左子树的右子树有节点插入，导致二叉树不平衡。要先进行局部的左旋，将根节点左子树变为左左的情况，再进行一次右旋

3.右右：根节点右子树的右子树有节点插入，导致二叉树不平衡。进行一次左旋。

4.右左：根节点右子树的左子树有节点插入，导致二叉树不平衡。局部右旋，再整体左旋。

红黑树

是一个二叉查找树，但是不是高度平衡的，具有特有的红黑规则。

根节点必须是黑色。

一个节点若没有子节点或父节点，则该节点指针属性值为Nil，视为叶节点，叶节点为黑色。

若某一个节点是红色，那么他的子节点不许是黑色。

对每一个节点，从该节点到其后代叶节点的简单路径上，包含相同数目的黑色节点。

添加节点时1，默认节点为红色，因为添加为红色时，添加效率高。

下面这个图是黑马的图：我觉得非常清晰

Set

Set系列集合添加的元素无序，无重复，无索引。

有三个实现类：HashSet 无序，不重复，无索引

LinkedHashSet 有序，不重复，无索引

TreeSet 可排序，不重复，无索引

Set集合的遍历

因为Set是继承的Collection，因此其可以使用collection的各种方法。

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.function.Consumer;

public class SetDemo {
    public static void main(String[] args) {

        Set<String> set = new HashSet<>();

        //注意set集合不允许数值重复，要注意此时.add方法返回的布尔值
        set.add("aaa");
        set.add("aaa");//这里的第二个add方法会false，添加失败
        set.add("bbb");
        set.add("ccc");

        System.out.println(set);//并且此时输出的结果与添加的顺序无关，可能是无序的


        //迭代器遍历
        Iterator<String> iterator = set.iterator();
        while (iterator.hasNext()){
            String next = iterator.next();
            System.out.println(next);
        }
        System.out.println("-------------");
        //增强for遍历
        for (String s : set) {
            System.out.println(s);
        }
        System.out.println("-------------");
        //lambda表达式

//        set.forEach(new Consumer<String>() {
//            @Override
//            public void accept(String s) {
//                System.out.println(s);
//            }
//        });

        set.forEach(s->System.out.println(s));


    }
}

HashSet底层原理

HashSet底层采用哈希表存储数据。增删改查性能都较好。

哈希值：根据hashCode()方法计算出来的int整数。

public class HashSetDemo {
    public static void main(String[] args) {

        Student s1 = new Student("zhangsan",123);
        Student s3 = new Student("zhangsan",123);//将hashcode方法重写后，相同的属性值就可以返回相同的值。
        Student s2 = new Student("lisi",456);

        System.out.println(s1.hashCode());
        System.out.println(s3.hashCode());
        System.out.println("-----------------");
        System.out.println(s2.hashCode());
        System.out.println("-----------------");
        //此处为第三种情况，属性值不同或地址值不同但是计算出来的哈希值相同，也就是发生了哈希碰撞
        System.out.println("abc".hashCode());
        System.out.println("acD".hashCode());
    }
}

jdk8以前HashSet底层原理：数组+链表

jdk8以后：数组+链表+红黑树

利用元素的哈希值和数组的长度算出数组应该存入的位置；利用如下公式计算出应存入位置。

创建一个默认长度16，默认加载因为0.75的数组（也就是当数组元素到达12个时，扩容两倍）。

判断计算出的位置是否为null，如果是null则直接存入。若此位置不是null，则会调用equals()方法比较想存入数值和数组内元素属性值是否一样，若一样，则不存，若不一样则存入数组，形成链表。

jdk8以前，会将新元素存入数组，老元素挂在新元素下面。

jdk8以后，直接将新元素挂在老元素下面，形成链表。（若链表中有多个元素，则会跟链表中所有元素都比较，确定不存在才会存入）。

当形成的链表比较长（链表长度大于8并且数组长度大于等于64），会自动转化为红黑树

int index = (数组长度 - 1) & 哈希值

如果集合中存储自定义对象，必须重写hashCode和equals方法。

问：

1.为什么HashSet存取顺序不一样

因为HashSet的底层是数组，但是数组下面还挂着链表，他依次走下来，会将链表中的数据依次输出，因此存取顺序可能不一样

2.HashSet为什么没有索引

因为索引指不清楚，数组下面挂着链表，不可能让一个索引指向多个元素，因此取消了索引。

3.HashSet如何保证数据去重

使用HashCode和equals方法。

LinkedHashSet底层原理

有序，不重复，无索引

此处有序，指保证数据存储和取出的元素顺序一致，每个元素额外多了一个双链表机制，记录存储顺序（记录下一个数据的地址值）。

注：想要实现数据去重，一般使用HashSet。若要实现去重并存取有序才使用LinkedHashSet。

TreeSet底层原理

可排序，不重复，无索引

按照默认规则（从小到大）排序。

int，double就是按照从小到大排序

对于字符，字符串，则按照字符再ASCII码表中的数字升序进行排列。（比较时逐位比较）

对于自定义对象，往TreeSet中添加自定义对象时有两种比较方式

1.给出比较规则，否则会报错。实现Comparable接口，并实现其中的compareTo方法。

2.比较器排序（默认使用第一种方式进行比较，当第一种不能实现时再用这种）。

TreeSet<String> ts = new TreeSet<>(new Comparator<String>()){
    @Override
    public int compare(String o1, String o2){//此处o1表示要添加的元素
                                             //o2表示红黑树中已经存在的元素
        return 0;   
    }
}

方法的返回值：

是负数则表示要添加的元素在左边，放在红黑树的左边。

是整数则在右边。