一、TreeSet
1、TreeSet集合底层实际上是一个TreeMap;TreeMap集合底层是一个二叉树
2、放到TreeSet集合中的元素,等同于放到TreeMap集合key部分了。
3、TreeSet集合存储元素特点:无序不可重复的,但是存储的元素可以自动按照大小顺序排序
称为:可排序集合。
无序指的是存进去的顺序和取出来的顺序不同,并且没有下标
TreeSet源码存元素:实际上是调用的TreeMap的put方法
public TreeSet() {
this(new TreeMap<E,Object>());
}
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
TreeMap中存元素:
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
TreeMap取元素:
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
测试如下:
public static void main(String[] args) {
TreeSet<String> set = new TreeSet<>();
set.add("A");
set.add("D");
set.add("F");
set.add("B");
set.add("G");
set.add("E");
set.add("C");
for (String str: set) {
System.out.println(str);
/*
A
B
C
D
E
F
G
*/
}
// 创建一个TreeSet集合
TreeSet<String> ts = new TreeSet<>();
// 添加String
ts.add("zhangsan");
ts.add("lisi");
ts.add("wangwu");
ts.add("zhangsi");
ts.add("wangliu");
// 遍历
for(String s : ts){
// 按照字典顺序,升序!
System.out.println(s);
/*
lisi
wangliu
wangwu
zhangsan
zhangsi
*/
}
TreeSet<Integer> ts2 = new TreeSet<>();
ts2.add(100);
ts2.add(200);
ts2.add(900);
ts2.add(800);
ts2.add(600);
ts2.add(10);
for(Integer elt : ts2){
// 升序!
System.out.println(elt);
/*
10
100
200
600
800
900
*/
}
二、比较器
1、TreeSet中有两种排序,一个是自然排序,一个是重写compareTo()方法自定义排序。
自然排序可以参考Integer,String等类中的实现。其顺序也是我们常见的“1,2,3,4”,“a,b,c,d”。
2、重写compareTo()方法自定义排序
(1)对自定义的类型来说,TreeSet无法排序, 因为没有指定 自定义类型对象之间的比较规则
程序运行的时候出现异常:
java.lang.ClassCastException: class com.collection.XX cannot be cast to class
java.lang.Comparable 出现这个异常的原因是: 自定义类型对象没有实现java.lang.Comparable接口
如下:
public class TreeSetCustom {
public static void main(String[] args) {
TreeSet<TreeSetPerson> set = new TreeSet<>();
TreeSetPerson p1 = new TreeSetPerson(28);
TreeSetPerson p2 = new TreeSetPerson(12);
TreeSetPerson p3 = new TreeSetPerson(24);
TreeSetPerson p4 = new TreeSetPerson(16);
set.add(p1);
set.add(p2);
set.add(p3);
set.add(p4);
for (TreeSetPerson person:set) {
System.out.println(person);
}
}
}
class TreeSetPerson {
private int age;
public TreeSetPerson(){
}
public TreeSetPerson(int age){
this.age = age;
}
@Override
public String toString(){
return "TreeSetPerson[age="+ this.age + "]";
}
}
3、TreeSet集合中元素可排序包括两种方式:
(1)放在集合中的元素实现java.lang.Comparable接口
(2)在构造TreeSet或者TreeMap集合的时候给传一个比较器对象Comparator
TreeSet提供了四种构造器
TreeSet()
TreeSet(Collection< ? extends E> c)
TreeSet(Comparator< ? super E> comparator)
TreeSet(SortedSet< E > s)
(1)实现java.lang.Comparable接口
/**
compareTo方法的返回值:
返回0表示相同,value会覆盖
返回>0,会继续在右子树上找
返回<0,会继续在左子树上找
*/
public class TreeSetCustom1 {
public static void main(String[] args) {
TreeSet<TreeSetPeople> peopleSet = new TreeSet<>();
//先按照年龄升序,如果年龄一样的再按照姓名升序
TreeSetPeople p1 = new TreeSetPeople(20,"张三");
TreeSetPeople p2 = new TreeSetPeople(12,"李四");
TreeSetPeople p3 = new TreeSetPeople(24,"王二");
// 按照字典顺序,升序!
TreeSetPeople p4 = new TreeSetPeople(18,"赵四");//zhaosi
TreeSetPeople p5 = new TreeSetPeople(18,"刘三");//liusan
TreeSetPeople p6 = new TreeSetPeople(16,"钱一");
peopleSet.add(p1);
peopleSet.add(p2);
peopleSet.add(p3);
peopleSet.add(p4);
peopleSet.add(p5);
peopleSet.add(p6);
for(TreeSetPeople people:peopleSet){
System.out.println(people);
}
}
}
/**
放在TreeSet集合中的元素需要实现java.lang.Comparable接口。
实现compareTo方法
* */
class TreeSetPeople implements Comparable<TreeSetPeople>{
private int age;
private String name;
public TreeSetPeople(){
}
public TreeSetPeople(int age,String name){
this.age = age;
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString(){
return "TreeSetPeople[age=" + this.age + ","
+ "name=" + this.name + "]";
}
/**
* 需要在这个方法中编写排序规则,按照什么进行比较
* k.compareTo(t.key)
* 拿着参数k和集合中的每一个k进行比较
* */
@Override
public int compareTo(TreeSetPeople o) {
if (this.age == o.age){
return this.name.compareTo(o.name);
}else {
return this.age - o.age;
}
}
}
(2)比较器对象Comparator
public class TreeSetComparatorTest {
public static void main(String[] args) {
// TreeSet<Child> childTreeSets = new TreeSet<>(new ChildComparator());
TreeSet<Child> childTreeSets = new TreeSet<>(new Comparator<Child>() {
@Override
public int compare(Child o1, Child o2) {
return o1.getAge() - o2.getAge();
}
});
Child c1 = new Child(10);
Child c2 = new Child(6);
Child c3 = new Child(2);
Child c4 = new Child(8);
childTreeSets.add(c1);
childTreeSets.add(c2);
childTreeSets.add(c3);
childTreeSets.add(c4);
for (Child c : childTreeSets){
System.out.println(c);
}
}
}
class Child{
private int age;
public Child(int age){
this.age = age;
}
@Override
public String toString(){
return "Child[age=" + this.age + "]";
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
}
class ChildComparator implements Comparator<Child>{
@Override
public int compare(Child o1, Child o2) {
return o1.getAge() - o2.getAge();
}
}
4、Comparable 和 Comparator选择
当比较规则不会发生改变时(比较规则只有1个的时候),可实现Comparable接口
如果比较规则有多个,并且需要多个比较规则之间频繁切换,可使用Comparator接口
三、二叉树
1、Teet/TreeMap是自平衡二叉树(AVL),遵循左小右大原则存放
存放是要依靠左小右大原则,存放时,要进行比较
2、遍历二叉树三种方式
(1)前序遍历:根左右
(2)中序遍历:左根右
(3)后序遍历:左右根
注:
前中后说的是“根” 的位置
根在前面是前序;根在中间是中序;根在后面是后序
3、 TreeSet集合/TreeMap集合采用的是:中序遍历方式(左根右)
Iterator迭代器采用的是中序遍历方式
存放的过程就是排序的过程,取出来就是自动按照大小顺序排列的
如下数据:
5 2 8 1 4 7 9 3
在二叉树中表示如下:
进行中序遍历方式(左跟右) 遍历取出,会得到
1 2 3 4 5(根) 7 8 9
如果想深入的研究二叉树数据结构可查阅数据结构相关书籍
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/35230.html