黑马程序员技术交流社区

标题: TreeSet比较对象排序compareTo()的疑问 [打印本页]

---

作者: pphdsny3    时间: 2012-8-14 16:43
标题: TreeSet比较对象排序compareTo()的疑问

1. package itheima14;
   
2. 
   
3. import java.util.*;
   
4. 
   
5. class TreeSetDemo
   
6. {
   
7.         public static void main(String[] args)
   
8.         {
   
9.                 TreeSet ts = new TreeSet();
   
10. 
    
11.                 ts.add(new Student("lisi02",22));
    
12.                 ts.add(new Student("lisi007",20));
    
13.                 ts.add(new Student("lisi09",19));
    
14.                 ts.add(new Student("lisi08",13));
    
15.                 //ts.add(new Student("lisi007",20));
    
16.                 //ts.add(new Student("lisi01",40));
    
17. 
    
18.                 Iterator it = ts.iterator();
    
19.                 while(it.hasNext())
    
20.                 {
    
21.                         Student stu = (Student)it.next();
    
22.                         System.out.println(stu.getName()+"..."+stu.getAge());
    
23.                 }
    
24.         }
    
25. }
    
26. 
    
27. 
    
28. class Student implements Comparable//该接口强制让学生具备比较性。
    
29. {
    
30.         private String name;
    
31.         private int age;
    
32. 
    
33.         Student(String name,int age)
    
34.         {
    
35.                 this.name = name;
    
36.                 this.age = age;
    
37.         }
    
38. 
    
39.         public int compareTo(Object obj)
    
40.         {
    
41. 
    
42.                 //return 0;
    
43.                
    
44.                 if(!(obj instanceof Student))
    
45.                         throw new RuntimeException("不是学生对象");
    
46.                 Student s = (Student)obj;
    
47. 
    
48.                 System.out.println(this.name+"....compareto....."+s.name);
    
49.                 if(this.age>s.age)
    
50.                         return 1;
    
51.                 if(this.age==s.age)
    
52.                 {
    
53.                         return this.name.compareTo(s.name);
    
54.                 }
    
55.                 return -1;
    
56.                 /**/
    
57.         }
    
58. 
    
59.         public String getName()
    
60.         {
    
61.                 return name;
    
62. 
    
63.         }
    
64.         public int getAge()
    
65.         {
    
66.                 return age;
    
67.         }
    
68. }

复制代码

得到的结果是：
lisi007....compareto.....lisi02
lisi09....compareto.....lisi02
lisi09....compareto.....lisi007
lisi08....compareto.....lisi007
lisi08....compareto.....lisi09
lisi08...13
lisi09...19
lisi007...20
lisi02...22

疑问：为什么lisi08进去以后只与007和09比较，而不与02比较？？
把年纪改大点也不行..

---

作者: pphdsny3    时间: 2012-8-14 18:15
知道二叉树的那幅图，但是还是搞不清楚，一个新元素被添加进去以后，他的比较过程是这么样的？有谁能讲讲么？

---

作者: 黄敏    时间: 2012-8-14 20:51


得到的结果是：
lisi007....compareto.....lisi02
lisi09....compareto.....lisi02
lisi09....compareto.....lisi007
lisi08....compareto.....lisi007
lisi08....compareto.....lisi09
lisi08...13
lisi09...19
lisi007...20
lisi02...22

疑问：为什么lisi08进去以后只与007和09比较，而不与02比较？？
把年纪改大点也不行..

跟你说一下我的理解吧，希望对你有帮助
应该是这样的，比较器先把22存进来，再把20存进来，存进来之前先判断20比22大还是小，很显然是小，所以就把20放在22的左边了，看图，依次都是在存入下一个数之前判断大小，存入想应的位置，二叉树原理，我说只是大概的意思，详细了解二叉树还请翻阅资料。

