❝今天来聊一聊树形结构如何排序。
❞
1.1 需求
现在要求实现一个菜单功能。而这个菜单会有层级关系，因此整个结构呈现出来的话，就是一颗树。这个功能相信大多数人都是做过的。很简单对吧。但是现在在加上一个功能，需要实现任意拖拽，你可以拖拽一个节点也可以是一颗子树。并且拖拽后的顺序要保持住。
1.2 理解消化需求
需求消化下就是两点：
实现菜单的树级结构 支持任意拖拽后的顺序保存
我们从java
语言层面的设计出发，要实现一颗树，我们很快就能想到的结构便是：
| id | pid | name |
|---|---|---|
| 1 | 0 | 我是父菜单 |
| 2 | 1 | 我是子菜单 |
| 3 | 2 | 我也是子菜单 |
最终效果：
我是父菜单 我是子菜单 我也是子菜单
那排序呢，要怎么来做？具体编码我不知道，但是肯定这个顺序肯定要保存起来的吧！因此我可以在调整下结构：
| id | pid | name | sort |
|---|---|---|---|
| 1 | 0 | 我是父菜单 | 0 |
| 2 | 1 | 我是子菜单 | 2 |
| 3 | 2 | 我也是子菜单 | 1 |
最终效果：
我是父菜单 我也是子菜单 我是子菜单
也就是呈现节点时，可以根据这个sort
来排序。
1.3 排序再思考
经过上面的思考后，我们对需求已经比较了解了，而且具体的实现也有一点底了。那到底要怎么去实现呢？菜单保存就不讨论了，主要就第2个问题，如何实现排序来展开探讨。可以先弄点数据来推导这个过程，
| id | pid | name |
|---|---|---|
| 1 | 0 | 菜单1 |
| 2 | 1 | 菜单2 |
| 3 | 2 | 菜单3 |
| 4 | 2 | 菜单4 |
| 5 | 2 | 菜单5 |
| 6 | 2 | 菜单6 |
| 7 | 0 | 菜单7 |
最终效果：
菜单1 菜单3 菜单4 菜单5 菜单6 菜单2 菜单7
问题1：现在假定要把菜单3移动到菜单4后面
需要传递的参数有：
id #当前移动的节点 id pid #当前移动的父节点 id index #移动的位置索引
从上面的效果图来看，菜单3和菜单4就是对调下位置。更改一下对应的sort
值即可。其他的都不用变化。
那我们可以知道，如果要移动的菜单和目标菜单的pid
一样的话，那只要变更下sort
位置即可。这个很简单。
问题2：把菜单7移到菜单2下面
需要传递的参数同上。
在结合上面的效果图来看，菜单7移到菜单2下面，可以这样做，
根据菜单7的 pid
获取pid
=菜单7.pid
的菜单列表，并将菜单7移除，同时对列表进行排序。这里是外部的排序。根据菜单2的 pid
获取pid
=菜单2.pid
的菜单列表，需要判断菜单列表的个数是否大于要移动的索引数，大于的话，可以直接按照索引添加元素；小于的话，直接添加。然后可以重新计算下sort
值。这里是内部的排序。
好像到这里，就已经可以了。很简单。但这里需要变更的菜单比较多。
除此之外呢，还有其他的算法吗？
设想一下，菜单创建的时候是有序的。而菜单在移动的过程中是部分有序的，可以做到最小化移动。在来看下效果图，
菜单1 菜单3 菜单4 菜单5 菜单6 菜单2 菜单7
问题1：现在假定要把菜单3移动到菜单4后面
这里只需要更改菜单3的sort
值，只要它的sort
值比菜单4要小，那不就实现了我们的要求了吗？
问题2：把菜单7移到菜单2下面
思考：根据菜单2的pid
获取pid
=菜单2.pid
的菜单列表。在根据要移动的位置，来更改sort
值。而这个sort
值又该怎么更新呢？如果现在不更改其他菜单，就只变更当前要移动菜单的sort
值。如果sort
值是这样分布的：
菜单1 10 菜单3 101010 菜单4 101011 菜单5 101012 菜单6 101013 菜单2 1010 菜单7 11
移动后会是这样：
菜单1 10 菜单7 101009 菜单3 101010 菜单4 101011 菜单5 101012 菜单6 101013 菜单2 1010
不过这样还是会有问题的。例如现在某个菜单要移动到菜单4，5之间，那sort
值又该怎么来定？
1.4 总结
的确，按照第一种方法来实现树形结构的排序是最简单的。按照第二种的话，sort
值的区间怎么来定呢？还有第三种、第四种吗？
❝本篇分享先到这里，欢迎关注。
❞
