黑马程序员技术交流社区
标题: 关于TreeSet集合的比较，排序的逻辑问题 [打印本页]
作者: 不喝茶的陆羽 时间: 2013-5-16 01:57
标题: 关于TreeSet集合的比较，排序的逻辑问题
本帖最后由 不喝茶的陆羽 于 2013-5-17 00:29 编辑
import java.util.*;
class TreeSetTest
{
public static void main(String[] args)
{
TreeSet ts = new TreeSet(new StrLenComparator());
ts.add("a");
ts.add("ab");
ts.add("abc");
Iterator it = ts.iterator();
while(it.hasNext())
{
System.out.println(it.next());
}
}
}
class StrLenComparator implements Comparator
{
public int compare(Object o1,Object o2)
{
String s1 = (String)o1;
String s2 = (String)o2;
int num = new Integer(s1.length()).compareTo(new Integer(s2.length()));
if(num==0)
return s1.compareTo(s2);
return num;
}
}
问题是：在对象进入TreeSet集合中进行比较时是如何完成的？我总觉得代码不足以进行两次及其以上的比较啊?像是现在的情况，就应该是a先进来，然后ab对象进来和a对象比，ab长，存在二叉树中a对象的右下方，然后第三个对象进来了，先和a对象进行比较，理论上应该再和，ab对象进行比较，事实上加输出语句也是的，但是在代码上并没有二次及其以上的比较语句啊？这是如何进行比较的？是因为定义TreeSet集合虚拟机就自动完成的吗？自己只需要定义怎么比，虚拟机会自己决定是和谁比怎么比吗？ ps:请大家仔细看下问题，不要纠结于2叉树，我完全明白2叉树的存储方式...
作者: xuemeng 时间: 2013-5-16 02:56
本帖最后由 xuemeng 于 2013-5-16 02:57 编辑
TreeSet是二叉树的结构, 二叉树的概述
Ø 二叉树是一种树状结构;
Ø 二叉树添加进来的第一个元素是根节点;
Ø 二叉树中每个节点最多两个子节点;
Ø 二叉树中每个节点都比自己左边的节点大, 比右边的节点小;
这个图能够充分解释你的疑惑!!
-
未命名.jpg
(89.08 KB, 下载次数: 2)
作者: 许智敏 时间: 2013-5-16 06:46
是二叉树结构，楼上的图很详细了，每一次向集合里添加元素时，因为集合里的元素已经是有序的了，所以添加元素用的是二分查找法，来确定元素的位置，
比如：1,2,3,4,5，要向里添加6，用二分查找，先算出中间元素index=0+ts.size()-1=2，即元素3的位置，比较6和3，6>3，直接向右比，左边就不比了，直到算出位置为止，提高了效率。
作者: 不喝茶的陆羽 时间: 2013-5-16 22:07
我要问的是，为什么集合中的元素是有序的，不用给我讲二叉树...那个老师讲了...希望大家能认真看下我提的问题再回答...
作者: 不喝茶的陆羽 时间: 2013-5-16 22:09
本帖最后由 不喝茶的陆羽 于 2013-5-17 00:30 编辑
xuemeng 发表于 2013-5-16 02:56 
TreeSet是二叉树的结构, 二叉树的概述
Ø 二叉树是一种树状结构;Ø 二叉树添加进来的第一个元素是根节 ...
谢谢你的回答，但是我问的实质上根本不是二叉树的问题，其中的一个问题是二叉树的存储结构是通过我上面的比较代码实现的吗？如果不是....详见我提的问题。
作者: 不喝茶的陆羽 时间: 2013-5-16 22:10
本帖最后由 不喝茶的陆羽 于 2013-5-17 00:31 编辑
许智敏 发表于 2013-5-16 06:46
是二叉树结构，楼上的图很详细了，每一次向集合里添加元素时，因为集合里的元素已经是有序的了，所以添加元 ...
谢谢你的回答，但是我问的不是二叉树...为什么大家都回答二叉树呢...
作者: xuemeng 时间: 2013-5-16 22:52
你弄懂怎么建立的二叉树，就知道其中是怎么比较的啦，建立二叉树的时候就进行相关的比较了。
作者: 不喝茶的陆羽 时间: 2013-5-17 00:25
本帖最后由 不喝茶的陆羽 于 2013-5-17 00:32 编辑
xuemeng 发表于 2013-5-16 22:52
你弄懂怎么建立的二叉树，就知道其中是怎么比较的啦，建立二叉树的时候就进行相关的比较了。 ...
谢谢你的回答，但请您仔细看完问题再回答....
作者: 不喝茶的陆羽 时间: 2013-5-17 11:44
顶顶，希望有人回答...
作者: 不喝茶的陆羽 时间: 2013-5-17 19:51
我自己找到了用于实现比较的代码
基于Comparable接口实现的二叉树操作
package org.lxh.demo11.comparabledemo;
class BinaryTree {
class Node {
// 声明一个节点类
private Comparable data;
// 保存具体的内容
private Node left;
// 保存左子树
private Node right;
// 保存右子树
public void addNode(Node newNode) {
// 要确定是放在左子树还是右子树
if (newNode.data.compareTo(this.data) < 0) {
if (this.left == null) {
// 放在左子树
this.left = newNode;
} else {
this.left.addNode(newNode);
}
}
if (newNode.data.compareTo(this.data) >= 0) {
if (this.right == null) {
// 放在右子树
this.right = newNode;
} else {
this.right.addNode(newNode);
}
}
}
public void printNode() {
// 输出时采用中序遍历
if (this.left != null) {
// 先输出左子树
this.left.printNode();
}
System.out.print(this.data + "\t"); // 再输出根节点
if (this.right != null) {
// 最后输出右子树
this.right.printNode();
}
}
};
private Node root;
// 根元素
public void add(Comparable data) {
Node newNode = new Node();
// 每传入一个新的内容就声
明一个根节点
newNode.data = data;
if (root == null) {
root = newNode;
// 如果是第1个元素，设置成
根元素
} else {
root.addNode(newNode);
// 确定节点是放在左子树还是右子树
}
}
public void print() {
// 输出节点
this.root.printNode();
}
};
public class ComparableDemo03 {
public static void main(String args[]) {
BinaryTree bt = new BinaryTree();
bt.add(8);
bt.add(3);
bt.add(3);
// 加入重复元素
bt.add(10);
bt.add(9);
bt.add(1);
bt.add(5);
bt.add(5); // 加入重复元素
System.out.println("排序之后的结果：");
bt.print();
}
}
程序运行结果：
排序之后的结果：
1 3 3 5 5 8 9 10
但是仍然没有明白
int num = new Integer(s1.length()).compareTo(new Integer(s2.length()));
if(num==0)
return s1.compareTo(s2);
return num;
这一小段是如何实现多次判断和比较的，难道是底层就已经封装了循环和自动调整比较对象？
作者: 曹睿翔 时间: 2013-5-19 07:50
如果问题已解决请再次编辑，改为以解决，方便大家看帖，没有就继续追问
作者: 不喝茶的陆羽 时间: 2013-5-19 10:18
曹睿翔 发表于 2013-5-19 07:50
如果问题已解决请再次编辑，改为以解决，方便大家看帖，没有就继续追问
还没有解决...我在顶下，问问吧。。
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |
