黑马程序员技术交流社区

标题: 关于TreeSet的小程序 [打印本页]
作者: amen0205    时间: 2013-3-9 04:44
标题: 关于TreeSet的小程序
  1. import java.lang.*;
  2. import java.util.*;
  3. class TreeDemo
  4. {
  5.         public static void main(String[] args)
  6.         {
  7.                 TreeSet tr=new TreeSet();

  9.                 tr.add(new Student("lili01",23));
  10.                 tr.add(new Student("lili02",20));
  11.                 tr.add(new Student("lili03",18));
  12.                 tr.add(new Student("lili04",30));
  13.                 tr.add(new Student("lili05",29));
  14.                 tr.add(new Student("lili06",60));
  15.                
  16.                 Iterator it=tr.iterator();
  17.                 while(it.hasNext())
  18.                 {
  19.                         Student s=(Student)it.next();
  20.                         System.out.println(s);
  21.                 }
  22.                 //System.out.println("Hello World!");
  23.         }
  24. }
  25. class Student implements Comparable
  26. {
  27.         private String name;
  28.         private int age;
  29.         Student(String name,int age)
  30.         {
  31.                 this.name=name;
  32.                 this.age=age;
  33.         }
  34.         public String getName()
  35.         {
  36.                 return name;
  37.         }
  38.         public int  getAge()
  39.         {
  40.                
  41.                 {
  42.                         return age;
  43.                 }
  44.         }
  45.         public int compareTo(Object o)
  46.         {
  47.                 if(!(o instanceof Student) )
  48.                         throw  new RuntimeException("该对象不是学生");

  50.                 Student s=(Student)o;
  51.                 System.out.println(this.name+"....compareto....."+s.name);

  53.                 if(this.age>s.age)
  54.                         return 1;
  55.                 if(this.age==s.age)
  56.                         return this.name.compareTo (s.name);
  57.                 else
  58.                         return -1;
  59.         }
  60. }
复制代码
这是关于TreeSet 的一个小程序
大家看下为什么结果是这样：



06 为什么先后和 02 05 04 比较了三次  就行了  我知道是二叉树分布 不过这个图该怎么画的？



QQ截图20130309043636.jpg (35.59 KB, 下载次数: 4)

QQ截图20130309043636.jpg
作者: 罗海清    时间: 2013-3-9 08:23
本帖最后由 罗海清 于 2013-3-9 08:29 编辑

不看不知道，我觉得是这样的解释。有谁能指出不对的地方，我们感激不尽。

这是我画的二叉树，首先要添加[lili01,23],然后添加【02，20】，所以02和01比较了一次。
接着添加【03，18】，所以，03和01，02都比较了一次。

接下来注意了，【04，30】来了。因为比较年龄，如果02号和01号的年龄相等，02号也会挂在
二叉树的左边。所以，04和02比较一次！接着是和01比较一次！然后，04挂在了右边！

接下来是【05，29】！同样，05不是首先和01比较，而是和02先比较！接着是04！
          所以05是和02，01，04都做了比较。
这时候，【06，60】来了。。。。。大事发生在这里，，，，，
     因为06只和02比较后发现，比02大！然后为了减少比较次数，，，它接着是和05比较，
发觉大于05，所以就和04比较，还是大于04，所以挂在右边。。。。

也就是06只是和02，05，04做了比较！

这是我的猜测，但是我做了添加一个【07，50】，发觉07和02，05，04，06比较。

新添一个【08，55】，发觉和02，05，07，06依次比较。。。

这就证明了以上我的说法是有根据的，本人认为是对的。

二叉树.PNG (11.27 KB, 下载次数: 3)

楼主原图

楼主原图

二叉树2.PNG (17.3 KB, 下载次数: 4)

新添了元素的图

新添了元素的图

比较图.PNG (17 KB, 下载次数: 2)

运行结果

运行结果
作者: 谢洋    时间: 2013-3-9 09:48
本帖最后由 谢洋 于 2013-3-9 09:52 编辑

