Java教程
Java-TreeSet集合，二叉树
本文主要是介绍Java-TreeSet集合，二叉树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
一、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
如果想深入的研究二叉树数据结构可查阅数据结构相关书籍
这篇关于Java-TreeSet集合，二叉树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
Springboot应用的多环境打包入门11-23
-
Springboot应用的生产发布入门教程11-23
-
Python编程入门指南11-23
-
Java创业入门：从零开始的编程之旅11-23
-
Java创业入门：新手必读的Java编程与创业指南11-23
-
Java对接阿里云智能语音服务入门详解11-23
-
Java对接阿里云智能语音服务入门教程11-23
-
JAVA对接阿里云智能语音服务入门教程11-23
-
Java副业入门：初学者的简单教程11-23
-
JAVA副业入门：初学者的实战指南11-23
-
JAVA项目部署入门：新手必读指南11-23
-
Java项目部署入门：新手必看指南11-23
-
Java项目部署入门：新手必读指南11-23
-
Java项目开发入门：新手必读指南11-23
-
JAVA项目开发入门：从零开始的实用教程11-23
栏目导航
