一.
treeset 集合可以对其中的元素进行排序,它有两种排序方法,现在我们想知道它底层是什么结构,它是怎么确定元素位置的?它是有原因的,而且它这种结构对于排序而言,效率很高.
一说到排序,之前说到选择冒泡.选择冒泡对于比较次数而言,比较多一些,因为是转着圈在比.对于 treeset 而言,有个比较好的地方就是
将例子中的元素按照年龄排序,演示一遍它是怎么存放的.
存 zhangsan,28 的时候,就在容器中搞了一个 zhangsan,28.容器中只有一个元素,不进行比较.紧跟着再来个 lisi,21,lisi 要调集自己的 compareto 和 zhangsan 碰一下.lisi 和 zhangsan 一比,发现比 28 小,返回一个负数,紧跟着放在了 28 的左边.和 28 比完只有两种情况,要么是大,要么是小.有人说,不是还有相等的情况么,相等是进不来的.接着 zhouqi 来了,和 28 一比,比 28 还要大,它和 21 不需要再进行相比了,它直接放置在 28 的右边.接着 25 来了,和 28 比,比 28 小,就不和 29 相比了,这样一来就可以提高一点效率 (如果一开始存储的数就是最值,那就惨了),没有必要挨个彭,这里是分了叉的.25 比 28 小,往左边走,比 21 大,就往右边放.最后 24 来了,比 28 小,往左边走,比 21 大,往右走,比 25 小,往左走.
我们把这种结构称之为二叉树,从一个结点上分出两个叉.这是一种数据结构,凡是相同进不来.怎么判断相同,只要是返回 0,就进不去.
因此,到现在我们就可以通过二叉树的方法完成排序,并能确定元素的位置.
二叉树中的结点有什么特点?首先结点包含了几个要素,就跟我们说链表一样,记住的是后面的数据.结点首先记住左边的数据,就是小的数据,小的就往左边放.21 结点中持有几个引用?两个,一个叫做左,一个叫做右,右放置的都是大的数据.不止两个,还有一个叫做父,记住的是它爹,一共是三,但是有的没有三个,最多是三个.
这种结构怎么寻找数据呢?先从 19 开始,它是最小的,紧跟着往上找,因为 19 没有左边和右边.到 21,按理说应该往上找,但是要看 21 右边有没有,有 25.然后 25 的左右有没有?就按照这样的顺序找.我感觉这样的顺序很奇怪,无法展现二叉树的高效率.
现在说一个效率问题,如果存储的数据很多的话,每记一个元素,都一直往下加,很慢,那怎么办呢?
二叉树做的还是可以的,比如说按照下面的截图,装载了五个元素
在装 19 的时候,怎么装?截图中的五个元素也是有序的,我们想在一个有序的结构当中,去确定一个元素的位置,怎么做最方便?二分查找,不用从顶层往下挨个比较,取五个元素中折中的那个元素,折中的那个元素不一定是 28,所以它每次在往里面放元素之前,先对已有的有序元素进行折半.这就是二叉树怎么提高效率地.
思考一个问题:现在用了比较器了,它厉害在能够对元素进行指定方式的排序.拿它能不能完成我们之前所学的有序的动作呢?要做怎么存进去,怎么取出来.
如果实现怎么存进去,怎么取出来,那就意味着先取出来的是 28,再取的是 21,那就是 21 大于 28,或者说 zhangsan 先取出来,然后是 lisi,也就是说 lisi 大于 zhangsan,说的不是年龄值,而是对象,21 所代表的这个对象.为什么呢?排完序后,取出来的都是最小的 (这和存的时候,按照什么顺序存有关吧),其次才变大,所以取的时候,必须保证 zhangsan 是小于 lisi 的,那么这个怎么画?
如果是这么画的就是,21 大于 28,21 位于 28 的右侧.21 怎么能大于 28 呢?二叉树谁管你年龄和姓名,是你指定的.二叉树看的是返回值,你要是说返回 0,那全都是一样的,不要把它固化在数值上.如果二叉树是下面截图这么画的话,取的先是 28,28 在这三个数中是最小的,右边放的全是大的,那么这个代码怎么写呢?
就不这儿那儿的比较了,全部返回正数.返回 1 就意味这,28 先进来了,liasi 和 zhangsan 一比,lisi 就比 zhangsan 大,二叉树不管其它的,就看返回值是正负,还是 0.观看输出结果,和存储的结果是一样的,这就是有序的.如果想要倒序的话,返回 - 1 就可以了.
按照指定条件比较,别忘了主要条件和次要条件.
来源: http://www.bubuko.com/infodetail-2467824.html