黑马程序员技术交流社区

标题: 为什么TreeSet第四个元素开始，不跟第一个元素比较 [打印本页]
作者: asinzuo    时间: 2015-8-14 07:38
标题: 为什么TreeSet第四个元素开始，不跟第一个元素比较
为什么TreeSet第四个元素开始，不跟第一个元素比较，后面的元素只是跟最近的两个三比较

TreeSet集合里放元素{4，2，6，1，7，8}
下面代码运行结果发现：1只跟2、6比较了，但是没有跟第一个元素4比较，7也是只跟2、6比较了，没有跟第一个元素4比较。而8则没有跟4、6比较。
  1. import java.util.*;
  2. /*
  3. TreeSet排序的第一种方式：让元素自身具备比较性。
  4. 元素需要实现Comparable接口，覆盖compareTo方法。
  5. */
  6. import java.util.Iterator;
  7. import java.util.TreeSet;

  9. class  QuChong
  10. {
  11.         public static void main(String[] args)
  12.         {
  13.                
  14.                 TreeSet ts=new TreeSet();
  15.                
  16.                 ts.add(new MyList(4));
  17.                 ts.add(new MyList(2));
  18.                 ts.add(new MyList(6));
  19.                 ts.add(new MyList(1));
  20.                 ts.add(new MyList(7));
  21.                 ts.add(new MyList(8));
  22.                
  23.                 Iterator it=ts.iterator();
  24.                 while(it.hasNext()){
  25.                         MyList my=(MyList)it.next();
  26.                         System.out.print(my.getNum());
  27.                 }

  29.         }
  30. }

  32. class MyList implements Comparable
  33. {
  34.         private int num;
  35.         MyList(int num)
  36.         {
  37.                 this.num=num;
  38.         }
  39.         public int compareTo(Object obj){
  40.                 MyList my=(MyList)obj;
  41.                 System.out.println(this.num+"---"+my.num);
  42.                 if(this.num==my.num)
  43.                        
  44.                         return 0;
  45.                 return 1;

  47.         }
  48.         public int getNum()
  49.         {
  50.                 return num;
  51.         }
  52. }
复制代码

发现1只跟2、6比较了，但是没有跟第一个元素4比较，7也是。而8则没有跟4、6比较。


比较treeset.png (1.11 KB, 下载次数: 103)

比较treeset.png
作者: 木易水寒    时间: 2015-8-14 07:38
你集合中的元素是按这种结构储存的  集合中的第一个元素为根 按顺序取数和根元素比较 只有当找到比根元素小和大的元素构成2杈树结构时不在把取出的元素与根元素比较，每个分支上的元素同理只有当其构成完成的2杈树结构时其对应的根元素不在进行比较 这就是为什么你最后的8除去4都比了一个遍 因为2 和 6都没有形成完成的结构
作者: War3cdota    时间: 2015-8-14 10:26
我觉得他是跟所有叶节点比较的，你按照从上往下的比较需要知道每次向下的子树，但是他的比较是和所有的叶节点（包括未存的和存一个的）比较。其实最终都是二叉树存储的。
作者: asinzuo    时间: 2015-8-14 15:53
War3cdota 发表于 2015-8-14 10:26
我觉得他是跟所有叶节点比较的，你按照从上往下的比较需要知道每次向下的子树，但是他的比较是和所有的叶节 ...

不是很到位的样子
作者: fmi110    时间: 2015-8-16 09:26
学习了。。。。
作者: 唯爱丶    时间: 2015-8-16 09:28
因为他的原理是二叉树存储的,所以只需要一次一次比较确定了存储位置读取的时候按照从左到右就可以了!
作者: 凡尘    时间: 2015-8-28 23:44
木易水寒 发表于 2015-8-14 22:48
你集合中的元素是按这种结构储存的  集合中的第一个元素为根 按顺序取数和根元素比较 只有当找到比根元素小 ...

回答的非常好！~  二分叉结构的比较方式就是这样的。



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