至于你说lisi08为什么不跟lisi02比较，在lisi08比较之前，lisi007已经和lisi02比较了，比较器知道了lisi007比lisi002，再存进去比较的时候，当存储器里面的比较元素多了的时候，（这就涉及到二叉树的遍历问题，二叉树遍历分三种，前序遍历，中序遍历，后序遍历，按着三种方式遍历了，选其一，看你比较元素的复杂度了，这是二叉树自己选择了），就不再跟比较器里的元素一一比较了，这就是二叉树的折中比较了，就不再一一相比较了，也就是遍历方式选择了，说了这么多，其实，你要想真正里面怎么比较，还是得看看数据结构里面的二叉树结构了，但是对于我们做java，只要知道有这个意思就行了，没必要深究，除非你是搞数据结构研究的

---

作者: 乐峰    时间: 2012-8-14 21:29
TreeSet的底层是基于TreeMap的，TreeMap的实现时基于红黑树（一种平衡二叉树）。
此树中，任意一个节点的都 大于等于它的左子树的最大值、小于等于右子树的最小值。
当你插入一个新值时，红黑树从根节点开始，跟当前节点作比较，如果小于当前节点的值，向左边找，如果大于当前节点的值，向右边找。
这样一直下去，会找到它的位置。
所以lisi08进去以后小于当前节点的值只能在左边找，也就只与007和09比较，不与02比较。
输出结果是
lisi007....compareto.....lisi02
lisi09....compareto.....lisi02
lisi09....compareto.....lisi007
lisi08....compareto.....lisi007
lisi08....compareto.....lisi09
lisi08...13
lisi09...19
lisi007...20
lisi02...22

无标题.png (14.82 KB, 下载次数: 24)

下载附件

2012-8-14 21:29 上传

---

作者: 黑马振鹏    时间: 2012-8-14 21:35

聂峰 发表于 2012-8-14 21:29
TreeSet的底层是基于TreeMap的，TreeMap的实现时基于红黑树（一种平衡二叉树）。
此树中，任意一个节点的 ...

为什么20是根节点？

---

作者: 乐峰    时间: 2012-8-14 21:55

黑马振鹏 发表于 2012-8-14 21:35
为什么20是根节点？

因为第一个数进去并没有调动compareTo方法，只有出现两个对象的时候才调动compareTo方法，而且是007与02进行比较，以007的值作为第一次的比较，也作为以后比较的根节点。

---

作者: 张忠豹    时间: 2012-8-14 23:26


又是二叉树……

---

作者: 张忠豹    时间: 2012-8-15 00:26
我觉得，这句话解释的不怎么靠谱，看我下面的程序：

import java.util.TreeSet;
class Students implements Comparable {
int count;
public Students(int count) {
  this.count = count;
}
public boolean equals(Object obj) {
  if (obj instanceof Student) {
   Students r = (Students) obj;
   if (r.count == this.count) {
    return true;
   }
  }
  return true;
}
public int compareTo(Object obj) {
  Students s = (Students) obj;
  System.out.println(this.count + "....compareto....." + s.count);
  Students r = (Students) obj;
  if (this.count > r.count) {
   return 1;
  } else if (this.count == r.count) {
   return 0;
  } else {
   return -1;
  }
}
}
public class TestTreeSet2 {
/**
  * @param args
  */
public static void main(String[] args) {
  // TODO Auto-generated method stub
  TreeSet ts = new TreeSet();
  ts.add(new Students(5));
  ts.add(new Students(-3));
  ts.add(new Students(9));
  ts.add(new Students(-2));
  ts.add(new Students(7));
}
}
//它的根节点是5而不是-3，这又是和解释啊！
//-3....compareto.....5
//9....compareto.....5
//-2....compareto.....5
//-2....compareto.....-3
//7....compareto.....5
//7....compareto.....9

zzz.jpg (15.16 KB, 下载次数: 14)

下载附件

2012-8-15 00:23 上传

---

作者: pphdsny3    时间: 2012-8-15 08:56

张忠豹 发表于 2012-8-15 00:26
我觉得，这句话解释的不怎么靠谱，看我下面的程序：

import java.util.TreeSet;

进过我多次的实验，得出了个小结论：
一个数进去以后先是跟根节点比较，如果小于则在根节点的左边找一个数比较--->（这个数貌似是折中找的还是什么的，不是很清楚）。然后比较结果再判断是大于还是小于，这样下去继续比较，直到比出结果来
有没有数据结构的牛人能给大家讲讲二叉树的具体比较过程呢？？？

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2