1.                                     tr.add(new Student("lili01",23));
2.                                     tr.add(new Student("lili02",20));
3.                                     tr.add(new Student("lili03",18));
4.                                     tr.add(new Student("lili04",30));
5.                                     tr.add(new Student("lili05",29));
6.                                     tr.add(new Student("lili06",60));
7.                                     tr.add(new Student("lili07",24));
8.                                     tr.add(new Student("lili08",22));
9.                                     tr.add(new Student("lili09",54));
lili01....compareto.....lili01
lili02....compareto.....lili01
lili03....compareto.....lili01
lili03....compareto.....lili02
lili04....compareto.....lili02
lili04....compareto.....lili01
lili05....compareto.....lili02
lili05....compareto.....lili01
lili05....compareto.....lili04
lili06....compareto.....lili02
lili06....compareto.....lili05
lili06....compareto.....lili04
lili07....compareto.....lili02
lili07....compareto.....lili05
lili07....compareto.....lili01
lili08....compareto.....lili02
lili08....compareto.....lili05
lili08....compareto.....lili01
lili09....compareto.....lili02
lili09....compareto.....lili05
lili09....compareto.....lili04
lili09....compareto.....lili06

从打印的结查与上图来看，注意图的中元素的角标
发现：二权树的比较方式，从集合中已有三个元素开始，每次都是从集合中的2号元素开始比较（其实也是中间）；然后再从集合中后面剩下元素的中间处（假设A处）开始比较，如果小于，再从2号到当前（A处）之间的中间(假设B处）那个元开始比；如果大于B处的，那么再从B与A之间的中间（假设C处）开始找,如此下去，直到找到适合的位置
这样子做大大提高了比较的效率

treesset.png (13.33 KB, 下载次数: 3)

treesset.png
作者: amen0205    时间: 2013-3-9 18:34
罗海清 发表于 2013-3-9 08:23
不看不知道，我觉得是这样的解释。有谁能指出不对的地方，我们感激不尽。

这是我画的二叉树，首先要添加[l ...

你 04 的时候  02   01  的年龄不同  你看错了  你后面的理解额   都乱了  
作者: 罗海清    时间: 2013-3-9 23:17
门文通 发表于 2013-3-9 18:34
你 04 的时候  02   01  的年龄不同  你看错了  你后面的理解额   都乱了

不是，，意思是说，02有可能和01的年龄相等，，所以就要比较第一个存入的数据的左边的一个，

也就是要比较02，，，那么为什么不比较位于02左边的03？是因为即使03的年龄也相等，，之后的元素和02比

较后的结果，与和03比较的结果的效果是一样的，为什么要多比较一次呢？

说的是这个意思。
作者: 移动小坦克    时间: 2013-3-10 04:04
本帖最后由 韩松范 于 2013-3-10 04:05 编辑


到了04，以后没有从01开始比较，而是从02开始比较的原因是，当数据到了3个以后，
比较是从中间开始比较（这个叫折半查找），也就是02，这样提高效率，如果大于中间数就比较01，如果小于02 ，就与03 比较。
当06进入以后还是先与前三位的中间数进行比较，如果比02大，这时就不与03做比较，因为此时不仅仅就3个数据了，而是与
02后，3个数据的中间数据作比较，也就是03，04，05，因为05的值，是这三个数据中的中间值，所以与05的值做比较，以后以此此类推
这个就是2叉数的特点。。。。。。。。。。


其实图形应该是这样的









无标题.png (19.78 KB, 下载次数: 4)

无标题.png
作者: amen0205    时间: 2013-3-10 04:17
韩松范 发表于 2013-3-10 04:04
到了04，以后没有从01开始比较，而是从02开始比较的原因是，当数据到了3个以后，
比较是从中间开始比较（ ...

按你说的  04  进来后折半  和02 比   那06进来怎么就不折半了  他应和01比啊
作者: amen0205    时间: 2013-3-10 04:22
罗海清 发表于 2013-3-9 23:17
不是，，意思是说，02有可能和01的年龄相等，，所以就要比较第一个存入的数据的左边的一个，

也就是要比 ...

04你说可能相等  就和02比了  那怎么不直接和 01 比呢   那06呢  也因为02和01可能相同  就又和02比了吗  那和02比完了 怎么就直接找上 05了  这需要找出一种规律  来明确原理   显然你还没总结出一个可以信服的规律出来 呵呵
作者: 罗海清    时间: 2013-3-10 09:38
门文通 发表于 2013-3-10 04:22
04你说可能相等  就和02比了  那怎么不直接和 01 比呢   那06呢  也因为02和01可能相同  就又和02比了吗  ...

没事，我的观点都是我自己的猜测
作者: amen0205    时间: 2013-3-10 17:37
罗海清 发表于 2013-3-10 09:38
没事，我的观点都是我自己的猜测

你知道平衡二叉树吗  我感觉应和这个有关  你有兴趣可以看看



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