PHP无限分类——左右值实现

Post at 2012-06-13 02:03:33php无限分类左右值预排序树

网站，一定离不开多级分类：小到导航栏的两三级分类，大到其它货物的无限分类等。PHP无限分类有多种算法，本文将介绍的是PHP左右值无限分类，也称为预排序树无限分类 ...

• 什么是左右值无限级分类
• 左右值无限分类的优缺点
• PHP无限分类研究对象
• 创建PHP左右值无限分类的SQL数据
• 获取所有的后代节点
• 计算所有子类的数量
• 插入分类算法
• PHP插入节点代码
• 移动节点演示图
• PHP移动分类函数
• 获取所有的父级
• 本文本演示文件下载
• PHP无限分类扩展阅读

什么是左右值无限级分类

左右值无限级分类，也称为预排序树无限级分类，是一种有序的树状结构，位于这些树状结构中的每一个节点都有一个“左值”和“右值”，其规则是：每一个后代节点的左值总是大于父类，右值总是小于父级，右值总是小于左值。处于这些结构中的每一个节点，都可以轻易的算出其祖先或后代节点。因此，可以用它来实现无限分类。

左右值无限分类的优缺点

优点：

• 通过一条SQL就可以获取所有的祖先或后代，这在复杂的分类中非常必要
• 通过简单的四则运算就可以得到后代的数量

缺点

• 分类操作麻烦
• 无法简单的获取子代（请看请“子代”和"后代"）

PHP无限分类研究对象

