TreeSet详解

痛定思痛。 2022-07-16 07:09 165阅读 0赞

1.TreeSet原理:  
/\*  
\* TreeSet存储对象的时候, 可以排序, 但是需要指定排序的算法  
\*  
\* Integer能排序(有默认顺序), String能排序(有默认顺序), 自定义的类存储的时候出现异常(没有顺序)  
\*  
\* 如果想把自定义类的对象存入TreeSet进行排序, 那么必须实现Comparable接口  
\* 在类上implement Comparable  
\* 重写compareTo()方法  
\* 在方法内定义比较算法, 根据大小关系, 返回正数负数或零  
\* 在使用TreeSet存储对象的时候, add()方法内部就会自动调用compareTo()方法进行比较, 根据比较结果使用二叉树形式进行存储  
\*/

2.TreeSet是依靠TreeMap来实现的。  
TreeSet是一个有序集合，TreeSet中的元素将按照升序排列，缺省是按照自然排序进行排列，意味着TreeSet中的元素要实现Comparable接口。或者有一个自定义的比较器。  
我们可以在构造TreeSet对象时，传递实现Comparator接口的比较器对象。

import java.util.Iterator;
    import java.util.*;
    
    public class TreeSetTest {
        public static void main(String[] args) {
            Set ts = new TreeSet();
            ts.add("abc");
            ts.add("xyz");
            ts.add("rst");
            Iterator it = ts.iterator();
            while (it.hasNext()) {
                System.out.println(it.next());
            }
        }
    }

输出结果：  
abc  
rst  
xyz

打印结果不是和先前加入的顺序一样，它是按照一个字母的排序法进行排序的。这是因为String 类实现了Comparable接口。  
如果我们自己定义的一个类的对象要加入到TreeSet当中，那么这个类必须要实现Comparable接口。

package test.treeset;
    import java.util.Iterator;
    import java.util.Set;
    import java.util.TreeSet;
    
    
    public class test_treeset { 
         @SuppressWarnings("unchecked")
        public static void main(String[] args) {
                Set ts = new TreeSet();
                ts.add(new Teacher("zhangsan", 1));
                ts.add(new Teacher("lisi", 2));
                ts.add(new Teacher("wangmazi", 3));
                ts.add(new Teacher("wangwu",4));
                ts.add(new Teacher("mazi", 3));
                Iterator it = ts.iterator();
                while (it.hasNext()) {
                    System.out.println(it.next());
                }
            }
    }
    class Teacher implements Comparable { 
        int num;
        String name;
    
        Teacher(String name, int num) {
            this.num = num;
            this.name = name;
        }
    
        public String toString() {
            return "学号：" + num + "\t\t姓名：" + name;
        }
    
        //o中存放时的红黑二叉树中的节点，从根节点开始比较
        public int compareTo(Object o) {
            Teacher ss = (Teacher) o;
            int result = num < ss.num ? 1 : (num == ss.num ? 0 : -1);//降序
            //int result = num > ss.num ? 1 : (num == ss.num ? 0 : -1);//升序
            if (result == 0) {
                result = name.compareTo(ss.name);
            }
            return result;
        }
    }

运行结果：  
学号：4 姓名：wangwu  
学号：3 姓名：mazi  
学号：3 姓名：wangmazi  
学号：2 姓名：lisi  
学号：1 姓名：zhangsan

3.比较器  
在使用Arrays对数组中的元素进行排序的时候，可以传递一个比较器。  
在使用Collections对集合中的元素进行排序的时候，可以传递一个比较器。  
那么在使用TreeSet对加入到其中的元素进行排序的时候可以传入一个比较器吗？

public TreeSet(Comparator<? super E> comparator) {
            this(new TreeMap<E,Object>(comparator));
        }

通过查看它的构造方法就知道可以传入一个比较器。  
构造一个新的空TreeSet，它根据指定比较器进行排序。插入到该 set 的所有元素都必须能够由指定比较器进行相互比较：对于 set 中的任意两个元素 e1 和e2，执行 comparator.compare(e1, e2) 都不得抛出 ClassCastException。如果用户试图将违反此约束的元素添加到 set 中，则 add 调用将抛出 ClassCastException。

package test.treeset;
    
    import java.util.Comparator;
    import java.util.Iterator;
    import java.util.TreeSet;
    
    public class TreeSetTest { 
        @SuppressWarnings("unchecked")
        public static void main(String[] args) {
            TreeSet ts = new TreeSet(new Teacher2.TeacherCompare());
            ts.add(new Teacher2("zhangsan", 2));
            ts.add(new Teacher2("lisi", 1));
            ts.add(new Teacher2("wangmazi", 3));
            ts.add(new Teacher2("mazi", 3));
            Iterator it = ts.iterator();
            while (it.hasNext()) {
                System.out.println(it.next());
            }
        }
    }
    
    class Teacher2 { 
        int num;
        String name;
    
        Teacher2(String name, int num) {
            this.num = num;
            this.name = name;
        }
    
        public String toString() {
            return "学号：" + num + " 姓名：" + name;
        }
    
        static class TeacherCompare implements Comparator { // 老师自带的一个比较器
            //o1中存放的事目标节点
            //o2中存放时的红黑二叉树中的节点，从根节点开始比较
            public int compare(Object o1, Object o2) {
                Teacher2 s1 = (Teacher2) o1;// 转型
                Teacher2 s2 = (Teacher2) o2;// 转型
                int result = s1.num > s2.num ? 1 : (s1.num == s2.num ? 0 : -1);
                if (result == 0) {
                    result = s1.name.compareTo(s2.name);
                }
                return result;
            }
        }
    }

运行结果：  
学号：1 姓名：lisi  
学号：2 姓名：zhangsan  
学号：3 姓名：mazi  
学号：3 姓名：wangmazi

文章转载于：[http://www.cnblogs.com/meng72ndsc/archive/2010/12/23/1914477.html][http_www.cnblogs.com_meng72ndsc_archive_2010_12_23_1914477.html]

[http_www.cnblogs.com_meng72ndsc_archive_2010_12_23_1914477.html]: http://www.cnblogs.com/meng72ndsc/archive/2010/12/23/1914477.html