无限层级菜单—左右值树型数据结构

技术分享28,062 人阅读

在上一篇博客中,我提到了后台菜单的问题。其实我不想写,因为比较久了,都差不多忘了,只记得当时理解得很痛苦。

 

下面这个菜单是一个多层级菜单的,在 计算机中心 菜单下,有6个子菜单,在子菜单 微信管理 下面又有3个子菜单,子菜单 企业号管理 又有2个子菜单,层次可以无限地增加,而且层级也是不固定的。

QQ截图20160117212949

 

那像这样的菜单结构在数据库应该怎么存储呢。

 

!没错,就是用树型数据结构,在之前的博客中,我也有写过对树型数据结构相关的想法(树型数组库结构设计),主要用 parent_id 字段记录父节点 id 值形成树成关系,为了方便查询不用使用递归,添加一个 parent_ids 辅助字段来记录节点的全部上级节点 id 。

 

这次我不想再用这种数据结构了,想尝试一下网上介绍的左右值的树型数据结构。

 

左右值意义

先看一下这张图

tree

如果你一眼就看出每个数字的意义,那请受我一拜~~~

 

这些菜单上左右两边的黑色数字就分别是节点的左右值了

请沿着根菜单的左边开始数起(1),往计算机中心的左边(2),再设备管理左边(3),设备管理右边(4),微信管理左边(5),服务号左边(6)。。。大家是否发现了规律。

把每个节点左右都当成两个连接点,从根菜单左边开始,沿着整个树的节点外围连接,一直连回到根菜单的右边,所经过节点的顺序就是节点的左右值了。

(不知这样表达大家是否能理解,我能想到的最通俗的表达也是这样了,不管,我就当是理解了)

 

很好,大家都理解了。

 

那我上一下菜单的数据库表图

QQ截图20160117233655

 

这里面还添加了一个 level 字段,这个大家都知道,这是节点的层级,根菜单的层级是0。

 

查询

让大家见识一下这种数据结构的魅力,你会发现查询变得如此的简单,曾经复杂的子孙节点查询,现在变得如果简单。

 

查询某一节点下面的全部子孙节点

 

计算某一节点下有多少个子孙节点

例如想查询第一张图上的计算机中心这个菜单底下有多少个子菜单
计算机中心的左值为2 右值为11。

子菜单数量(不包括自身节点)

( 右值 – 左值 – 1 ) / 2  => ( 11 – 2 – 1 ) / 2 = 4

子菜单数量(包括自身节点)

( 右值 – 左值 + 1 ) / 2  => ( 11 – 2 + 1) / 2 = 5

 

节点排序

当你在 sql 查询时排序条件加上 order by l 的话,你会发现,返回的节点是按节点全部展开后由上往下的顺序,这个非常有用,在下面的 菜单跟树表格中非常关键。

QQ截图20160118202312

 

查询某一节点的全部父祖节点

 

判断

判断某一节点是否是某一节点的子节点

假如我想查询企业号menu1(左:8,右:9)是否是设备管理menu2(左:3,右:4)的子菜单。

判断式: menu1.l > menu2.l AND menu1.r < menu2.r

8 > 3 AND 9 <4 = false

说明企业号不是设备管理的子菜单

 

判断某一节点是否是某一节点的父节点

假如我想查询计算机中心menu1(左:2,右:11)是否是服务号menu2(左:6,右:7)的父菜单。

判断公式: menu1.l < menu2.l AND menu1.r > menu2.r

2 < 6 AND 11 > 7 = true

说明计算机中心是服务号的父菜单

 

判断某一节点是否有子菜单

将节点的右值减去左值,如果大于1则说明有。

 

相信以上的查询及判断已经可以满足对数据的日常使用了,那下面就来一个实际例子,就是我上个博客说到的 AdminLTE 后台菜单。

根据 AdminLTE 模板的 html 结构,以我第一个图为例,那生成的 html 代码如下所示(菜单不包括根菜单)

 

一个菜单就是一个 li ,如果菜单有子菜单的话,就得加上 treeviewcss 样式,然后在里面嵌套一个 treeview-menu 样式的 ul ,再写上菜单 li ,以此类推,然后哪个菜单是当前打开的就在其 li 上及全部上级菜单 li 加上 active 样式。

 

我需要拼结的就是 <ul class="sidebar-menu"></ul> 中间的那些 html ,那怎么把这些数据转变成菜单的 html 呢,理解上比递归还要难,现在回头看看我当时写的代码,我真感谢我当时有写注释。

 

上面的理解完,再来看下面这张图,想想这个 table 怎么写的,特别是菜单名称前面那些线,这可不是什么树插件哦,这些都是普通的文本。

QQ截图20160118200959

 

我直接上代码吧,这代码我也快看不懂了,下面这个方法,可以获取一个带有 line 键名的菜单数组。

在模板中遍历数组时,就可以用 $menu[“line”] 来输出菜单名称前面的连接线。

 

添加节点

查询是如此的优雅,但它的增删修就略显麻烦,这就是美丽的代价。

想想,现在我想添加个 WIFI管理 菜单到 设备管理 后面,如下图所示,整个树的数据会产生什么变化。

new_tree

你会发现在 WIFI管理 后面的到 根菜单 的右边,所有的连接点都增加了 2。

因为一个节点有两个连接点,将这个新增节点放到树结构的任意位置后,新增节点后面的节点将受到影响,都增加了2。

 

下面是我基于 thinkphp 写的一个新增菜单的代码,传入一个父菜单的 Id 和新增菜单的信息,新增菜单将添加到父菜单的子级菜单的最后一个。

 

删除节点

删除节点跟新增节点方向相反,删除节点后,将受到影响的节点减去被删除节点的影响值(一个节点两个连接点,就是2,如果移动的节点是父节点,那么影响值就是右值 – 左值 + 1)。

下面是我写的删除菜单的代码,但我这个限制了只能删除末级菜单,就是没有子菜单的菜单。

 

移动节点位置

接下来才是最难以理解的地方,这才是我不想写这个博客的主要原因。

如果我现在想把 组织结构 菜单移动到 计算机中心 菜单下,微信管理 菜单前,如下图所示,那会对整个树产生什么影响呢。

moved_tree

比对一下两边的节点的左右值,会发现,受到影响的节点都是移动节点的原位置到目标位置中间经过路径的节点。

其实移动节点位置最重要的就是计算出受到影响的节点,然后计算机移动节点的影响值(一个节点两个连接点,就是2,如果移动的节点是父节点,那么影响值就是右值 – 左值 + 1),根据移动节点的相对位置(前、后、子级)加或减去这个影响值。

 

我还是直接上代码吧,这个方法需要传入一个移动节点的 Id,一个目标节点的 Id,一个相对于目标节点的位置。

比如我想把 组织结构 移动到 微信管理 前面,那么 组织结构 就是 移动节点微信管理就是 目标菜单前面 就是 相对位置

大家自己理解,我很难用言语来讲述这坨代码。

 

总算写完了,这就是我对于左右值树型数据结构的一些想法跟实践,希望对大家有所帮助。