本文用于演示的对象：狼魂博客[http://pjiaxu.com]的导航栏，其结构如下图：

1.[1]舞文弄墨[8] [9]洞若观火[12] [13]WEB开发[20]
2.------------------------------------------------------
3.| | |
4.| | |
5.| [10]用户体验[11] |
6.| |
7.-------------------------------------------- ----------------------------------
8.[2]似水流年[3] [4]纸上谈兵[5] [6]隔岸观火[7] [14]PHP[15] [16]JS[17] [18]HTML[19]

其中的[数字]就是每一级的“左右值”，这里的左右值是早已经存在的，我们就以此为例，逐步研究这种算法。

创建PHP左右值无限分类的SQL数据

01.createtable `navs`(
02.`id`int primary key auto_increment,
03.`name`varchar(32) notnull,
04.`lft`int not null,
05.`rght`int not null
06.);
07.insertinto `navs`(`name`,`lft`,`rght`)
08.values
09.('舞文弄墨',1,8),
10.('似水流年',2,3),
11.('纸上谈兵',4,5),
12.('隔岸观火',6,7),
13.('洞若观火',9,12),
14.('用户体验',10,11),
15.('WEB开发',13,20),
16.('PHP',14,15),
17.('JS',16,17),
18.('HTML',18,19);

上图，我为了方便，将SQL有意识的缩进了一下，这应该可以一目了然这种结构了吧。

获取所有的后代节点

了解了PHP预排序村的规则后，我们就可以很清晰的知道如何获取某个节点的所有子代——左值比它大，右值比它小。如，我们要获取“舞文弄墨”的所有子后代，可以使用以下的SQL语句：

1.select* from `navs` where `lft`>1 and `rght`<8

得到如下的结果：

计算所有子类的数量

有人认为使用 count 配合上面的语句就可以算出，这当然是可以的，但有更快的方式：每有子类节点中每个节点占用两个值，而这些值都是不一样且连续的，那些就可以计算出子代的数量=(右值-左值-1)/2。减少1的原因是排除该节点，你可以想像一个，一个单节点，左值是1，右值是2，没有子类节点，而这时它的右值-左值=1.

插入分类算法

还是先以图为例，比如，现在狼魂的博客[http://pjiaxu.com]发行了一个pblog博客系统，那么它想要在*导航上加上pblog这个导航菜单，需要怎么做（这是加*菜单的例子）？然而，它又想在Javascript中加入个jQuery分类，又该怎么做？做这些操作有两个重难点：

1. 为插入分类分配一个左右值
2. 更新其它节点的左右值

结果的示例图如下：

01.[1]舞文弄墨[8] [9]洞若观火[12] [13]WEB开发[22] [23]pblog[24]
02.-----------------------------------------------------------------------
03.| | |
04.| | |
05.| [10]用户体验[11] |
06.| |
07.-------------------------------------------- ----------------------------------
08.[2]似水流年[3] [4]纸上谈兵[5] [6]隔岸观火[7] [14]PHP[15] [16]JS[19] [20]HTML[21]
09.|
10.[17]jquery[18]

我们分析一下这两种情况：

• 插入最*节点：它的左右值与该树中最大的右值有关：左值=最大右值+1，右值=最大右值+2，你可以自己模拟一下；
• 插入子节点：它的左右值与它的父级有关：左值=父级的右值，右值=父级的左值+1，这时要更新的数据有：父级的右值，所有左值大于父级左级，右值大于低级右值的节点左右值都应该+2；你可以模拟在jquery下再加一个节点看是不是如此。

有了这些分析，就不难用PHP来实现了，下面，就使用PHP写一个插入算法；

PHP插入节点代码

01.define('DB_HOST','localhost');
02.define('DB_USER','root');
03.define('DB_PWD','`12345');
04.define('DB_NAME','test');
05.classEndlessByLR
06.{
07.functioninsert($name,$parentid)
08.{
09.$db= new mysqli(DB_HOST,DB_USER,DB_PWD,DB_NAME);
10.if($parentid== 0)
11.{
12.//增加*，即与WEB开发同级，详见[http://pjiaxu.com/]导航中的Pblog
13.$sql= 'select max(`rght`) as `maxid` from `navs`;';
14.$result= $db->query($sql);
15.//这里基本不用做出错判断，一般都有数据的
16.$row= $result->fetch_array(MYSQLI_ASSOC);
17.$lft= $row['maxid']+1;
18.$rght= $lft+1;
19.}
20.else
21.{
22.$sql= "select * from `navs` where `id`={$parentid};";
23.$result= $db->query($sql);
24.//这里应做个出错判断
25.$row= $result->fetch_array(MYSQLI_ASSOC);
26.$rght= $row['rght'];
27.$sql= "update `navs` set `rght`=`rght`+2 where `rght`>={$rght};";
28.$db->query($sql);
29.$sql= "update `navs` set `lft`=`lft`+2 where `lft`>{$rght};";
30.$db->query($sql);
31.$lft= $row['rght'];
32.$rght= $lft+1;
33.}
34.$sql= "insert into `navs`(`name`,`lft`,`rght`)values('{$name}',{$lft},{$rght});";
35.return$db->query($sql);
36.}
37.}

注意，使用这段PHP函数需要以上SQL的支持；现在，我们就使用这个函数插入刚才所说的两个节点，看看结果是否一致？

1.$eblr= new EndlessByLR();
2.$eblr->insert('pblog',0);//0是*, 9是JS，在插入之前，你应该是知道的！
3.$eblr->insert('jquery',9);

产生了以下的结果：

你可以花点时间验证一下是不是跟演示图一样。

网上搜索引擎有一个相似的文章占了前几页，在更新又值时是使用 `rght`>{$rght} 而不是 `rght`>={$rght}；就我今天目测了N久的得出结果：这是不科学的！

解决了插入的问题，实际上就解决了很多实际应用了。现在，我们需要研究另一种操作：移动节点——这个是要了亲命的操作！

移动节点演示图

我们还是来演示推算一下再到代码中去吧。突然间，狼魂博客[http://pjiaxu.com/map.html]觉得pblog大多的内容都是PHP，那何不把它移动到PHP分类下呢？

01.[1]舞文弄墨[8] [9]洞若观火[12] [13]WEB开发[22](24) [25]other[26](假设存在)
02.----------------------------------------------------------------------
03.| | |
04.| | |
05.| [10]用户体验[11] |
06.| |
07.-------------------------------------------- --------------------------------------
08.[2]似水流年[3] [4]纸上谈兵[5] [6]隔岸观火[7] [14]PHP[15](17) (18)[16]JS[19](21) (22)[20]HTML[21](23)
09.| |
10.(15)[23]pblog[24](16) (19)[17]jquery[18](20)

方括号[]中的数字是现在的左右值，小括号()中的数字是期望值，也就是移动后应该得到的左右值。最终将是以下的样子：

01.[1]舞文弄墨[8] [9]洞若观火[12] [13]WEB开发[24]
02.----------------------------------------------------------------------
03.| | |
04.| | |
05.| [10]用户体验[11] |
06.| |
07.-------------------------------------------- ---------------------------------------
08.[2]似水流年[3] [4]纸上谈兵[5] [6]隔岸观火[7] [14]PHP[17] [18]JS[21] [22]HTML[23]
09.| |
10.[15]pblog[16] [19]jquery[20]

我们继续分析——移动共可以四个方向移动：

• pblog移动到php之下成为它的子类
• pblog移动到php之上成为它的父类
• pblog移动到php左右成为它的兄弟

我们以子类为例子演示推算一下，假设(x1,y1)、(x2,y2)是php和pblog的左右值，那么，我们能过分析得到以下的结论：

• 左值在min(y1,y2)最小右值和max(x1,x2)最大左值之间都需要加2
• 右值在min(x1,x2)最小左值和max(y1,y2)最大右值之间都需要加2
• 移动节点的左值=父类节点的右值，右值=父类节点右值+1

通过以上的分析，就可以写出移动节点的PHP代码。

PHP移动分类函数

01.<?php
02.classEndlessByLR{
03.//......
04.//......
05.//接上面的代码
06.functionmove($formid,$toid, $derect)
07.{
08.if($formid== $toid)
09.{
10.returntrue;
11.}
12.$sql= "select * from `navs` where `id`=$formid
13.union
14.select * from `navs` where `id`=$toid";
15.$db= new mysqli(DB_HOST,DB_USER,DB_PWD,DB_NAME);
16.$result= $db->query($sql);
17.$rows= $result->fetch_all(MYSQLI_ASSOC);//php版本要大于5.3才可以用
18.if($rows[0]['lft'] >$rows[1]['lft'])
19.{
20.$maxlft= $rows[0]['lft'];
21.$minlft= $rows[1]['lft'];
22.}
23.else
24.{
25.$maxlft= $rows[1]['lft'];
26.$minlft= $rows[0]['lft'];
27.}
28.if($rows[0]['rght'] >$rows[1]['rght'])
29.{
30.$minrght= $rows[1]['rght'];
31.$maxrght= $rows[0]['rght'];
32.}
33.else
34.{
35.$minrght= $rows[0]['rght'];
36.$maxrght= $rows[1]['rght'];
37.}
38.
39.switch($derect)
40.{
41.case'child':
42.$sql= "update `navs` set `lft`=`lft`+2 where `lft` between $minrght and $maxlft";
43.$db->query($sql);
44.//echo $sql;
45.$sql= "update `navs` set `rght`=`rght`+2 where `rght` between $minlft and $maxrght";
46.$db->query($sql);
47.//echo $sql;
48.$lft= $minlft+1;
49.$rght= $lft+1;
50.$sql= "update `navs` set `lft`=$lft,`rght`=$rght where id=$formid limit 1;";
51.//echo $sql;
52.$db->query($sql);
53.break;
54.case'parent':
55.break;
56.case'before':
57.break;
58.case'after':
59.break;
60.}
61.}

这个函数就将我们刚才的分析以代码的方式实现，现在我们就将pblog移到PHP子类中去：

1.$eblr->move(11,8,'child');

得到的结果如下图：

如要移动看其它位置，看各位模仿移动子类自行分析。

获取所有的父级

这个为什么要放最后，那是——只有在最后，jquery才有直属两个祖先——js和web开发，其实看一下就知道了，获取一个分类的直属祖先（类似于我们平时看到网站的"你所在的位置"一样获取一条直达首页的路径）。规则就是：左值小于该分类，右值大于该分类的节点；如，获取jquery的路径就是：

1.select* from `navs` where `lft`<17 and `rght`>28