java进阶(31)--TreeSet集合、TreeMap集合、自平衡二叉树

一、TreeSet集合简单

1、TreeSet集合底层是一个TreeMap

2、TreeMap集合底层是一个二叉树

3、放到TreeSet集合的元素等同于放到TreeMap集合的Key部分

4、TreeSet集合中元素：无序不可重复，但是可以按照元素大小顺序自动排序，称为可排序集合。

5、二叉树数据机构包含：Key，Value，left，right，parent

6、TreeSet集合或TreeMap集合的Key部分元素想做到排序，包含以下两种方式：

第一种：放在集合中元素需要实现Java.lang.Comparable接口

第二种：在构造TreeSet或者TreeMap集合时需要传一个比较器对象：comparator接口

7、comparable接口与comparator接口怎么选择？

当比较规则不会改变或规则只一个时一般选择comparable接口；

当比较规则有多个，并且需要各个比较规则之间频繁切换，建议使用comparator接口，符合ocp原则。

 

二、实例操作，TreeSet集合使用

1、根据数据库中数据，按照一定的顺序（String类型）取出

 2、根据数字（Integer）顺序取出

 3、对于自定义的类型来说，TreeSet可以排序吗？

报错：java.lang.ClassCastException，JAVAADVANCE.Person cannot be cast to java.lang.Comparable

以下程序：对于Person类型来说，无法排序，因为没有指定Person对象的比较规则；程序运行时出现异常

出错直接原因：Person未实现comparable接口。

 4、自定义类元素写入TreeSet，第一种方式：实现Comparable接口并重写compareTo方法。

 5、使用第一种方式-重新compareTo方法：实现客户按照“姓名“，”年龄“排序，当年龄相等时，按照姓名排序。

 遍历集合，查看最终排序结果

  6、TreeSet集合中元素可排序的第二种方式：使用比较器的方式

注意：

Comparable是Java.lang包下的

Comparator是Java.until包下的

 创建Tree集合使用编写的比较器，遍历集合，查看最终排序结果

 

7、使用第二种方式，但采取静态内部类的方式，使用比较器

 查看运行的结果：

 

 三、自平衡二叉树

1、自平衡二叉树，遵循左小右大的原则存放数据

2、遍历二叉树的时候有三种方式：

　　前序遍历：根左右

　　中序遍历：左根右

　　后序遍历：左右根

　　注意：前中后说的是"根"的位置

　　根在前面是前序，根在中间是中序，根在后面是后序

3、TreeSet集合/TreeMap集合采用是中序遍历方式

　　Itertor迭代器采用的是中序遍历方式，即左根右

4、举例说明二叉树结构：

　　数据如下：100，200，50，60，80，140，130，135，180.，666.40...

 

 5、采用中序方式遍历取出：

完成排序：40，50，55，60，80，100，120，130，135，140，180，200，666